Abel maraton

[lfe]

Svar: Løsningene danner en uendelig familie med funksjoner $\mathcal{F}$. Denne familien består av alle funksjoner som tilfredsstiller at for hvert positive odde heltall $n$ kan vi velge to positive heltall $a$ og $b$, der $ab=n$, slik at $f(2^{m}n)=2^{m}a+b$.

Bevis:

Vi ser at likningen i oppgaven er ekvivalent med $$1)P(m,n):-(2^m-1)n=(f(2^{m}n)-f(n))(f(2^{m}n)-2^{m}f(n))$$
Videre viser vi oppgaven med induksjon.

Induksjonsgrunnlag: $f(n)=a+b$ og $f(2n)=2a+b$, der $ab=n$
Av 1) er $f(2n)-f(n)=a$ og $f(2n)-2f(n)=-b$, der $ab=n$, siden $f(2n)-f(n)>f(2n)-2f(n)$. Dette likningssystemet gir oss at $f(n)=a+b$ og $f(2n)=2a+b$.

Induksjonstrinn: Anta at $f(2^{m}n)=2^{m}a+b$, for alle $m<k$. Vi vil vise at denne antagelsen impliserer $f(2^{k}n)=2^{k}a+b$.
La $f(2^{k}n)=x$. Likningene $P(1,2^{k-1}n)$ og $P(2,2^{k-2}n)$ kan faktoriseres slik at vi får $$0=(x-2^{k-1}a-b)(x-2^{k}a-2b)+2^{k-1}ab=(x-2^{k}a-b)(x-2^{k-1}a-2b)$$ $$0=(x-2^{k-2}a-b)(x-2^k-4b)+9\cdot 2^{k-2}ab=(x-2^{k}a-b)(x-2^{k-2}a-4b)$$ Det betyr at $f(2^{k}n)=2^{k}a+b$, med mindre $2^{k-1}a-2b=2^{k-2}-4b$.
Vi tar nå for oss tilfellet der $2^{k-1}a-2b=2^{k-2}-4b$. Likningen forenkles til $2^{k-2}a=2b$. Siden både $a$ og $b$ er oddetall, må $a=b$ og $k=3$. Det betyr at $n=c^2$, der $c$ er et heltall. Vi vet at $f(n)=2c$, $f(2n)=3c$ og $f(4n)=5c$. Det holder dermed å vise at $f(8n)\ne 6c$. Dette følger av likningen $P(3,n)$ siden $f(8n)=6c$ leder til en motsigelse.

Induksjonstrinnet ovenfor impliserer egenskapen til $\mathcal{F}$. En rask test gir oss også at alle funksjoner i $\mathcal{F}$ tilfredsstiller likningen.

[lfe]

La $a,b,c\in \mathbb{R}$. Vis $$ab+bc+ca+max\{|a-b|,|b-c|,|c-a|\}\le 1+\frac{1}{3}(a+b+c{)}^2$$

[Lil_Flip39]

UTAG, la $a⩽b⩽c$
da får vi $ab+bc+ca+c-a⩽1+\frac{1}{3}(a+b+c{)}^2$
hvis vi flytter $ab,bc,ca$ til høre siden, er finner vi faktoriseringen:
$c-a⩽1+\frac{1}{6}((a-b{)}^2+(b-c{)}^2+(c-a{)}^2)$ nå utnytter vi ife sin favoriituliket, cauchy shwarz ulikheten.
da får vi $(1+1)((a-b{)}^2+(b-c{)}^2)⩽(a-c{)}^2$. da har vi:
$1+\frac{1}{6}((a-b{)}^2+(b-c{)}^2+(c-a{)}^2)⩾1+\frac{1}{4}(c-a{)}^2$.
Nå er det nok å vise $c-a⩽1+\frac{1}{4}(c-a{)}^2⟺1⩽\frac{1}{c-a}+\frac{c-a}{4}$, men dette følger av AM-GM

[Lil_Flip39]

ny oppgave:
finn alle $k$ slik at eksiterer et naturlig tall $n$ slik at:
$7^k\mid 1^n+2^n+3^n$

