To mengder

[mrcreosote]

Betrakt mengdene

[tex]A=\{\lfloor sqrt2\rfloor,\lfloor2sqrt2\rfloor,\lfloor3sqrt2\rfloor,\dots\}[/tex]

og

[tex]B=\{\lfloor2+ sqrt2\rfloor,\lfloor2(2+sqrt2)\rfloor,\lfloor3(2+sqrt2)\rfloor,\dots\}[/tex]

Hvilke naturlige tall ligger i begge disse mengdene? Hvilke ligger ikke i noen?

[Charlatan]

[tex]A= \{ \lfloor \sqrt{2}k \rfloor \ | \ k \in \mathbb{N} \} \\ B= \{ \lfloor (\sqrt{2}+2)s \rfloor \ | \ s \in \mathbb{N} \}[/tex]

Først merker vi oss at hvert element generert av både [tex]\lfloor \sqrt{2}k \rfloor[/tex] og [tex]\lfloor (\sqrt{2}+2)s \rfloor[/tex] er forskjellige fra andre elementer i samme sett for forskjellige heltall [tex]k,s[/tex].

Vi vil finne elementer [tex]a,b[/tex] i [tex]A, B[/tex] respektivt slik at [tex]a=b[/tex]. De eksisterer hvis vi kan finne [tex]k,s[/tex] slik at

[tex]\lfloor \sqrt{2}k \rfloor=\lfloor (\sqrt{2}+2)s \rfloor \ ... \ (1)[/tex]

[tex](1)[/tex] medfører at [tex]\sqrt{2}k[/tex] og [tex](\sqrt{2}+2)s[/tex] ligger i samme enhetsintervall på tallinja som betyr at

[tex]|\sqrt{2}k-(\sqrt{2}+2)s|<1 \\ \Leftrightarrow (\sqrt{2}+1)s -1<-\frac{\sqrt{2}}{2}+(\sqrt{2}+1)s<k<\frac{\sqrt{2}}{2}+(\sqrt{2}+1)s< (\sqrt{2}+1)s +1 \ ... \ (2) [/tex]

Siden ingen av uttrykkene ytterst til høyre og venstre i [tex](2)[/tex] er heltall, så har vi at

[tex]\lceil (\sqrt{2}+1)s \rceil -1 =\lfloor (\sqrt{2}+1)s \rfloor \leq k \leq \lfloor (\sqrt{2}+1)s \rfloor +1 \Rightarrow k= \lfloor (\sqrt{2}+1)s \rfloor \ \vee \ k=\lfloor (\sqrt{2}+1)s \rfloor+1 \ ... \ (3)[/tex]

La [tex]r[/tex] være definert ved [tex](\sqrt{2}+1)s=\lfloor (\sqrt{2}+1)s \rfloor+r[/tex]. Da er [tex]0<r<1[/tex]. Dessuten er [tex]\lfloor \sqrt{2}s \rfloor+r=\sqrt{2}s[/tex].

Vi setter inn den første verdien til [tex]k[/tex] fra [tex](3)[/tex] i [tex](1)[/tex] på venstre side:

[tex]\lfloor \sqrt{2}k \rfloor = \lfloor \sqrt{2}\lfloor (\sqrt{2}+1)s \rfloor \rfloor= \lfloor \sqrt{2}((sqrt{2}+1)s-r) \rfloor=\lfloor 2s+\sqrt{2}s-\sqrt{2}r \rfloor = \lfloor 2s+\lfloor \sqrt{2}s \rfloor+r-\sqrt{2}r \rfloor =2s+\lfloor \sqrt{2}s \rfloor+\lfloor -(\sqrt{2}-1)r \rfloor=2s+\lfloor \sqrt{2}s \rfloor-1 \ ... \ (4)[/tex]

[tex](1)[/tex] og [tex](4)[/tex] gir en motsigelse, så vi prøver med den andre verdien for [tex]k[/tex] :

