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^ma+b$.

Bevis:

Vi ser at likningen i oppgaven er ekvivalent med \[1) \quad P(m,n):\quad -(2^m-1)n=(f(2^mn)-f(n))(f(2^mn)-2^mf(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^kn)=2^ka+b$.
La $f(2^kn)=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^ka-2b)+2^{k-1}ab=(x-2^ka-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^ka-b)(x-2^{k-2}a-4b)\] Det betyr at $f(2^kn)=2^ka+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)\neq 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|\}\leq 1+\frac{1}{3}(a+b+c)^2\]

[Lil_Flip39]

UTAG, la $a\leqslant b\leqslant c$
da får vi $ab+bc+ca+c-a \leqslant 1+\frac{1}{3}(a+b+c)^2$
hvis vi flytter $ab,bc,ca$ til høre siden, er finner vi faktoriseringen:
$c-a \leqslant 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)\leqslant (a-c)^2$. da har vi:
$1+\frac{1}{6}((a-b)^2+(b-c)^2+(c-a)^2)\geqslant 1+\frac{1}{4}(c-a)^2$.
Nå er det nok å vise $c-a\leqslant 1+\frac{1}{4}(c-a)^2\iff 1\leqslant \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 \pmod{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{\phi(p^m)}{l}}\not\equiv 1 \pmod{p^m}$. Det holder dermed å vise at $p^{p^{m-2}(p-1)}\not\equiv 1\pmod{p^m}$
Anta for motsigelsens skyld at $p^{p^{m-2}(p-1)}\equiv 1\pmod{p^m}$. Av LTE vet vi at $a^p\equiv 1 \pmod{p^m}$ impliserer $a\equiv 1\pmod{p^{b}}$, der $b\leq m-1$. Med induksjon får vi dermed at $p^{(p-1)}\not\equiv 1\pmod{p^2}$, en motsigelse.

En rask sjekk gir oss at 3 er en primitiv rot modulo 7 og $3^6\not\equiv 1\pmod{49}$. Dermed er 3 en primitiv rot modulo $7^k$. Videre har vi at $2^3\equiv 1 \pmod 7$. Av LTE er dermed $2^{\frac{\phi(7^k)}{2}}\equiv 1 \pmod{7^k}$. Vi har derfor at når $n=\frac{\phi(7^k)}{2}$, så er $1^n+2^n+3^n\equiv 1+2-3\equiv 0\pmod{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 [tex]f(n) = \frac{n^{3/2}}{3}[/tex]
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: [tex]s(n) >= f(n)[/tex]
Vi bruker induksjon på [tex]\frac{(i+1)i}{2}[/tex] for å vise dette.
Basecase, [tex]s(1)= 2>= \frac{1}{3}[/tex]
videre antar vi at påstanden gjelder for [tex]s(\frac{(i+1)i}{2})[/tex], altsa opptill rett før rekken øker tallet den legger til, og viser at den holder fram til [tex]s((\frac{(i+1)(i+2)}{2})[/tex]
Vi ser først at [tex]f'(n)>0[/tex], og at s vokser konstant mellom [tex]\frac{(i+1)i}{2}[/tex]
Siden vi antar [tex]s(\frac{(i+1)i}{2}) > f(\frac{(i+1)i}{2})[/tex], får vi at om f blir større på en verdi [tex]n \in (\frac{(i+1)i}{2},\frac{(i+1)(i+2)}{2})[/tex], må vi også ha [tex]f(\frac{(i+1)(i+2)}{2} > s(\frac{(i+1)(i+2)}{2}[/tex]
Dette gir implikasjonen: f større en s en n i intervallet => f større en s på siste. ([tex]f(n) > s(n) => f(s(\frac{(i+1)(i+2)}{2} >= s(s(\frac{(i+1)(i+2)}{2} [/tex]
som er ekvivalent med: f ikke større på siste => f ikke større på en i intervallet, av LEM [tex]( f(\frac{(i+1)(i+2)}{2} < s(s(\frac{(i+1)(i+2)}{2} ) => f(n) < s(n) for alle n i intervallet)[/tex]
som er ekvivalent med: f mindre på siste => f ikke større på en i intervallet [tex]f(\frac{(i+1)(i+2)}{2}) < s(\frac{(i+1)(i+2)}{2}) => f(n) < s(n) for alle n i intervallet)[/tex]
så vi må bare vise at [tex]s(\frac{(i+1)(i+2)}{2} >= f(\frac{(i+1)(i+2))}{2} [/tex]
der [tex]s(\frac{(i+1)(i+2)}{2}[/tex] er en sum som ser slik ut: (vi setter i+1 = i for enkelhetens skyld)
[tex]2+3+3+4+4+4 + .... (i+1)+ (i+1)+..+ (i+1)+ (i+1)[/tex], der (i+1) opptrer i ganger.

la [tex]k(n) = s(\frac{(n+1)(n)}{2}[/tex], da er [tex]k(n) = sum{1}{n} i^2 +i = \frac{(n+2)(n+1)n}{3}[/tex]
Husk at vi vil vise [tex]k(i) = \frac{(n+2)(n+1)n}{3} >= f(\frac{(n+1)(n)}{2}) = \frac{(\frac{(n+1)(n)}{2})^{3/2}}{3} [/tex]
Som er det samme som:
[tex](n+2)(n+1)n >=\frac{(n+1)(n)}{2})^{3/2}[/tex]
[tex](n+2)^{2}(n+1)^{2} n^{2} >= \frac{(n+1)^{3}(n)^{3}}{2^{3}})[/tex]
[tex]8*(n+2)^2 >= (n+1)n[/tex], 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 [tex]s(n) >= f(n)[/tex] så oppgaven er bevist

[CCPenguin]

Ny oppgave:
finn alle n slik at
[tex]\frac{n^2 +1}{⌊\sqrt{n}⌋^2 +2}[/tex]
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\leqslant b \leqslant 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\leqslant (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 (mod 8)$ 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(mod 3)$ 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} \rightarrow \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\geq 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)\geq (\sqrt{-y^2+2yf(y)}+1)^2= -y^2+2yf(y)+2\sqrt{-y^2+2yf(y)}+1\]
Dette impliserer $y^2f(x)^2\geq -y^2+2yf(y)$ siden $x\geq 1$. Dermed er $(f(x)^2+1)y\geq 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\neq 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 [tex]n \in \mathbb{N}[/tex], 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 [tex]2^{k-1}[/tex] 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:
[tex]a^b b^c = c^a[/tex]
Der a,b,c er positive heltall, vis at:
(i) en hver primdivisor av a deler b.
(ii) Løs likningen under antagelsen [tex]b \geq a[/tex]
(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))\geqslant v_p(a)$, men siden $b$ ikke har noen faktor av $p$, får vi at $v_p(v_p(a))\geqslant v_p(a)$ som er en motstigelse.
for (ii) har vi da at $a^{a+c}\leqslant c^a$ la $x=c/a$, da får vi at $a^{ax}\leqslant 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.