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) \Leftrightarrow x\equiv a_n \pmod{f(n)}$.
Bevis:
Vi viser at $x\equiv a\pmod{f(n)} \implies 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 \pmod{f(n)} \implies n \nmid f(n)$ følger åpenbart. Dermed er påstanden bevist.
3)Påstand: $d \mid n \implies 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 \pmod{f(d)}, \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) \Leftrightarrow f(n)\mid x$
Bevis:
Av 2) vet vi at $n\mid f(x) \Leftrightarrow x\equiv a_n \pmod{f(n)}$. 3) impliserer at $n\mid f(2a_n)$. Dermed er $2a_n\equiv a_n \pmod{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))\leq 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\neq 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) \implies f(pq)\mid pq$. Påstanden er vist.
7) løser oppgaven.
Abel maraton
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
Lil_Flip38
- Noether
- Innlegg: 35
- Registrert: 10/12-2023 10:58
- Sted: Abelmaraton
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.
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.
Sist redigert av Lil_Flip38 den 30/07-2024 10:47, redigert 4 ganger totalt.
-
Lil_Flip38
- Noether
- Innlegg: 35
- Registrert: 10/12-2023 10:58
- Sted: Abelmaraton
Ny oppgave:
La $\mathcal{P}\{S\}$ være mengden av alle delmengder av en mengde $S$
La $f: \mathcal{P}\{S\} \rightarrow \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$
La $\mathcal{P}\{S\}$ være mengden av alle delmengder av en mengde $S$
La $f: \mathcal{P}\{S\} \rightarrow \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$
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)
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)
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?
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
- Noether
- Innlegg: 20
- Registrert: 13/12-2023 07:55
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:
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}$
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) Vist 7873 ganger
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
- Noether
- Innlegg: 20
- Registrert: 13/12-2023 07:55
La $P(n)$ være den største primdivisoren til $n$. finn alle $n \geq 2$ slik at
$P(n) + \lfloor \sqrt{n} \rfloor = P(n+1) + \lfloor \sqrt{n+1} \rfloor$
$P(n) + \lfloor \sqrt{n} \rfloor = P(n+1) + \lfloor \sqrt{n+1} \rfloor$
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
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
Den eneste løsningen er $f(x)=2x$
Bevis:
La $P(x,y)$ være likningen gitt i oppgaven.
Påstand: $f(x)\geq 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\geq 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)\geq 2d(b)\geq d(b)$ for alle $a>2b$.
Påstand: $d(x)=0,\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$.
Bevis:
La $P(x,y)$ være likningen gitt i oppgaven.
Påstand: $f(x)\geq 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\geq 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)\geq 2d(b)\geq d(b)$ for alle $a>2b$.
Påstand: $d(x)=0,\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$.
Sist redigert av lfe den 05/08-2024 22:15, redigert 2 ganger totalt.
Oppgave: finn alle par [tex](x,y) [/tex], slik at [tex]5 F_x -3 F_y = 1[/tex].
(5,6), (3,4),(6,7) er det eneste som går:
Dette funker åpenbart siden [tex]5*5-3*8 = 25-24 = 1[/tex]
[tex]5*8-3*13=40-39=1[/tex], så (6,7) går
[tex]10-9=1[/tex], så (3,4) går
Anta først x = 1,
Da får vi [tex]3 F_y =4[/tex], som er umulig
Bevis:
Lemma 1: for x>1 [tex]F_{x+2} > 2* F_{x} [/tex]
Bevis lemma 1:
Åpenbart erfibonaccitallene en strengt økende følge untatt for [tex]F_1 \rightarrow F_2[/tex]
Siden [tex]F_{x+2} = F_{x+1}+F_{x}[/tex], og [tex] F_{x+1}>F_{x}[/tex], følger det.
åpenbart vil dette også gjelde for alle [tex]y >= x+2[/tex]
Lemma 2: y = x+1
Bevis lemma 2:
Anta først [tex]y<=x[/tex]
Da vil [tex]5 F_x - 3 F_y >=2 F_x >= 2[/tex], som åpenbart er umulig siden utrykket er lik 1
Anta y > x+1, x >1 og [tex]5 F_x=1+3 F_y [/tex]. Av lemma 1:
[tex]5 F_x=1+3 F_y > 1+6 F_x[/tex], som åpenbart er en motsigelse.
Dermed er y = x+1
Vi kan nå fullføre oppgaven
Siden [tex]F_{x+1} = F_{x-1} + F_x[/tex] får vi
[tex]5 F_x -3 F_x - 3 F_{x-1} = 1[/tex].
[tex]2F_x - 3 F_{x-1} = 1[/tex], og ved å bruke samme substitusjon for [tex]F_x[/tex]
[tex]2F_{x-1}+2F_{x-2} - 3 F_{x-1} = 1[/tex]
[tex]2 F_{x-2} -F_{x-1} = 1[/tex], og ved samme substitusjon igjen:
[tex]F_{x-2} = 1+F_{x-3}[/tex]
dette går åpenbart bare når [tex]F_{x-2} = 2[/tex], som impliserer [tex]x-2 = 3, x = 5, y = 6[/tex]
Eller når [tex]F_{x-2}= 3[/tex]
Da er x-2=4, x=6
[tex]x=6, y=7[/tex],
Den andre muligheten er når [tex]x-3<1, x<4[/tex]
x=3, y=4 har vi vist går
x=2 gir 5*1-2*3=-1, som ikke går
(5,6), (3,4),(6,7) er det eneste som går:
Dette funker åpenbart siden [tex]5*5-3*8 = 25-24 = 1[/tex]
[tex]5*8-3*13=40-39=1[/tex], så (6,7) går
[tex]10-9=1[/tex], så (3,4) går
Anta først x = 1,
Da får vi [tex]3 F_y =4[/tex], som er umulig
Bevis:
Lemma 1: for x>1 [tex]F_{x+2} > 2* F_{x} [/tex]
Bevis lemma 1:
Åpenbart erfibonaccitallene en strengt økende følge untatt for [tex]F_1 \rightarrow F_2[/tex]
Siden [tex]F_{x+2} = F_{x+1}+F_{x}[/tex], og [tex] F_{x+1}>F_{x}[/tex], følger det.
åpenbart vil dette også gjelde for alle [tex]y >= x+2[/tex]
Lemma 2: y = x+1
Bevis lemma 2:
Anta først [tex]y<=x[/tex]
Da vil [tex]5 F_x - 3 F_y >=2 F_x >= 2[/tex], som åpenbart er umulig siden utrykket er lik 1
Anta y > x+1, x >1 og [tex]5 F_x=1+3 F_y [/tex]. Av lemma 1:
[tex]5 F_x=1+3 F_y > 1+6 F_x[/tex], som åpenbart er en motsigelse.
Dermed er y = x+1
Vi kan nå fullføre oppgaven
Siden [tex]F_{x+1} = F_{x-1} + F_x[/tex] får vi
[tex]5 F_x -3 F_x - 3 F_{x-1} = 1[/tex].
[tex]2F_x - 3 F_{x-1} = 1[/tex], og ved å bruke samme substitusjon for [tex]F_x[/tex]
[tex]2F_{x-1}+2F_{x-2} - 3 F_{x-1} = 1[/tex]
[tex]2 F_{x-2} -F_{x-1} = 1[/tex], og ved samme substitusjon igjen:
[tex]F_{x-2} = 1+F_{x-3}[/tex]
dette går åpenbart bare når [tex]F_{x-2} = 2[/tex], som impliserer [tex]x-2 = 3, x = 5, y = 6[/tex]
Eller når [tex]F_{x-2}= 3[/tex]
Da er x-2=4, x=6
[tex]x=6, y=7[/tex],
Den andre muligheten er når [tex]x-3<1, x<4[/tex]
x=3, y=4 har vi vist går
x=2 gir 5*1-2*3=-1, som ikke går
Sist redigert av CCPenguin den 06/08-2024 14:55, redigert 1 gang totalt.