Side 1 av 1
Ordning av de naturlige tall
Lagt inn: 04/03-2018 17:56
av Gustav
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}$
Re: Ordning av de naturlige tall
Lagt inn: 25/03-2018 00:44
av Markus
Har du noe starthint her Gustav?
Re: Ordning av de naturlige tall
Lagt inn: 25/03-2018 01:08
av Aleks855
Disse nøttene blir bare vanskeligere og vanskeligere.
Tror forøvrig ikke det er noen grunn til bekymring. MathJax faila ved innlasting, men bare denne ene gangen (såvidt jeg kan se).
Re: Ordning av de naturlige tall
Lagt inn: 26/03-2018 18:51
av mingjun
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å.
Re: Ordning av de naturlige tall
Lagt inn: 04/04-2018 16:34
av Gustav
Fint!