[lfe]

Løsning: Alle naturlige tall $k$
Bevis:
Vi viser først et lemma.

Lemma: La $r$ være en primitiv rot modulo $p$. Dersom $r^{p-1}\not\equiv 1(\mathrm{mod}{p}^2)$, så er $r$ en primitiv rot modulo $p^m$ for alle naturlige tall $m$.
Bevis:
Anta at $l\mid p-1$. Åpenbart er $r^{\frac{\varphi (p^m)}{l}}\not\equiv 1(\mathrm{mod}{p}^m)$. Det holder dermed å vise at $p^{p^{m-2}(p-1)}\not\equiv 1(\mathrm{mod}{p}^m)$
Anta for motsigelsens skyld at $p^{p^{m-2}(p-1)}\equiv 1(\mathrm{mod}{p}^m)$. Av LTE vet vi at $a^p\equiv 1(\mathrm{mod}{p}^m)$ impliserer $a\equiv 1(\mathrm{mod}{p}^b)$, der $b\le m-1$. Med induksjon får vi dermed at $p^{(p-1)}\not\equiv 1(\mathrm{mod}{p}^2)$, en motsigelse.

En rask sjekk gir oss at 3 er en primitiv rot modulo 7 og $3^6\not\equiv 1(\mathrm{mod}49)$. Dermed er 3 en primitiv rot modulo $7^k$. Videre har vi at $2^3\equiv 1(\mathrm{mod}7)$. Av LTE er dermed $2^{\frac{\varphi (7^k)}{2}}\equiv 1(\mathrm{mod}{7}^k)$. Vi har derfor at når $n=\frac{\varphi (7^k)}{2}$, så er $1^n+2^n+3^n\equiv 1+2-3\equiv 0(\mathrm{mod}{7}^k)$.

[lfe]

Ny oppgave:
La $A$ være mengden av rasjonelle tall $\frac{a}{b}$ slik at $0<\frac{a}{b}<1$ og $gcd(a,b)=1$. Vis at summen av nevnerene til $n$ innbyrdes ulike tall fra $A$ minst er lik $\frac{1}{3}{n}^{\frac{3}{2}}$.

[CCPenguin]

