Zadanie
Pamätáte si ešte, ako sme vám na sústredeniach vždy hovorili, že príde Mojo a bude Náboj? Hádam hej, veď to už celkom zľudovelo. Skúsme to teraz trochu pozmeniť. Namiesto Náboja budeme mať nekonečne veľa konečných postupností núl a jednotiek, ktoré označíme \(a_1,a_2,a_3,\dots\) Začneme s \(a_1=0\). Príde Mojo a postupne bude vytvárať ďalšie členy tejto postupnosti, a to tak, že si na papier napíše poslednú zatiaľ vytvorenú postupnosť, \(a_i\), dvakrát za sebou, ale keď ju bude písať druhýkrát, tak namiesto núl bude písať jednotky a namiesto jednotiek nuly. Takto dostane postupnosť \(a_{i+1}\) a tak isto postupuje ďalej. Prvé štyri členy teda budú \[a_1=0,\ a_2=01,\ a_3=0110,\ a_4=01101001.\] Keď Mojo bude opakovať tento proces donekonečna, dostane postupnosť \(a=0110100110010110\dots\) Dokážte, že desatinné číslo \(0.a\) nie je racionálne.1
Poznámka: Zápis \(0.a\) znamená, že nalepíme \(a\) ako desatinnú časť čísla za \(0\).
Podľa Martina Kopčányho (upravené)
Dokázať, že niečo je racionálne číslo, je ekvivalentné s nájdením periódy v desatinnom rozvoji. Dokázanie, že niečo nie je racionálne, je ekvivalentné s dokázaním, že taká perióda neexistuje. Dokážeme, že žiadna taká perióda nemôže existovať.
Uvažujme nasledujúce dve operácie a dva pojmy. Nech \(p\) je číslo zložené z núl a jednotiek. Operácia \(p^s\) predstavuje číslo \(p\) napísané odzadu. Číslo \(p\) je symetrické (t. j. palindróm1), ak platí \(p^s=p\). Operáciou \(p^i\) dostaneme inverzné číslo k číslu \(p\), to je také, ktoré sa napíše z čísla \(p\) vymenením \(0\) za \(1\) a naopak. Antisymetrické číslo je také, pre ktoré platí \(p^{is}=p\). Na poradí operátorov \(i\) a \(s\) nezáleží. Znakom \(|\) označíme spojenie čísel za seba. Rozmyslime si, že \((a|b)^i=a^i|b^i\), \((a|b)^s=b^s|a^s\).
Všimnime si, že číslo \(a_2\) je antisymetrické číslo, \(a_3\) je symetrické číslo a \(a_4\) je antisymetrické číslo. Pre indukciu predpokladajme, že \(a_{2k-1}\) je symetrické číslo a \(a_{2k-2}\) je antisymetrické číslo, potom \[(a_{2k})^{is} = (a_{2k-1}|a_{2k-1}^i)^{is} =(a_{2k-1}^i|a_{2k-1})^s=a_{2k-1}^s|a_{2k-1}^{is}=a_{2k-1}|a_{2k-1}^i=a_{2k},\] čiže \(a_{2k}\) je antisymetrické číslo za využitého predpokladu, že \(a_{2k-1}\) je symetrické. Ak \(a_{2k}\) je antisymetrické číslo, potom \[a_{2k+1}^s = (a_{2k} | a_{2k}^i)^s = a_{2k}^{is}|a_{2k}^{s}=a_{2k}|a_{2k}^{i}=a_{2k+1},\] tak \(a_{2k+1}\) je symetrické číslo za využitia antisymetrickosti \(a_{2k}^{is}=a_{2k}\), resp. \(a_{2k}^{s}=a_{2k}^i\).
Označme \(p\) periódu dĺžky \(d\). Taktiež vieme, že ak perióda existuje, musí niekde začať a jej začiatok si môžeme definovať na ľubovoľný iný neskorší člen postupnosti. Pre názornú ukážku \(0.\overline{17} = 0.1\overline{71}\).
Môžeme predpokladať, že existuje \(a_{2i-1}\) také, že \(a_{2i-1} = 0110\dots p\). Potom \(a_{2i}=0110 \ldots p | p\ldots=a_{2i-1}| p\ldots\). Keďže \(a_{2i-1}^s=a_{2i-1}\) je symetrické, taktiež vieme, že číslo \[a_{2i}=a_{2i-1}|a_{2i-1}^i=a_{2i-1}|a_{2i-1}^{si} = a_{2i-1} | (0110\dots p)^{si} = a_{2i-1} | (p^s\dots 0110)^i = a_{2i-1} | p^{si}\dots 1001.\] Za \(a_{2i-1}\) nasleduje \(p^{si}\), ale zároveň to musí byť rovné \(p\), takže \(p=p^{si}\) je antisymetrické číslo.
Ak je dĺžka čísla \(p\) nepárna, t. j. \(d=2k+1\), tak stredná cifra čísla \(p\) a \(p^{is}\) sú rôzne, a keďže musí platiť \(p=p^{is}\), tak dostávame spor.
Ak je dĺžka párna, uvažujme následujúcu postupnosť \(A=01\), \(B=10\) a \(b_2 =AB\), \(b_3=ABBA\) a tak ďalej. Číslo \(b_n\) má rovnaký tvar ako \(a_n\), len namiesto \(0\), \(1\) máme \(A\), \(B\). Keď však dosadíme \(A=01\), \(B=10\), dostaneme \(b_n=a_{n+1}\). Dôkaz indukciou, pre \(n=1\) platí \(b_1=A=01=a_2\). Ďalej \[b_n=b_{n-1}|b_{n-1}^i=a_n|a_{n}^i=a^{n+1}.\]
Označme desatinné číslo \(0.b\), ktoré má za desatinnou čiarkou znaky \(A\), \(B\) namiesto \(0\), \(1\). Perióda \(p\) je zvolená tak, že začína na nepárnej pozícii. Preto pozostáva z úsekov dĺžky \(2\), ktoré sú \(A\) alebo \(B\). To znamená, že \(0.b\) je periodické s dĺžkou periódy \(d/2\). Lenže \(0.b\) je zároveň len prepísané \(0.a\), kde píšeme \(A\), \(B\) namiesto \(0\), \(1\). Takže \(0.a\) je periodické aj s periódou dĺžky \(d/2\). Avšak periódu \(p\) sme si mohli zvoliť najkratšiu možnú, a dostali sme kratšiu periódu ako \(p\) dĺžky \(d/2\), čo je spor.
Preto taká perióda nemôže existovať a číslo \(0.a\) nie je racionálne.
Známymi palindrómami sú napríklad kobyla ma malý bok, Alomomola, aktivitka.↩︎
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.