[tex]\lfloor \sqrt{2}k \rfloor=\lfloor \sqrt{2}+\sqrt{2}\lfloor(\sqrt{2}+1)s \rfloor \rfloor=\lfloor \sqrt{2}+\sqrt{2}((\sqrt{2}+1)s-r) \rfloor=\lfloor \sqrt{2}+2s+\sqrt{2}s-\sqrt{2}r \rfloor = \lfloor \sqrt{2}+2s+\lfloor \sqrt{2}s \rfloor+r-\sqrt{2}r \rfloor=2s+\lfloor \sqrt{2}s \rfloor+\lfloor \sqrt{2}-(\sqrt{2}-1)r \rfloor[/tex]

Men [tex]1= \sqrt{2}-(\sqrt{2}-1) < \sqrt{2}-(\sqrt{2}-1)r <\sqrt{2}[/tex], så [tex]\lfloor \sqrt{2}-(\sqrt{2}-1)r \rfloor =1[/tex] som gir enda en motsigelse.

[tex]A[/tex] og [tex]B[/tex] har ingen felles elementer.

Vi finner alle elementer [tex]a \in A, b \in B[/tex] slik at [tex]a,b < N[/tex] for et vilkårlig heltall [tex]N[/tex].

[tex]\lfloor \sqrt{2}k \rfloor < N \Leftrightarrow \sqrt{2}k<N \Leftrightarrow k < \frac{\sqrt{2}}{2}N \Leftrightarrow k=1,2,...,\lfloor \frac{\sqrt{2}}{2}N \rfloor[/tex].

[tex]\lfloor (\sqrt{2}+2)s \rfloor < N \Leftrightarrow (\sqrt{2}+2)s < N \Leftrightarrow s < (1-\frac{\sqrt{2}}{2})N \Leftrightarrow s=1,2,...,\lfloor (1-\frac{\sqrt{2}}{2})N \rfloor[/tex].

Det er altså [tex]\lfloor \frac{\sqrt{2}}{2}N \rfloor[/tex] muligheter for [tex]a[/tex], og [tex]\lfloor (1-\frac{\sqrt{2}}{2})N \rfloor[/tex] muligheter for [tex]b[/tex].

Men siden [tex]a \not = b[/tex], må hver av dem ha forskjellige verdier. Det er [tex]N-1[/tex] verdier under [tex]N[/tex] tilgjengelig. Antall verdier [tex]a[/tex] og [tex]b[/tex] opptar er

[tex]\lfloor (1-\frac{\sqrt{2}}{2})N \rfloor + \lfloor \frac{\sqrt{2}}{2}N \rfloor=N+ \lfloor \frac{\sqrt{2}}{2}N \rfloor +\lfloor -\frac{\sqrt{2}}{2}N \rfloor=N+ \lfloor \frac{\sqrt{2}}{2}N \rfloor -\lceil -\frac{\sqrt{2}}{2}N \rceil=N-1[/tex].

Dette betyr at [tex]a[/tex] og [tex]b[/tex] opptar hver verdi under [tex]N[/tex] for hvilken som helst [tex]N[/tex]. Ved induksjon tar [tex]a[/tex] og [tex]b[/tex] verdiene til alle naturlige tall. Det er altså ingen tall som ikke ligger i verken [tex]A[/tex] eller [tex]B[/tex].

Interessant nok er [tex]A \cap B =\emptyset[/tex] og [tex]A \cup B = \mathbb{N}[/tex].

[Charlatan]

Oppfølger:


[tex]A= \{ \lfloor \sqrt{n}k \rfloor \ | \ k \in \mathbb{N} \} \\ B= \{ \lfloor (\sqrt{n}+n)k \rfloor \ | \ k \in \mathbb{N} \}[/tex]

Hva er sannsynligheten for at et tilfeldig valgt naturlig tall ligger i [tex]A[/tex] eller [tex]B[/tex] hvis [tex]n[/tex] er et naturlig tall?