Abel maraton

[lfe]

Løsning:

1) Påstand: $f(1)=1$
Bevis:
Anta for motsigelsens skyld at $f(1)>1$. Det betyr at 1 deler kun ett ab tallene $f(m+1)\dots f(m+f(1))$, en motsigelse siden 1 deler alle heltall.

2) Påstand: For alle $n$ eksisterer det et heltall $a_n$ slik at $n\mid f(x)\iff x\equiv a_n(\mathrm{mod}f(n))$.
Bevis:
Vi viser at $x\equiv a(\mathrm{mod}f(n))⟹n\mid f(x)$ med induksjon:
La $a$ være det minste heltallet slik at $n\mid f(a)$. Anta at $n\mid f(a+k\cdot f(n))$. Hvis vi ser på når $m=a-1+k\cdot f(n)$ og $m=a+k\cdot f(n)$ får vi at $n\mid f(a+(k+1)\cdot f(n))$.
$x\not\equiv a(\mathrm{mod}f(n))⟹n\nmid f(n)$ følger åpenbart. Dermed er påstanden bevist.


3)Påstand: $d\mid n⟹f(d)\mid f(n)$
Bevis:
La $d$ og $n$ være to heltall slik at $d\mid n$. Av 2) vet vi at $a_n+k\cdot f(n)\equiv a_d(\mathrm{mod}f(d)),\mathrm{\forall }k\in \mathbb{N}$ siden $n\mid f(a_n+k\cdot f(n))$. Dette impliserer at $f(d)\mid f(n)$

4) Påstand: $n\mid f(x)\iff f(n)\mid x$
Bevis:
Av 2) vet vi at $n\mid f(x)\iff x\equiv a_n(\mathrm{mod}f(n))$. 3) impliserer at $n\mid f(2a_n)$. Dermed er $2a_n\equiv a_n(\mathrm{mod}f(n))$. Det betyr at $f(n)\mid a_n$ og påstanden er bevist.

5) Påstand: $f(f(n))=n$
Bevis:
Vi ser at $f(f(n))\le n$ fordi det ikke kan være flere multipler av $n$ i intervallet $[m+1,m+f(f(n))]$ siden $f(n)\mid f(kn)$ (av 3)). Av 4) har vi at $n\mid f(f(n))$. Dermed er $f(f(n))=n$.

6) Påstand: Dersom $p$ er et primtall, så er $f(p)=q$, der $q$ også er et primtall.
Bevis:
Av 5) må $f$ være bijektiv. $f(x)=1$ har derfor kun løsningen $x=1$. Anta for motsigelsens skyld at $f(p)=uv$, der $u,v>1$. Av 4) vet at $f(u)\mid p$ og $f(v)\mid p$, en motsigelse. Påstanden er dermed bevist.

7) Påstand: Dersom $f(p)=q\ne p$, så er $f(pq)=pq$.
Bevis:
Vi vet at $f(q)=p$. Av 4) har vi at $f(p)\mid pq$ og $f(q)\mid pq$ impliserer at $pq\mid f(pq)$. Videre får vi dermed av 4) at $pq\mid f(pq)⟹f(pq)\mid pq$. Påstanden er vist.

7) løser oppgaven.

[lfe]

Ny oppgave:
La $P\in \mathbb{Z}[x]$, der $degP=n>1$. La $k$ være et positivt heltall. La $Q(x)=P^k(x)$. Vis at $Q(x)$ maks har $n$ fikspunkter.

[Lil_Flip38]

Jeg gjør antagelsen at det skal være HELTALLIGE fikspunkter.
Anta $Q$ har mer enn $n$ fikspunkter. La $n+1$ av disse være $a_0,....,a_n$
Påstand 1: $|P(a_i)-P(a_j)|=|a_i-a_j|$
Vi ser at $a_i-a_j|P(a_i)-P(a_j)|Q(a_i)-Q(a_j)=a_i-a_j$. Siden $Q$ er et polynom i $P$
Påstand 2: $P(a_i)-P(a_j)=a_i-a_j$ eller $P(a_i)-P(a_j)=a_j-a_i$ for alle $i,j$.
Dette følger av å se på 3 sykliske cases av påstand 1 med $(i,j,k)$ og anta at de ikke alle er like. Når man summer de 3 følger resultatet greit. Jeg dropper utregningen med tanke på at jeg skriver på telefon.
Av påstand 2 følger det at enten $P(a_i)-a_i=c$ eller $P(a_i)+a_i=c$. For alle $i$. Problemet oppstår når $P(x)-x-c$ eller $P(x)+x-c$bare er i grad $n$, men det har minst $n+1$ røtter siden $a_i$ vil alltid være en rot, og det er $n+1$ av de, og et polynom med grad $n$ har maks $n$ røtter, og å trekke fra $x$ endrer ikke på graden.

[Lil_Flip38]

