Ordning av de naturlige tall Skriv et svar


Dette spørsmålet er en metode for identifisering og hindring av automatiserte innsendinger.
Smil
:D :) :( :o :shock: :? 8-) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:
BBCode er
[img] er
[flash] er AV
[url] er
Smil er
Emne
   

Utvid visningen Emne: Ordning av de naturlige tall

Re: Ordning av de naturlige tall

Innlegg Gustav » 04/04-2018 15:34

Fint!

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å.

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).

Re: Ordning av de naturlige tall

Innlegg Markus » 25/03-2018 00:44

Har du noe starthint her Gustav?

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}$

Topp