Ordning av de naturlige tall

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Vis at det fins en ordning av de naturlige tallene, dvs. en følge $x_i$ med $i=1,2,3,4,...$ slik at ethvert naturlig tall forekommer nøyaktig én gang, og slik at følgen $\sum_{i=1}^n \frac{1}{x_i}$ for $n=1,2,3,4,...$ inneholder alle naturlige tall, dvs. at for ethvert naturlig tall $m$, fins en $n$ slik at $m=\sum_{i=1}^n \frac{1}{x_i}$
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

Har du noe starthint her Gustav?
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Disse nøttene blir bare vanskeligere og vanskeligere.

Bilde

:lol:

Tror forøvrig ikke det er noen grunn til bekymring. MathJax faila ved innlasting, men bare denne ene gangen (såvidt jeg kan se).
Bilde
mingjun
Cayley
Cayley
Innlegg: 91
Registrert: 18/11-2016 21:13
Sted: Det projektive planet

Det kan godt være mulig at jeg har misset ut på et mer elegant bevis enn som så. Det skulle ikke overraske meg hvis det er mulig å gjøre dette ikke-konstruktivt, ettersom hele oppgaven baserer seg egentlig på faktumet at det finnes nok enkle brøker til å lage så mange av hvilken som helst annen brøk vi vil. Uansett, her er mitt bevis.

Definisjon: Et enkelt brøk er et brøk i formen av $\frac{1}{x}$ hvor $x$ er et heltall.

Lemma:
For alle heltall $x<y$, det er mulig å skrive $\frac{1}{x}$ som en sum av endelig mange unike enkle brøker $\frac{1}{a_1}> \frac{1}{a_2}> \dots$ hvor $\frac{1}{a_1}<\frac{1}{y}$.

Bevis:
For ethvert enkelt brøk $\frac{1}{z}$ kan vi skrive $\frac{1}{z}=\frac{1}{z+1}+\frac{1}{z^2+z}$. Legg så merke til at leddene på høyre side er ulike for $z\neq 1$ og begge mindre enn $\frac{1}{z}$. Vi utfører nå en enkel algoritme på $S=\{a_1,a_2,\dots\}$ (anta at $a_1\leq a_2\leq a_3 \leq...$, vi tillater at samme tall opptrer flere gang i $S$). I begynnelsen er $S=\{x\}$, og summen av inversene av elementene i $S$ er konstant lik $\frac{1}{x}$:

Velg det minste $a_i$ slik at $a_i\in S$ ikke er unik i $S$ eller oppfyller $a_i\leq y$ (kall en slik $a_i$ for ulovlig), bytt ut $a_i$ med dens omskriving beskrevet over. Legg merke til at for hver gang denne algortimen utføres, blir den minste ulovlige $a_i$ større. Definer så $b$ som det største elementet i $S$ i det første øyeblikket der ingen $a_i\leq y$. Utfør nå algoritmen helt til det ikke eksisterer noen ulovlige $a_i\leq b$. Ved definisjon er nå alle ulovlige elementer større enn $b$, og alle har kommet fra å bytte ut en $a_i$ i intervallet mellom $y$ og $b+1$ med $a_i^2+a_i$. Dermed må nå alle ulovlige $a_j$ og $a_i$ oppfylle $|a_j-a_i|>2y >2$.

Nå som det er minst en distanse av 2 mellom alle ulovlige $a_i$, vil en utbytting aldri skape flere ulovlige elementer enn den fjerner. Hvis vi da anvender utbyttingen på den største ulovlige $a_i$, vil det nødvendigvis komme til et punkt hvor $a_i^2+a_i$ er større enn det største elementet i $S$, hvor vi da får fjernet et ulovlig element. Dersom vi gjentar dette vil vi ende opp med en mengde $S$ som er hva vi ønsket. $\blacksquare$

Alt som nå gjenstår er å lage den ønskede følgen $x_1,x_2,\dots$. Vi går frem slik:
1) La $x_1=1$.
2) Velg den minste $n$ som ikke ennå har opptrådt i $x_i$, og fest den på enden av følgen.
3) Anvend lemma $n-1$ ganger for å få $n-1$ mengder hvis sum av respektive inverser av dens elementer er $\frac{1}{n}$. For hver gang lemma anvendes, fest elementene i mengden fra lemma til slutten av følgen. For hver gang, la valget av $y$ i lemma være den største $m$ som har opptrådt i følgen så langt.
4) Nå vil summen av $\frac{1}{x_i}$ opp til dette punktet være $1$ større enn ved starten av steg 2). Gå til steg 2.

Ved konstruksjon vil alle heltallige $n$ finnes i følgen, og pga. $\sum \frac{1}{x_i}$ ved starten av steg 2). starter med å være $1$, vil den gå gjennom alle heltallene også.
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Fint!
Svar