Ny oppgave:
La $\mathcal{P}\{S\}$ være mengden av alle delmengder av en mengde $S$
La $f:\mathcal{P}\{S\}\to \mathcal{P}\{S\}$ være en økende funksjon. Det vil si at
$x\subseteq y\Rightarrow f(x)\subseteq f(y)$ vis at det eksisterer $T\in \mathcal{P}\{S\}$ slik at $f(T)=T$

[xor]

Hype oppgave da

[CCPenguin]

Texeditor vil ikk laste så blir stygt
la A <= B betegne at A er en delmengde av B
observer først at hvis f(ø) = ø, er vi ferdige, anta derfor videre f(ø) != ø

La X være mengden av alle A slik at A <= f(A)
denne mengden er åpenbart ikketom siden ø <= f(ø)
la B være unionen av alle elementene i X. B er åpenbart største element i X, siden det er unionen av alle elementene.
Vi ser videre at B <= f(B).
dermed vil også f(B) <= f(f(B))
dette betyr at f(B) er et element i X.
Siden B er største element i X, og B <= f(B), må B=f(B)

[CCPenguin]

Ny Oppgave:
Ta for deg et 2024 x 2024 rutenett.
To ruter er ved siden av hverandre om de deler en side.
En fargelegging av rutenettet i rødt og violett kalles "hvit hest" hvis hver rute i rutenettet er ved siden av et partall antall violette ruter.
Hvor mange "hvit hest" fargelegginger finnes?

[TorsteinBM]

svar: $2^{2024}$

først observerer vi at hvis vi fargelegger rutenettet i en sjakk-fargelegging påvirker hvit og svart ikke hverandre så vi kan finne svaret på en av fargene og ta det i andre siden vi jobber med partall rutenett
så fra nå av snakker jeg om hvite ruter

definer hvit hest fargelegging som HH

lemma 1: kantene i en HH fargelegging er symmetrisk over diagonalene
bevis: hvis vi velger en rute langs kanten og fargelegger den violett er den del av to 3-ere det vil si plasser hvis 3 og bare 3 ruter er ved siden av én rute dette betyr at det må være én violett bandt de andre i 3-eren men de to er og del av en 4-er hvor derfor de andre to rutene må ha én violett og dette fortsetter helt til vi kommer til enden hvor vi har at 2 av rutene i en 3-er har én violett så den tredje må også være violett og siden prosessen beveger seg normalt på diagonalen den krysser blir det en speiling.

lemma 2: hvis vi har definert kantene i en fargelegging slik at de oppfyller lemma 1 fins det bare én HH fargelegging
bevis: siden vi har definert alle kantene og ingen av disse er deler av 4-ere men bare 3-ere eller 2-ere hvor 2 av rutene allerede er definert og at de tilsammen nabo med alle som er ett hakk inn blir alle disse definert og denne prosessen fortsetter bare at nå har vi 4-ere hvor 3 er definert men det fungerer på helt samme måte. og dette kan vi gjøre helt inn til midten så hele er definert.

claim 1: hele rutenettet er definert ved én kant
bevis: dette er bare å kombinere lemma 1 og 2 så vi får at 1012 kan definere rutenettet

claim 2: vi kan ikke definere hele rutenettet med 1011 eller ferre farger
bevis: ved å bruke lemma 1 over begge diagonalene får vi at vi bare trenger å vise at hvis vi har en trekant med grunnflate og høyde 1012
bilde med høyde og grunnflate 3:

Skjermbilde 2024-08-01 122145.png (2.81 KiB) Viewed 49143 times

lemma 3: toppen av trekanten vil være definert av alle langs kanten
bevis definer violett som 1 og rød som 0
først observerer vi at hvis vi har definert alle unntatt en rute rundt en rute blir den siste xor av de tidligere og xor er komuttativt og (a xor a) = 0
så hvis vi har 3 av fire rundt en rute hvor de er (a xor b), b, (b xor c) ender vi opp med at den siste blir (a xor b xor c) dette er akuratt det som skjer i trekanten vår og dette fortsetter oppover hele som betyr at toppen er xor av alle rutene

dette gjør ferdig bevist for claim 2 så vi har at for hvit er det $2^{1012}$ så vi har at svaret er $2^{2024}$

[TorsteinBM]

La $P(n)$ være den største primdivisoren til $n$. finn alle $n\ge 2$ slik at

$P(n)+\lfloor \sqrt{n}\rfloor =P(n+1)+\lfloor \sqrt{n+1}\rfloor$

[CCPenguin]

Hvis [sqrt(n+1)] er en større, må P(n+1)være en mindre, som betyr at p(n+1) =2, p(n)=3
Hvis de er like er p(n+1)=p(n) som er umulig
Da får vi n+1=2^k, n=3^m *2^r
Åpenbart må da r=0, siden begge ikke er partall
Da er 1+3^k=2^c
Av catalan har dette ingen løsninger
Untatt k=1, c=2
Som gir n=3 som løsning

[CCPenguin]