Vi viser først et nyttig lemma:
la $f(n)=\frac{n^{3/2}}{3}$
Vi på summen s(n) = 2+3+3+4+4+4+5+5+5+5+6+6+6+6+6..., der hver i opptrer i-1 ganger, og n betegner antall tall som summes sammen
Lemma 1: $s(n)>=f(n)$
Vi bruker induksjon på $\frac{(i+1)i}{2}$ for å vise dette.
Basecase, $s(1)=2>=\frac{1}{3}$
videre antar vi at påstanden gjelder for $s(\frac{(i+1)i}{2})$, altsa opptill rett før rekken øker tallet den legger til, og viser at den holder fram til $s((\frac{(i+1)(i+2)}{2})$
Vi ser først at $f^{\prime }(n)>0$, og at s vokser konstant mellom $\frac{(i+1)i}{2}$
Siden vi antar $s(\frac{(i+1)i}{2})>f(\frac{(i+1)i}{2})$, får vi at om f blir større på en verdi $n\in (\frac{(i+1)i}{2},\frac{(i+1)(i+2)}{2})$, må vi også ha $f(\frac{(i+1)(i+2)}{2}>s(\frac{(i+1)(i+2)}{2}$
Dette gir implikasjonen: f større en s en n i intervallet => f større en s på siste. ($f(n)>s(n)=>f(s(\frac{(i+1)(i+2)}{2}>=s(s(\frac{(i+1)(i+2)}{2}$
som er ekvivalent med: f ikke større på siste => f ikke større på en i intervallet, av LEM $(f(\frac{(i+1)(i+2)}{2}<s(s(\frac{(i+1)(i+2)}{2})=>f(n)<s(n)foralleniintervallet)$
som er ekvivalent med: f mindre på siste => f ikke større på en i intervallet $f(\frac{(i+1)(i+2)}{2})<s(\frac{(i+1)(i+2)}{2})=>f(n)<s(n)foralleniintervallet)$
så vi må bare vise at $s(\frac{(i+1)(i+2)}{2}>=f(\frac{(i+1)(i+2))}{2}$
der $s(\frac{(i+1)(i+2)}{2}$ er en sum som ser slik ut: (vi setter i+1 = i for enkelhetens skyld)
$2+3+3+4+4+4+....(i+1)+(i+1)+..+(i+1)+(i+1)$, der (i+1) opptrer i ganger.

la $k(n)=s(\frac{(n+1)(n)}{2}$, da er $k(n)=sum1n{i}^2+i=\frac{(n+2)(n+1)n}{3}$
Husk at vi vil vise $k(i)=\frac{(n+2)(n+1)n}{3}>=f(\frac{(n+1)(n)}{2})=\frac{(\frac{(n+1)(n)}{2}{)}^{3/2}}{3}$
Som er det samme som:
$(n+2)(n+1)n>=\frac{(n+1)(n)}{2}{)}^{3/2}$
$(n+2{)}^2(n+1{)}^2{n}^2>=\frac{(n+1{)}^3(n{)}^3}{2^3})$
$8\ast (n+2{)}^2>=(n+1)n$, som åpenbart stemmer:

Nå tilbake til oppgaven.

først ser vi at den minimale summen av n tall i A, vil opptre når nevnere en minimale. Vi vet at for hver n er det maks n-1 brøker med n som nevner i A, så den minimale summen vil være større eller lik en s(n),
vi har vist at $s(n)>=f(n)$ så oppgaven er bevist

[CCPenguin]

Ny oppgave:
finn alle n slik at
$\frac{n^2+1}{\lfloor \sqrt{n}{\rfloor }^2+2}$
er et heltall

[Lil_Flip39]

det er ingen $n$ som oppfyller kravet.
la $\lfloor \sqrt{n}\rfloor =a$, og da blir $n=a^2+b$ hvor $0⩽b⩽2a$
da blir oppgaven til $a^2+2\mid (a^2+b{)}^2+1$ hvis vi trekker fra $a^4+2a^2$ og $(2b-2)(a^2+2)$ fra høyre siden får vi:
$a^2+2\mid b^2-4b+5⩽(2a-2{)}^2+1<4(a^2+2)$ som impliserer
$(b-2{)}^2+1=k(a^2+2)$ hvor $k=1,2,3$
1) $k=1$
dette går ikke siden da må det være 2 kvadratall med differanse 1, som er umulig untatt hvis det er 0 men det går ikke.
2) $k=2$
$(b-2{)}^2-3=2a^2$
vi utnytter modulo 8, som impliserer at venstresiden er $\equiv 5,6,1(mod8)$ mens høyresiden kan bare være $0,2(mod8)$ som er en motstigelse.
3) $k=3$
høyre siden er et multippel av 3, men venstre siden er $\equiv 1,2(mod3)$ som er en motstigelse.

dette er alle muligheter så vi er ferdige.

[Lil_Flip39]

la $\mathbb{N}$ være de plsitive heltallene.
finn alle funksjoner $f:$ $\mathbb{N}\to \mathbb{N}$ slik at
$x^2-y^2+2y(f(x)+f(y))$
er et kvadratall for alle positive heltall $x,y$

[lfe]

Løsning: $f(x)=x$
Bevis:
La $P(x,y)$ være uttrykket i oppgaven.

1) Påstand: $p\mid f(p)$ for alle primtall $p$.
Bevis:
$P(p,p)$ gir oss at $4pf(p)$ er et kvadrattall. Dermed må $p\mid f(p)$.

2) Påstand: $-y^2+2yf(y)$ er et kvadrattall for alle $y\in \mathbb{N}$.
Bevis:
Det er et velkjent lemma at dersom $a$ er en kvadratisk rest modulo $p$ for alle primtall $p$, så er $a$ et kvadrattall.
Av 1) gir $P(p,y)$ oss at $-y^2+2yf(y)$ er en kvadratisk rest for alle primtall $p$. Dermed er $-y^2+2yf(y)$ et kvadrattall.

3) Påstand: $(f(x{)}^2+1)y\ge 2f(y)$
Bevis:
Åpenbart er $P(x,y)>-y^2+2yf(y)$. Siden begge sidene av ulikheten er kvadrattall, har vi at $$x^2+2yf(x)-y^2+2yf(y)\ge (\sqrt{-y^2+2yf(y)}+1{)}^2=-y^2+2yf(y)+2\sqrt{-y^2+2yf(y)}+1$$
Dette impliserer $y^{2}f(x{)}^2\ge -y^2+2yf(y)$ siden $x\ge 1$. Dermed er $(f(x{)}^2+1)y\ge 2f(y)$.

Skuffeprinsippet og 3) impliserer at det eksisterer et heltall $n$ slik at $f(p)=np$ for uendelig mange $p$.

4) Påstand: $f(x)=x$
Bevis:
La $q$ være et primtall slik at $f(q)=nq$.
Vi har dermed av $P(q,m)$ at $p^2-m^2+2mnq+2mf(m)=(p+mn{)}^2-(mn{)}^2-m^2+2mf(m)$ er et kvadrattall. Dette impliserer at $-(mn{)}^2-m^2+2mf(m)$ er differansen mellom uendelig mange kvadrattall, en motsigelse med mindre $2mf(m)=(mn{)}^2+m^2$ for alle $m$. Det betyr at $f(m)=\frac{n^2+1}{2}m$ for alle $m$. Dermed har vi $n=\frac{n^2+1}{2}$, som kun har løsningen $n=1$.

[lfe]

Ny oppgave:
La $S$ være en mengde med ikke-negative heltall. Vi definerer $r_S(n)$ til å være antall ordnede tupler $(s_1,s_2)$ slik at $s_1+s_2=n$, $s_1\in S$, $s_2\in S$ og $s_1\ne s_2$. Eksisterer det en partisjon av mengden ikke-negative heltall inn i to mengder $A$ og $B$ slik at $r_A(n)=r_B(n)$ for alle positive heltall $n$?

[CCPenguin]

Vi viser at mengden A, B der A er alle tall med et partall antall enere i sin binære representasjon, og B er alle med et odde antall går.
La $n\in \mathbb{N}$, og anta x,y i A eller B summer til n.
Vi ser på alle sifferplassene i desimalrepresentasjonen til x og y der de har forskjellige tall (1 og null)
f eks, om vi har tallene 1001, og 1100, ser vi på 2. og 4. plass, der de er forskjellige. Hver gang vi også bytter en 1 og 0 på disse plassene, byttes pariteten til begge tallene og vi får ett nytt gyldig par.
Om det er k plasser, er det $2^{k-1}$ forskjellige uordnede par vi kan lage. Halvparten av disse vil åpenbart være partall, og halvparten oddetall. Om vi repeterer dette for alle par x, y som summer til n, får vi at det er like mange.

[CCPenguin]

Gitt likningen:
$a^b{b}^c=c^a$
Der a,b,c er positive heltall, vis at:
(i) en hver primdivisor av a deler b.
(ii) Løs likningen under antagelsen $b\ge a$
(iii) vis at likningen har uendelig antall løsninger

[Lil_Flip39]

for (i), anta $p\mid a$ og $p$ ikke deler $b$. da har vi $b\times v_p(a)=a\times v_p(c)$ Vi vet at $v_p(a\times v_p(c))⩾v_p(a)$, men siden $b$ ikke har noen faktor av $p$, får vi at $v_p(v_p(a))⩾v_p(a)$ som er en motstigelse.
for (ii) har vi da at $a^{a+c}⩽c^a$ la $x=c/a$, da får vi at $a^{ax}⩽x^a$ som ikke holder med mindre $a=b=c=1$. så $(1,1,1)$ er eneste løsning
for (iii) $(a,b,c)=(n^n,n^{n-1},n^n)$ for alle naturlige tall $n$ funker, siden vi får at $n^{n^n}\times n^{n^{n+1}-n^n}=n^{n^{n+1}}$, som åpenbart holder.