Løsning:
La [tex]\omega[/tex] være omsirkelen til ABC. La [tex]X=\omega \cap CD[/tex] og [tex]Y=\omega \cap BE[/tex].
Påstand: XFLY er syklisk
Bevis:
Følger av konversen til Reims teorem på FL, BC og [tex]\omega[/tex].
Påstand: XDAI og YPAE er syklisk
Bevis:
Det følger av vinkeljakt:
[tex]\measuredangle DIA=\measuredangle CBA =\measuredangle CXA =\measuredangle DXA[/tex]
Dermed er XDAI syklisk. (YPAE) følger av liknende vinkeljakt.
Påstand: XFLYPI er syklisk
Bevis:
Følger av vinkeljakt:
[tex]\measuredangle XID =\measuredangle XAD =\measuredangle XAB =\measuredangle XCB =\measuredangle XLF[/tex]
Dermed er XFLYI syklisk. Av liknende vinkeljakt får vi at P også ligger på XFLY.
Abel maraton
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Ny oppgave:
For hvert par av heltall (i,j) velger vi et punkt [tex]P_{i,j}=(x,y)[/tex] på det kartesiske planet slik at [tex]i<x<i+1[/tex] og [tex]j<y<j+1[/tex]. Finn alle reelle tall [tex]c>0[/tex] slik at firkanten [tex]P_{i,j}P_{i+1,j}P_{i+1,j+1}P_{i,j+1}[/tex] har omkrets mindre enn c for alle heltall i og j.
For hvert par av heltall (i,j) velger vi et punkt [tex]P_{i,j}=(x,y)[/tex] på det kartesiske planet slik at [tex]i<x<i+1[/tex] og [tex]j<y<j+1[/tex]. Finn alle reelle tall [tex]c>0[/tex] slik at firkanten [tex]P_{i,j}P_{i+1,j}P_{i+1,j+1}P_{i,j+1}[/tex] har omkrets mindre enn c for alle heltall i og j.
-
TorsteinBM
- Noether
- Innlegg: 33
- Registrert: 13/12-2023 07:55
Svar c>=4
Påstand 1, c = 4 er en mulig c
Bevis
Hvis vi plasserer punktet i P(i, j) i [tex](0.5-sign(i)*\sum_{k=1}^{|i|}\frac{1}{4^i}, 0.5-sign(j)*\sum_{k=1}^{|j|}\frac{1}{4^j})[/tex]
Får vi at distansen er omkretsen går mot 4 så c = 4 er mulig
Påstand 2, c < 4 er ikke mulig
Bevis:
Hvis vi fixer en c under 4 kan vi gjøre følgende
Hvis vi velger (n+2)×(n+2)ruter vil gjennomsnittsarealet være mer enn n^2/(n+1)^2 fordi vi kan fjærne mindre enn 1 fra venstre og høyre og samme med topp og bunn så minimum sum av arealet blir over n^2 og antall firkanter er (n+1)^2 vi vet at den beste firkanten som gir mest areal per omkrets er kvadratet så hvis vi lar n gå mot uendelig får vi at omkretsen går mot 4 og vi kan tvinge den over c
Påstand 1, c = 4 er en mulig c
Bevis
Hvis vi plasserer punktet i P(i, j) i [tex](0.5-sign(i)*\sum_{k=1}^{|i|}\frac{1}{4^i}, 0.5-sign(j)*\sum_{k=1}^{|j|}\frac{1}{4^j})[/tex]
Får vi at distansen er omkretsen går mot 4 så c = 4 er mulig
Påstand 2, c < 4 er ikke mulig
Bevis:
Hvis vi fixer en c under 4 kan vi gjøre følgende
Hvis vi velger (n+2)×(n+2)ruter vil gjennomsnittsarealet være mer enn n^2/(n+1)^2 fordi vi kan fjærne mindre enn 1 fra venstre og høyre og samme med topp og bunn så minimum sum av arealet blir over n^2 og antall firkanter er (n+1)^2 vi vet at den beste firkanten som gir mest areal per omkrets er kvadratet så hvis vi lar n gå mot uendelig får vi at omkretsen går mot 4 og vi kan tvinge den over c
-
TorsteinBM
- Noether
- Innlegg: 33
- Registrert: 13/12-2023 07:55
La N være et positivt heltall. En samling av 4N^2 enhetsfliser med to segmenter tegnet på dem som vist i bildet under, settes sammen til et 2N ganger 2N bord.
Fliser kan roteres. Segmentene på flisene definerer stier på brettet. Bestem minst mulig antall og størst mulig antall slike stier.
- Screenshot_20240718-163831_ibisPaint X.jpg (33.21 kiB) Vist 24105 ganger
-
Lil_Flip38
- Noether
- Innlegg: 40
- Registrert: 10/12-2023 10:58
- Sted: Abelmaraton
Svar: $4N, 2N^2+2N+1$
Vi viser først minimum. Hvis vi roterer flisene slik at stiene blir linjer parallel med diagonalen, ser vi lett at det er $4N$ stier.
Observer at det er $8N$ punkter på kanten som må alle være med i en sti, og en sti inneholder maks $2$ punkter på kanten. Dette impliserer at det er minst $4N$ stier.
Nå viser vi maks. Vi klassifiserer stier inn i to typer: stier som treffer kanten, eller en sti som er en sykel. Kall antall vi har av hver av disse a, b. Vi har følgene konstruksjon: hjørnene blir til en sti av lengde 1, rundt kanten blir det trekanter av lengde 2, og i midten blir det sykler av lengde 4. Ved å gjøre litt utregning får vi $2N^2+2N+1$ sykler.
Til sammen har vi $2*4N^2$ segmenter. Segmentet i hjørnene har muligheten til å være i en sykel av lengde 1. de på siden må være med i en sti med lengde minst 2. en sykel inni har minst lengde 4. Da får vi ulikheten $8N^2>=4b+2(a-4)+4$. Nå ser av minimum beviset vårt at $a=4N$. Da følger det greit av utregning at $b<=2N^2-2N+2$. Antall stier er jo da $a+b$, som impliserer resultatet vi så etter. Da er vi ferdige.
Vi viser først minimum. Hvis vi roterer flisene slik at stiene blir linjer parallel med diagonalen, ser vi lett at det er $4N$ stier.
Observer at det er $8N$ punkter på kanten som må alle være med i en sti, og en sti inneholder maks $2$ punkter på kanten. Dette impliserer at det er minst $4N$ stier.
Nå viser vi maks. Vi klassifiserer stier inn i to typer: stier som treffer kanten, eller en sti som er en sykel. Kall antall vi har av hver av disse a, b. Vi har følgene konstruksjon: hjørnene blir til en sti av lengde 1, rundt kanten blir det trekanter av lengde 2, og i midten blir det sykler av lengde 4. Ved å gjøre litt utregning får vi $2N^2+2N+1$ sykler.
Til sammen har vi $2*4N^2$ segmenter. Segmentet i hjørnene har muligheten til å være i en sykel av lengde 1. de på siden må være med i en sti med lengde minst 2. en sykel inni har minst lengde 4. Da får vi ulikheten $8N^2>=4b+2(a-4)+4$. Nå ser av minimum beviset vårt at $a=4N$. Da følger det greit av utregning at $b<=2N^2-2N+2$. Antall stier er jo da $a+b$, som impliserer resultatet vi så etter. Da er vi ferdige.
-
Lil_Flip38
- Noether
- Innlegg: 40
- Registrert: 10/12-2023 10:58
- Sted: Abelmaraton
Ny oppgave: kan være litt tøft til tider. Definitivt ikke G6 på shortlist.
La [tex]ABC[/tex] være en spissvinklet trekant med omsirkel [tex]\omega[/tex]. En sirkel [tex]\Omega[/tex] er tangent til [tex]\omega[/tex] i [tex]A[/tex] og [tex]BC[/tex] i [tex]D[/tex]. La [tex]AB, AC[/tex] skjære [tex]\Omega[/tex] i [tex]P,Q[/tex]. La [tex]M,N[/tex] være refleksjonene av $D$ over [tex]B,C[/tex]. Linjene [tex]MP,NQ[/tex] skjærer i [tex]K[/tex] og skjærer [tex]\Omega[/tex] igjen i [tex]I,J[/tex]. La strålen [tex]KA[/tex] skjære sirkelen gjennom [tex]I,J,K[/tex] igjen i $X$. Vis at linjene [tex]XP,XQ[/tex] er isogonale i [tex]\angle BXC[/tex].
(Isogonal betyr at de er symmetriske om vinkelhalveringslinja)
La [tex]ABC[/tex] være en spissvinklet trekant med omsirkel [tex]\omega[/tex]. En sirkel [tex]\Omega[/tex] er tangent til [tex]\omega[/tex] i [tex]A[/tex] og [tex]BC[/tex] i [tex]D[/tex]. La [tex]AB, AC[/tex] skjære [tex]\Omega[/tex] i [tex]P,Q[/tex]. La [tex]M,N[/tex] være refleksjonene av $D$ over [tex]B,C[/tex]. Linjene [tex]MP,NQ[/tex] skjærer i [tex]K[/tex] og skjærer [tex]\Omega[/tex] igjen i [tex]I,J[/tex]. La strålen [tex]KA[/tex] skjære sirkelen gjennom [tex]I,J,K[/tex] igjen i $X$. Vis at linjene [tex]XP,XQ[/tex] er isogonale i [tex]\angle BXC[/tex].
(Isogonal betyr at de er symmetriske om vinkelhalveringslinja)
Løsning:
1) Påstand: [tex]PQ\parallel BC[/tex]
Bevis:
Vinkeljakt: [tex]\measuredangle ACB =-\measuredangle CDQ -\measuredangle DQC=-\measuredangle PAD+\measuredangle AQD=\measuredangle AQD -\measuredangle PQD=\measuredangle AQP[/tex]
Dette impliserer påstanden siden A, Q og C er kollineære.
2) Påstand: X, A, K og D er kollineære
Bevis:
Det holder å vise at K ligger på AD. La [tex]R=PQ \cap AD[/tex], [tex]K_1=AD \cap MP[/tex] og [tex]K_2=AD \cap NQ[/tex].
Vi vet at [tex]-1=(M,D;B,\infty )=(N,D;C,\infty )[/tex].
Av 1) har vi:
[tex](M,D;B,\infty )\stackrel{P}\doublebarwedge (K_1,D;A,R)[/tex]
[tex](N,D;C,\infty )\stackrel{P}\doublebarwedge (K_2,D;A,R)[/tex]
Dermed får vi [tex]K_1=K_2=K[/tex].
Det betyr at K ligger på AD.
3) Påstand: (MDIX) og (NDJX)
Bevis:
Følger av vinkeljakt:
[tex]\measuredangle DBI =\measuredangle QPI =\measuredangle QJI =\measuredangle KJI =\measuredangle KXI =\measuredangle DXI[/tex]
I vinkeljakten bruker vi 1), 2), JKIX syklisk og QPJI syklisk.
Dermed er MDIX syklisk. En identisk vinkeljakt gir oss også NDJX syklisk.
4) Påstand: [tex]XMN\sim ABC[/tex]
Bevis:
Det holder å vise at [tex]AB \parallel XM[/tex] og [tex]AC \parallel XN[/tex].
Vinkeljakt der vi bruker 3):
[tex]\measuredangle MXD = \measuredangle BID =\measuredangle PID =\measuredangle PAD[/tex].
Av 2) er dermed [tex]AB \parallel XM[/tex].
Liknende bevis gir [tex]AC \parallel XN[/tex]
5) Påstand: (BDQX) og (CDPX)
Av symmetri holder det å vise at BDQX er syklisk. Vi viser påstanden med formlike trekanter.
[tex]\measuredangle BAD =\measuredangle DAQ[/tex]
[tex]\measuredangle QDA=\measuredangle QPA =\measuredangle DBA[/tex]
Dette impliserer at [tex]ABD\sim ADQ[/tex]. Vi har dermed at [tex]\frac{AD}{BD}=\frac{AQ}{DQ}[/tex].
Videre har vi:
[tex]\measuredangle QDB =\measuredangle QDC =\measuredangle QAD =\measuredangle QAX[/tex].
[tex]\frac{AX}{BD}=\frac{AB}{BD}=\frac{AQ}{DQ}[/tex]
Det betyr at [tex]BDQ\sim XAQ[/tex] og påstanden følger siden [tex]\measuredangle DBQ =\measuredangle AXQ=\measuredangle DXQ[/tex].
Av 5) har vi at [tex]\measuredangle BXQ=\measuredangle BDQ =\measuredangle CDQ =\measuredangle DAQ=\measuredangle PAD=\measuredangle PDB=\measuredangle PDC =\measuredangle PXC[/tex]. Dermed er XP og XQ isogonalkonjugater i [tex]\angle BXC[/tex].
1) Påstand: [tex]PQ\parallel BC[/tex]
Bevis:
Vinkeljakt: [tex]\measuredangle ACB =-\measuredangle CDQ -\measuredangle DQC=-\measuredangle PAD+\measuredangle AQD=\measuredangle AQD -\measuredangle PQD=\measuredangle AQP[/tex]
Dette impliserer påstanden siden A, Q og C er kollineære.
2) Påstand: X, A, K og D er kollineære
Bevis:
Det holder å vise at K ligger på AD. La [tex]R=PQ \cap AD[/tex], [tex]K_1=AD \cap MP[/tex] og [tex]K_2=AD \cap NQ[/tex].
Vi vet at [tex]-1=(M,D;B,\infty )=(N,D;C,\infty )[/tex].
Av 1) har vi:
[tex](M,D;B,\infty )\stackrel{P}\doublebarwedge (K_1,D;A,R)[/tex]
[tex](N,D;C,\infty )\stackrel{P}\doublebarwedge (K_2,D;A,R)[/tex]
Dermed får vi [tex]K_1=K_2=K[/tex].
Det betyr at K ligger på AD.
3) Påstand: (MDIX) og (NDJX)
Bevis:
Følger av vinkeljakt:
[tex]\measuredangle DBI =\measuredangle QPI =\measuredangle QJI =\measuredangle KJI =\measuredangle KXI =\measuredangle DXI[/tex]
I vinkeljakten bruker vi 1), 2), JKIX syklisk og QPJI syklisk.
Dermed er MDIX syklisk. En identisk vinkeljakt gir oss også NDJX syklisk.
4) Påstand: [tex]XMN\sim ABC[/tex]
Bevis:
Det holder å vise at [tex]AB \parallel XM[/tex] og [tex]AC \parallel XN[/tex].
Vinkeljakt der vi bruker 3):
[tex]\measuredangle MXD = \measuredangle BID =\measuredangle PID =\measuredangle PAD[/tex].
Av 2) er dermed [tex]AB \parallel XM[/tex].
Liknende bevis gir [tex]AC \parallel XN[/tex]
5) Påstand: (BDQX) og (CDPX)
Av symmetri holder det å vise at BDQX er syklisk. Vi viser påstanden med formlike trekanter.
[tex]\measuredangle BAD =\measuredangle DAQ[/tex]
[tex]\measuredangle QDA=\measuredangle QPA =\measuredangle DBA[/tex]
Dette impliserer at [tex]ABD\sim ADQ[/tex]. Vi har dermed at [tex]\frac{AD}{BD}=\frac{AQ}{DQ}[/tex].
Videre har vi:
[tex]\measuredangle QDB =\measuredangle QDC =\measuredangle QAD =\measuredangle QAX[/tex].
[tex]\frac{AX}{BD}=\frac{AB}{BD}=\frac{AQ}{DQ}[/tex]
Det betyr at [tex]BDQ\sim XAQ[/tex] og påstanden følger siden [tex]\measuredangle DBQ =\measuredangle AXQ=\measuredangle DXQ[/tex].
Av 5) har vi at [tex]\measuredangle BXQ=\measuredangle BDQ =\measuredangle CDQ =\measuredangle DAQ=\measuredangle PAD=\measuredangle PDB=\measuredangle PDC =\measuredangle PXC[/tex]. Dermed er XP og XQ isogonalkonjugater i [tex]\angle BXC[/tex].
Ny oppgave:
La [tex]f_1,f_2,f_3:\mathbb{R}\rightarrow \mathbb{R}[/tex] være funksjoner slik at [tex]a_1f_1+a_2f_2+a_3f_3[/tex] er monoton for alle [tex]a_1,a_2,a_3\in \mathbb{R}[/tex]. Vis at det eksisterer tre tall [tex]c_1,c_2,c_2\in \mathbb{R}[/tex], der ikke alle er lik 0, slik at [tex]c_1f_1(x)+c_2f_2(x)+c_3f_3(x)=0[/tex], for alle [tex]x\in \mathbb{R}[/tex].
La [tex]f_1,f_2,f_3:\mathbb{R}\rightarrow \mathbb{R}[/tex] være funksjoner slik at [tex]a_1f_1+a_2f_2+a_3f_3[/tex] er monoton for alle [tex]a_1,a_2,a_3\in \mathbb{R}[/tex]. Vis at det eksisterer tre tall [tex]c_1,c_2,c_2\in \mathbb{R}[/tex], der ikke alle er lik 0, slik at [tex]c_1f_1(x)+c_2f_2(x)+c_3f_3(x)=0[/tex], for alle [tex]x\in \mathbb{R}[/tex].
Bevis:
WLOG la [tex]\alpha _1 = 1[/tex], siden alt kan skaleres.
WLOG anta at alle funksjonene er positvt monotone, siden fortegnet på [tex]\alpha_i[/tex] kan flippes
Hvis 2 av funksjonene er konstante kan vi velge konstanten foran den ikkekonstante funksjonen til å være null, også utjevne de 2 andre.
Anta først [tex]f_3(0) \neq 0, f_2(0) \neq 0, [/tex]
Anta videre at om en av funksjonene [tex]f_1, f_2, f_3[/tex] er konstante, er [tex]f_1 konstant[/tex]
Først, ser vi at om vi lar [tex]\alpha_3 = -\frac{\alpha_2 f_2(0)+f_1(0)}{f_3(0)} [/tex]
så vil [tex]f_1(0) + \alpha _2 f_2(0) + \alpha _3 f_3(0) = 0 \forall \alpha_2 \in \mathbb{R}[/tex]. Dermed vil
[tex]f_1(x)+\alpha_2 f_2(x) + -\frac{\alpha_2 f_2(0)+f_1(0)}{f_3(0)} f_3(x) [/tex]
Være en kontinuerlig funksjon i [tex]\alpha_2[/tex]
Vi har nå 2 cases:
1: det finnes [tex]\alpha_2 [/tex] slik at funksjonen er økende og det finnes [tex]\beta _2[/tex] der utrykket er synkende
Anta at [tex]\alpha_2 > \beta_2 [/tex], argumentet er tilsvarende ellers.
åpenbart vil funksjonen være økende for alle [tex]\alpha > \alpha2[/tex], og motsatt for [tex]\beta < \beta_2[/tex]
La nå [tex] x= \frac{\alpha_2- \beta_2}{2} [/tex]. Om utrykket er voksende i x, ser vi på det nedre intervallet [tex][\beta_2, x][/tex], og om den er synkende ser vi på [tex] [x, \alpha_2] [/tex]. ved å fortsette denne prosessen får vi en følge av intervaller der ved det største elementet er utrykket alltid voksende, og ved det minste er det alltid synkende. Dette vil lage en følge med nestede intervaller, og siden størrelsen av de nestede intervallene går mot null, vil det konvergere mot nøyaktig ett punkt i [tex]\mathbb{R}[/tex], der funksjonen er både voksende og synkende, dermed konstant. siden utrykket er 0 i x = 0, må den være konstant lik null
2: uavhengig av verdien til [tex]\alpha _2[/tex], har funksjonen samme monotonisitet
Den eneste måten dette kan skje på er enten at a2f2 og a2f3 utgjevner hverandre og blir konstante. Hvis ikke, kan vi øke eller synke a2 så mye slik at vi får et punkt der funksjonen øker eller synker mer en resten av utrykket, og monotonisiteten endres.
Om de utgjevner hverandre og blir konstante får vi at [tex]\alpha _2 f_2 (x) - \frac{\alpha_2 f_2(0)}{f_3(0)} f_3(x)[/tex] er konstant når x varieres.
Dette impliserer at [tex]f_2(x) = c f_3 (x) + k[/tex], for noen konstanter c, k.
Da kan det originale utrykket skrives som [tex] f_1(x) +( \alpha_2+\alpha_3) f_3 (x) +\alpha_2 k [/tex], som kan omformes til
[tex] f_1(x) +\alpha f_3 (x) +\alpha_2 k [/tex], for nye konstanter [tex]\alpha, \alpha_2[/tex]
som vil være monotont for ethvert valg av [tex]\alpha, \alpha_2[/tex]. om vi nå justerer [tex]\alpha [/tex] slik at [tex]f_1(x)+\alpha f_3(x)[/tex] er konstant (med samme strategi som i 1), kan vi justere [tex]\alpha_2[/tex] slik at utrykket blir null.
(om det ikke fines en slik [tex]\alpha[/tex], må funksjonen være konstant, da får vi 2 konstante funksjoner)
Anta nå [tex]f_3(0) = 0 [/tex] eller [tex] f_2(0) =0, [/tex]
Valget av x=0 er i utganspunktet irrelevant, ethvert fikspunkt fungerer. Dermed kan vi gå så langt vi vil mot høyre for å finne en x der to av funksjonene ikke er null, og kalle de funksjonene [tex]f_2, f_3[/tex]. hvis dette er umulig er 2 av funskjonene konstante, noe vi allerede har håndtert.
QED
WLOG la [tex]\alpha _1 = 1[/tex], siden alt kan skaleres.
WLOG anta at alle funksjonene er positvt monotone, siden fortegnet på [tex]\alpha_i[/tex] kan flippes
Hvis 2 av funksjonene er konstante kan vi velge konstanten foran den ikkekonstante funksjonen til å være null, også utjevne de 2 andre.
Anta først [tex]f_3(0) \neq 0, f_2(0) \neq 0, [/tex]
Anta videre at om en av funksjonene [tex]f_1, f_2, f_3[/tex] er konstante, er [tex]f_1 konstant[/tex]
Først, ser vi at om vi lar [tex]\alpha_3 = -\frac{\alpha_2 f_2(0)+f_1(0)}{f_3(0)} [/tex]
så vil [tex]f_1(0) + \alpha _2 f_2(0) + \alpha _3 f_3(0) = 0 \forall \alpha_2 \in \mathbb{R}[/tex]. Dermed vil
[tex]f_1(x)+\alpha_2 f_2(x) + -\frac{\alpha_2 f_2(0)+f_1(0)}{f_3(0)} f_3(x) [/tex]
Være en kontinuerlig funksjon i [tex]\alpha_2[/tex]
Vi har nå 2 cases:
1: det finnes [tex]\alpha_2 [/tex] slik at funksjonen er økende og det finnes [tex]\beta _2[/tex] der utrykket er synkende
Anta at [tex]\alpha_2 > \beta_2 [/tex], argumentet er tilsvarende ellers.
åpenbart vil funksjonen være økende for alle [tex]\alpha > \alpha2[/tex], og motsatt for [tex]\beta < \beta_2[/tex]
La nå [tex] x= \frac{\alpha_2- \beta_2}{2} [/tex]. Om utrykket er voksende i x, ser vi på det nedre intervallet [tex][\beta_2, x][/tex], og om den er synkende ser vi på [tex] [x, \alpha_2] [/tex]. ved å fortsette denne prosessen får vi en følge av intervaller der ved det største elementet er utrykket alltid voksende, og ved det minste er det alltid synkende. Dette vil lage en følge med nestede intervaller, og siden størrelsen av de nestede intervallene går mot null, vil det konvergere mot nøyaktig ett punkt i [tex]\mathbb{R}[/tex], der funksjonen er både voksende og synkende, dermed konstant. siden utrykket er 0 i x = 0, må den være konstant lik null
2: uavhengig av verdien til [tex]\alpha _2[/tex], har funksjonen samme monotonisitet
Den eneste måten dette kan skje på er enten at a2f2 og a2f3 utgjevner hverandre og blir konstante. Hvis ikke, kan vi øke eller synke a2 så mye slik at vi får et punkt der funksjonen øker eller synker mer en resten av utrykket, og monotonisiteten endres.
Om de utgjevner hverandre og blir konstante får vi at [tex]\alpha _2 f_2 (x) - \frac{\alpha_2 f_2(0)}{f_3(0)} f_3(x)[/tex] er konstant når x varieres.
Dette impliserer at [tex]f_2(x) = c f_3 (x) + k[/tex], for noen konstanter c, k.
Da kan det originale utrykket skrives som [tex] f_1(x) +( \alpha_2+\alpha_3) f_3 (x) +\alpha_2 k [/tex], som kan omformes til
[tex] f_1(x) +\alpha f_3 (x) +\alpha_2 k [/tex], for nye konstanter [tex]\alpha, \alpha_2[/tex]
som vil være monotont for ethvert valg av [tex]\alpha, \alpha_2[/tex]. om vi nå justerer [tex]\alpha [/tex] slik at [tex]f_1(x)+\alpha f_3(x)[/tex] er konstant (med samme strategi som i 1), kan vi justere [tex]\alpha_2[/tex] slik at utrykket blir null.
(om det ikke fines en slik [tex]\alpha[/tex], må funksjonen være konstant, da får vi 2 konstante funksjoner)
Anta nå [tex]f_3(0) = 0 [/tex] eller [tex] f_2(0) =0, [/tex]
Valget av x=0 er i utganspunktet irrelevant, ethvert fikspunkt fungerer. Dermed kan vi gå så langt vi vil mot høyre for å finne en x der to av funksjonene ikke er null, og kalle de funksjonene [tex]f_2, f_3[/tex]. hvis dette er umulig er 2 av funskjonene konstante, noe vi allerede har håndtert.
QED
Ny Oppgave:
la p>3 være et primtall slik at [tex]p\equiv 3 (mod 4)[/tex]
Gitt et positivt heltall [tex]a_0[/tex], definer følgen [tex]a_0, a_1, ....[/tex] ved å la
[tex]a_n = a_{n-1}^{2^n}[/tex] for alle [tex]n \geq 1[/tex]
Vis at man kan velge [tex]a_0[/tex] slik at følgen
[tex]a_N, a_{N+1}, a_{N+2}, ....[/tex]
ikke er konstant modulo p for alle positive heltall N
la p>3 være et primtall slik at [tex]p\equiv 3 (mod 4)[/tex]
Gitt et positivt heltall [tex]a_0[/tex], definer følgen [tex]a_0, a_1, ....[/tex] ved å la
[tex]a_n = a_{n-1}^{2^n}[/tex] for alle [tex]n \geq 1[/tex]
Vis at man kan velge [tex]a_0[/tex] slik at følgen
[tex]a_N, a_{N+1}, a_{N+2}, ....[/tex]
ikke er konstant modulo p for alle positive heltall N
Løsning:
Vi viser først et lemma.
Lemma: La [tex]m>2[/tex] være et positivt heltall slik at [tex]m \equiv 2 \pmod 4[/tex]. Følgen [tex]\{b_n\}_{n\geq N} \{2^{\frac{n(n+1)}{2}}\}_{n\geq N}[/tex] er ikke konstant modulo m for alle positive heltall N.
Bevis:
Vi legger først merke til den rekursive definisjonen [tex]b_n=2^n \cdot b_{n-1}[/tex] og at ingen av elementene i følgen er kongruent med 0 modulo m. Anta for motsigelsens skyld at det eksisterer et positivt heltall N slik at [tex]\{2^{\frac{n(n+1)}{2}}\}_{n\geq N}[/tex] er konstant modulo m. Det betyr at [tex]b_i\equiv b_N\not \equiv 0 \pmod m, \forall i>N[/tex]. Åpenbart er [tex]gcd(b_n,m)=2[/tex]. Vi ønsker nå å se på følgen modulo [tex]m'=\frac{m}{2}[/tex]. Av antagelsen vet vi at [tex]\{\frac{b_n}{2}\}_{n\geq N}[/tex] er konstant modulo [tex]m'[/tex], der [tex]gcd(\frac{b_n}{2},m')=1[/tex]. Av den rekursive definisjonen for følgen har vi [tex]1\equiv\frac{b_N}{2}\cdot (\frac{b_N}{2})^{-1}\equiv \frac{b_{N+1}}{2}\equiv \frac{2^{N+1}\cdot b_N}{2}\cdot(\frac{b_N}{2})^{-1}\equiv 2^{N+1} \pmod{m'}[/tex] og [tex]1\equiv\frac{b_{N+1}}{2}\cdot (\frac{b_{N+1}}{2})^{-1}\equiv \frac{b_{N+2}}{2}\equiv \frac{2^{N+2}}\cdot b_{N+1}{2}\cdot(\frac{b_{N+1}}{2})^{-1}\equiv 2^{N+2} \pmod{m'}[/tex]. Dette impliserer at [tex]1\equiv 2^{N+1}\equiv 2^{N+1}\cdot 2 \equiv 2 \pmod{m'}[/tex], en motsigelse siden [tex]m' \neq 1[/tex].
Vi tar nå fatt på oppgaven.
1) Påstand: [tex]a_n={a_0}^{2^{\frac{n(n+1)}{2}}}[/tex]
Bevis: Vi viser det med induksjon: Åpenbart holder påstanden for [tex]n=1[/tex]. Anta [tex]a_{n}={a_{0}}^{2^{\frac{n(n+1}{2}}}[/tex]. Induksjonshypotesen impliserer [tex]a_{n+1}={a_n}^{2^{n+1}}=({a_0}^{2^{\frac{n(n+1)}{2}}})^{2^{n+1}}={a_0}^{2^{\frac{(n+1)(n+2)}{2}}}[/tex]. Dermed er påstanden bevist.
Vi velger [tex]a_0=g[/tex], der g er en primitiv rot modulo p. Av 1) er [tex]a_n={g}^{2^{\frac{n(n+1)}{2}}}[/tex]. Det holder dermed å vise at følgen [tex]\{2^{\frac{n(n+1)}{2}}\}_{n\geq N}[/tex] er ikke konstant modulo [tex]p-1[/tex] for alle positive heltall N, men det følger av lemmaet siden [tex]p-1\equiv 2 \pmod 4[/tex].
Vi viser først et lemma.
Lemma: La [tex]m>2[/tex] være et positivt heltall slik at [tex]m \equiv 2 \pmod 4[/tex]. Følgen [tex]\{b_n\}_{n\geq N} \{2^{\frac{n(n+1)}{2}}\}_{n\geq N}[/tex] er ikke konstant modulo m for alle positive heltall N.
Bevis:
Vi legger først merke til den rekursive definisjonen [tex]b_n=2^n \cdot b_{n-1}[/tex] og at ingen av elementene i følgen er kongruent med 0 modulo m. Anta for motsigelsens skyld at det eksisterer et positivt heltall N slik at [tex]\{2^{\frac{n(n+1)}{2}}\}_{n\geq N}[/tex] er konstant modulo m. Det betyr at [tex]b_i\equiv b_N\not \equiv 0 \pmod m, \forall i>N[/tex]. Åpenbart er [tex]gcd(b_n,m)=2[/tex]. Vi ønsker nå å se på følgen modulo [tex]m'=\frac{m}{2}[/tex]. Av antagelsen vet vi at [tex]\{\frac{b_n}{2}\}_{n\geq N}[/tex] er konstant modulo [tex]m'[/tex], der [tex]gcd(\frac{b_n}{2},m')=1[/tex]. Av den rekursive definisjonen for følgen har vi [tex]1\equiv\frac{b_N}{2}\cdot (\frac{b_N}{2})^{-1}\equiv \frac{b_{N+1}}{2}\equiv \frac{2^{N+1}\cdot b_N}{2}\cdot(\frac{b_N}{2})^{-1}\equiv 2^{N+1} \pmod{m'}[/tex] og [tex]1\equiv\frac{b_{N+1}}{2}\cdot (\frac{b_{N+1}}{2})^{-1}\equiv \frac{b_{N+2}}{2}\equiv \frac{2^{N+2}}\cdot b_{N+1}{2}\cdot(\frac{b_{N+1}}{2})^{-1}\equiv 2^{N+2} \pmod{m'}[/tex]. Dette impliserer at [tex]1\equiv 2^{N+1}\equiv 2^{N+1}\cdot 2 \equiv 2 \pmod{m'}[/tex], en motsigelse siden [tex]m' \neq 1[/tex].
Vi tar nå fatt på oppgaven.
1) Påstand: [tex]a_n={a_0}^{2^{\frac{n(n+1)}{2}}}[/tex]
Bevis: Vi viser det med induksjon: Åpenbart holder påstanden for [tex]n=1[/tex]. Anta [tex]a_{n}={a_{0}}^{2^{\frac{n(n+1}{2}}}[/tex]. Induksjonshypotesen impliserer [tex]a_{n+1}={a_n}^{2^{n+1}}=({a_0}^{2^{\frac{n(n+1)}{2}}})^{2^{n+1}}={a_0}^{2^{\frac{(n+1)(n+2)}{2}}}[/tex]. Dermed er påstanden bevist.
Vi velger [tex]a_0=g[/tex], der g er en primitiv rot modulo p. Av 1) er [tex]a_n={g}^{2^{\frac{n(n+1)}{2}}}[/tex]. Det holder dermed å vise at følgen [tex]\{2^{\frac{n(n+1)}{2}}\}_{n\geq N}[/tex] er ikke konstant modulo [tex]p-1[/tex] for alle positive heltall N, men det følger av lemmaet siden [tex]p-1\equiv 2 \pmod 4[/tex].
-
Lil_Flip38
- Noether
- Innlegg: 40
- Registrert: 10/12-2023 10:58
- Sted: Abelmaraton
Det er mulig at de ikke er symmetriske om aksene eller sentrum.
I $x,y$ planet la $O=(0,0), A=(2,0), B=(2,1), C=(0,2),D=(-1,2)$. Det er lett å se at trekantene $OAB$ og $OCD$ er kongruente. Vi regner ut likningen til det unike kjeglesnittet gjennom disse 5 punktene som har formen: $Ax^2+Bxy+Cy^2+Dx+Ey+F=0$. Det er litt utregning som jeg lar skli, men det er trivielt. Til slutt ender vi opp med $x^2+(3/2)xy+3y^2-2x-6y$. Det er velkjent at hvis $AC>0$ er kjeglesnittet en elipse. Når man roterer $OAB$ med 90 grader rundt $O$ ender man opp med $OCD$. Siden trekantene er i samme retning, kan det ikke være refleksjon over en av aksene. For at det skal være symmetrisk om sentrum, må det være rotasjon med 180 grader rundt sentrum. Da kan det ikke ha noen fikspunkter utenom sentrum, men $O$ er et fixedpunkt som ikke er sentrum. Derfor er vi ferdige.
I $x,y$ planet la $O=(0,0), A=(2,0), B=(2,1), C=(0,2),D=(-1,2)$. Det er lett å se at trekantene $OAB$ og $OCD$ er kongruente. Vi regner ut likningen til det unike kjeglesnittet gjennom disse 5 punktene som har formen: $Ax^2+Bxy+Cy^2+Dx+Ey+F=0$. Det er litt utregning som jeg lar skli, men det er trivielt. Til slutt ender vi opp med $x^2+(3/2)xy+3y^2-2x-6y$. Det er velkjent at hvis $AC>0$ er kjeglesnittet en elipse. Når man roterer $OAB$ med 90 grader rundt $O$ ender man opp med $OCD$. Siden trekantene er i samme retning, kan det ikke være refleksjon over en av aksene. For at det skal være symmetrisk om sentrum, må det være rotasjon med 180 grader rundt sentrum. Da kan det ikke ha noen fikspunkter utenom sentrum, men $O$ er et fixedpunkt som ikke er sentrum. Derfor er vi ferdige.
-
Lil_Flip38
- Noether
- Innlegg: 40
- Registrert: 10/12-2023 10:58
- Sted: Abelmaraton
Let $\mathbb N$ denote the set of positive integers. A function $f\colon\mathbb N\to\mathbb N$ has the property that for all positive integers $m$ and $n$, exactly one of the $f(n)$ numbers
\[f(m+1),f(m+2),\ldots,f(m+f(n))\]
is divisible by $n$. Prove that $f(n)=n$ for infinitely many positive integers $n$.
\[f(m+1),f(m+2),\ldots,f(m+f(n))\]
is divisible by $n$. Prove that $f(n)=n$ for infinitely many positive integers $n$.
Disclaimer: texeditoren funket ikke,
Løste med litt hint
Lemma 0: f(1) = 1
anta f(1) = k.
da vil 1 dele nøyaktig et av tallene f(m+1) ... f(m+k) for alle m.
men 1 deler alle tall, så de må være like alle sammen, dermed må enten alle f(x) være like, som åpenbart er umulig, eller det er bare ett tall, som impliserer k=1.
Lemma 1: n|f(x) = > x = i f(n) +k, der i varierer og k er konstant
bevis:
fra oppgaven, vet vi at gitt f(n) påfølgende tall, vil n dele nøyaktig ett av tallene.
Vi vet at n deler et av tallene f(2), f(3), f(1+f(n))
la k være det minste tallet slik at n | f(k)
da vil n dele nøyaktig ett av tallene f(k), f(k+1), ... f(k+f(n)-1).
men n | f(k), så n deler ingen av de andre tallene. Når vi da går videre til f(k+f(n)), får vi at k må dele f(k+f(n)).
tilsvarene argument for i >1 viser at n kun deler funksjoner av tall på formen k+i f(n)
vi kaller f(n) avstanden mellom faktorene til n
Lemma 2: a|b => f(a) | f(b)
Anta a|b.
f(a) er da avstanden mellom hver faktor til a, f(b) er avstanden mellom hver faktor av b
hvis f(a) ikke deler f(b), får vi at det finnes et multippel x av f(b), som ikke er et multippel av f(a), men dette er umulig, siden b|n => a|n, så f(a) |x
Lemma 3: n | f(x) => f(n) |x
anta n | f(x)
vi har av lemma 2 at x|mx => f(x) |f(mx),
dermed vil n|f(2x)
vi har da at mx = q f(n) + k og at (m-1)x = i f(n) + k
slik at mx-(m-1)x = (q-i) f(n) = x, med mindre q = i. Hvis dette gjelder for alle m, vil f(kx) være konstant for alle k. noe som åpenbart fører til en motsigelse, fordi f(p) | f(xp) for alle primtall p. Dermed hadde tallet blitt uendelig stort
dermed vil (q-i) f(n) = x, som betyr at f(n) | x.
la nå x være minste tall slik at n | f(x)
Av lemma 3: f(n) | x
Siden det er minste mulige x, vil x være mindre en avstandene mellom faktorene, slik at x <= f(n). Dermed vil x = f(n)
Av det får vi at x|f(n), og av lemma 3 følger det at f(x) | n
dermed har vi at f(x) = n, og f(n) = x:
Dermed har vi at f(f(n)) = n for uendelig mange n. (Vi vet det er uendelig mange siden f ikke er oppad begrenset, uendelig mange tall kan ikke mappes på samme tall, siden da hadde det blitt uendelig stort, dermed kan vi velge uendelig mange minste x-er)
Vi kan nå fullføre oppgaven
MEN det er sent, så fullfører heller imorgen
Løste med litt hint
Lemma 0: f(1) = 1
anta f(1) = k.
da vil 1 dele nøyaktig et av tallene f(m+1) ... f(m+k) for alle m.
men 1 deler alle tall, så de må være like alle sammen, dermed må enten alle f(x) være like, som åpenbart er umulig, eller det er bare ett tall, som impliserer k=1.
Lemma 1: n|f(x) = > x = i f(n) +k, der i varierer og k er konstant
bevis:
fra oppgaven, vet vi at gitt f(n) påfølgende tall, vil n dele nøyaktig ett av tallene.
Vi vet at n deler et av tallene f(2), f(3), f(1+f(n))
la k være det minste tallet slik at n | f(k)
da vil n dele nøyaktig ett av tallene f(k), f(k+1), ... f(k+f(n)-1).
men n | f(k), så n deler ingen av de andre tallene. Når vi da går videre til f(k+f(n)), får vi at k må dele f(k+f(n)).
tilsvarene argument for i >1 viser at n kun deler funksjoner av tall på formen k+i f(n)
vi kaller f(n) avstanden mellom faktorene til n
Lemma 2: a|b => f(a) | f(b)
Anta a|b.
f(a) er da avstanden mellom hver faktor til a, f(b) er avstanden mellom hver faktor av b
hvis f(a) ikke deler f(b), får vi at det finnes et multippel x av f(b), som ikke er et multippel av f(a), men dette er umulig, siden b|n => a|n, så f(a) |x
Lemma 3: n | f(x) => f(n) |x
anta n | f(x)
vi har av lemma 2 at x|mx => f(x) |f(mx),
dermed vil n|f(2x)
vi har da at mx = q f(n) + k og at (m-1)x = i f(n) + k
slik at mx-(m-1)x = (q-i) f(n) = x, med mindre q = i. Hvis dette gjelder for alle m, vil f(kx) være konstant for alle k. noe som åpenbart fører til en motsigelse, fordi f(p) | f(xp) for alle primtall p. Dermed hadde tallet blitt uendelig stort
dermed vil (q-i) f(n) = x, som betyr at f(n) | x.
la nå x være minste tall slik at n | f(x)
Av lemma 3: f(n) | x
Siden det er minste mulige x, vil x være mindre en avstandene mellom faktorene, slik at x <= f(n). Dermed vil x = f(n)
Av det får vi at x|f(n), og av lemma 3 følger det at f(x) | n
dermed har vi at f(x) = n, og f(n) = x:
Dermed har vi at f(f(n)) = n for uendelig mange n. (Vi vet det er uendelig mange siden f ikke er oppad begrenset, uendelig mange tall kan ikke mappes på samme tall, siden da hadde det blitt uendelig stort, dermed kan vi velge uendelig mange minste x-er)
Vi kan nå fullføre oppgaven
MEN det er sent, så fullfører heller imorgen