Ny oppgave;
La $c>0$ være et reelt tall
Finn alle funksjoner $f:{\mathbb{R}}_{+}\to {\mathbb{R}}_{+}$
Slik at
$f((c+1)x+f(y))=f(x+2y)+2cx$
For alle $x,y\in {\mathbb{R}}_{+}$

[lfe]

Den eneste løsningen er $f(x)=2x$
Bevis:
La $P(x,y)$ være likningen gitt i oppgaven.

Påstand: $f(x)\ge 2x$
Bevis:
Anta for motsigelsens skyld at det eksisterer en $y\in {\mathbb{R}}_{+}$ slik at $f(y)<2y$.
Dette impliserer at $2y-f(y)\in {\mathbb{R}}_{+}$. Dermed har vi av $P(\frac{2y-f(y)}{c},y)$ at $$f(\frac{2y-f(y)}{c}+2y)=f(\frac{2y-f(y)}{c}+2y)+2(2y-f(y))$$, en motsigelse.

La $d(x)=f(x)-2x\ge 0$. Vi ønsker å vise at $d(x)=0$.
Likningen i oppgaven gir oss $d((c+1)x+d(y)+2y)+2d(y)=d(x+2y)$. Dermed er $d(a)\ge 2d(b)\ge d(b)$ for alle $a>2b$.

Påstand: $d(x)=0,\mathrm{\forall }x\in {\mathbb{R}}_{+}$
Bevis:
Anta for motsigelsens skyld at det eksisterer $z\in {\mathbb{R}}_{+}$ slik at $d(z)>0$.
Det følger at $d(f(z)+(c+1)x)<d(2z+x)$ for alle $x$.
La $n$ være et naturlig tall slik at $(c+1{)}^n>2$. Vi har at $d(kf(z)+x)<d(2z+\frac{(k-1)f(z)}{c+1}+\frac{x}{c+1})$.
For store nok $k$ kan vi repetere denne ulikheten til at vi får $d(kf(z)+x)<d(L+\frac{x}{(c+1{)}^n})$.
Dette er en motsigelse fordi for stor nok $x$ er $kf(z)+x>2(L+\frac{x}{c+1^n})$, der L er en konstant.
Dermed er $d(x)=0$ for alle $x$, som impliserer at $f(x)=2x$.

[lfe]

La $F_n$ være det n-te fibonaccitallet, der $F_1=F_2=1$. Finn alle $(x,y)$ slik at $5F_x-3F_y=1$.

[CCPenguin]

Oppgave: finn alle par $(x,y)$, slik at $5F_x-3F_y=1$.
(5,6), (3,4),(6,7) er det eneste som går:
Dette funker åpenbart siden $5\ast 5-3\ast 8=25-24=1$
$5\ast 8-3\ast 13=40-39=1$, så (6,7) går
$10-9=1$, så (3,4) går
Anta først x = 1,
Da får vi $3F_y=4$, som er umulig
Bevis:
Lemma 1: for x>1 $F_{x+2}>2\ast F_x$
Bevis lemma 1:
Åpenbart erfibonaccitallene en strengt økende følge untatt for $F_1\to F_2$
Siden $F_{x+2}=F_{x+1}+F_x$, og $F_{x+1}>F_x$, følger det.
åpenbart vil dette også gjelde for alle $y>=x+2$
Lemma 2: y = x+1
Bevis lemma 2:
Anta først $y<=x$
Da vil $5F_x-3F_y>=2F_x>=2$, som åpenbart er umulig siden utrykket er lik 1
Anta y > x+1, x >1 og $5F_x=1+3F_y$. Av lemma 1:
$5F_x=1+3F_y>1+6F_x$, som åpenbart er en motsigelse.
Dermed er y = x+1
Vi kan nå fullføre oppgaven
Siden $F_{x+1}=F_{x-1}+F_x$ får vi
$5F_x-3F_x-3F_{x-1}=1$.
$2F_x-3F_{x-1}=1$, og ved å bruke samme substitusjon for $F_x$
$2F_{x-1}+2F_{x-2}-3F_{x-1}=1$
$2F_{x-2}-F_{x-1}=1$, og ved samme substitusjon igjen:
$F_{x-2}=1+F_{x-3}$
dette går åpenbart bare når $F_{x-2}=2$, som impliserer $x-2=3,x=5,y=6$
Eller når $F_{x-2}=3$
Da er x-2=4, x=6
$x=6,y=7$,
Den andre muligheten er når $x-3<1,x<4$
x=3, y=4 har vi vist går
x=2 gir 5*1-2*3=-1, som ikke går

[CCPenguin]

Finn alle funksjoner $f:\mathbb{N}\to \mathbb{N}$ slik at for alle $m,n\in \mathbb{N}$ vil følgende likhet holde:
$(2^m+1)f(n)f(2^{m}n)=2^{m}f(n{)}^2+f(2^{m}n{)}^2+(2^m-1{)}^{2}n$