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.

Ordning av de naturlige tall

Innlegg Gustav » 04/03-2018 17:56

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}$
Gustav offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 4296
Registrert: 12/12-2008 12:44

Re: Ordning av de naturlige tall

Innlegg Markus » 25/03-2018 00:44

Har du noe starthint her Gustav?
Markus offline
Fermat
Fermat
Innlegg: 760
Registrert: 20/09-2016 12:48
Bosted: NTNU

Re: Ordning av de naturlige tall

Innlegg Aleks855 » 25/03-2018 01:08

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
Aleks855 offline
Rasch
Rasch
Innlegg: 5895
Registrert: 19/03-2011 15:19
Bosted: Trondheim

Re: Ordning av de naturlige tall

Innlegg mingjun » 26/03-2018 17:51

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å.
mingjun offline
Cayley
Cayley
Innlegg: 91
Registrert: 18/11-2016 21:13
Bosted: Det projektive planet

Re: Ordning av de naturlige tall

Innlegg Gustav » 04/04-2018 15:34

Fint!
Gustav offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 4296
Registrert: 12/12-2008 12:44

Hvem er i forumet

Brukere som leser i dette forumet: Ingen registrerte brukere og 58 gjester