Opravovatelia

Viktor [email protected]

Poďme dokázať indukciou, že sa naozaj všetky kladné celé čísla dajú v takomto tvare vyjadriť. Začnime indukčnou bázou: $$1 = 3^0\cdot2^0.$$ Zjavne takto vieme vyjadriť číslo $1$. Teraz pokračujme indukčným krokom: Predstavme si, že máme takto vyjadriť číslo $n$. Môžeme rátať s pravdivosťou indukčného predpokladu, ktorý nám hovorí, že takto už vieme vyjadriť všetky nižšie kladné celé čísla. Pokiaľ $n$ je párne, vieme ho vyjadriť veľmi jednoducho tak, že vyjadríme $n/2$, ale v každom člene zvýšime mocninu $2$ o $1$, čím teda celý výsledok zdvojnásobíme bez toho, aby prestala platiť podmienka zoradenia mocnín zo zadania. Napríklad číslo $7$ vieme vyjadriť ako $$7 = 3^1\cdot2^0+3^0\cdot2^2.$$ Potom vieme vyjadriť jeho dvojnásobok nasledovne: $$14 = 3^1\cdot2^1+3^0\cdot2^3.$$ Čo ak je ale $n$ nepárne? Nájdime najvyššie celé číslo $x$ také, že $3^x \leq n$. Pokiaľ dochádza k rovnosti, $n$ je mocnina troch a dá sa vyjadriť jednoducho nasledovne: $$n = 3^x\cdot2^0.$$ V opačnom prípade je nerovnosť ostrá, a teda $n-3^x$ je nejaké kladné celé číslo menšie ako $n$. Označme ho $m$. Zároveň platí, že keďže $x$ je najvyššie také číslo, určite už pre číslo o jedna vyššie nerovnosť neplatí, teda $3^{x+1} > n$. Z toho vyplýva aj, že $m = n-3^x < 3^{x+1} - 3^x = 2\cdot3^x$, ale táto horná hranica pre veľkosť $m$ bude relevantná až neskôr. Teraz si povedzme, ako vyjadriť $n$. Podľa indukčného predpokladu určite $m$ vyjadriť vieme, tak jednoducho k tomuto súčtu na začiatok (poradie členov nás zaujíma, pretože náš súčet musí spĺňať dve podmienky ich poradia) pripočítajme člen $3^x\cdot2^0$. Teda napríklad, keď číslo $10$ vieme vyjadriť ako $$10 = 3^1\cdot2^1+3^0\cdot2^2,$$ skúsme z neho vyjadriť číslo $19$. Odrátajme od $19$ najvyššiu možnú mocninu troch, čo je v tomto prípade $9$, a sčítajme ju s vyjadrením čísla $19-9 = 10$. Dostaneme tak $$19 = 3^2\cdot2^0+3^1\cdot2^1+3^0\cdot2^2,$$ Dokážme, že takýto rad bude vždy spĺňať všetky zadané podmienky. Určite platí, že súčtom je naozaj $n$, pretože prvý člen dáva súčet $3^x$ a zvyšné $m = n-3^x$. Teraz už len ukázať, že exponenty nad trojkami klesajú a exponenty nad dvojkami stúpajú.

Začnime dvojkami. V našom novom člene je exponent nad dvojkou vždy $0$. Keďže zvyšné exponenty už boli súčasťou správneho vyjadrenia čísla $m$, určite stúpajú aj teraz, a teda jediný problém, ktorý môže nastať, je keď aj exponent druhého členu je $0$. Toto ale nemôže nastať. Prečo? Tento exponent bol pôvodne prvým členom vyjadrenia $m$. Teda ak by bol nulový, znamenalo by to, že $m$ je súčtom niekoľkých členov, z ktorých jeden je nejakým číslom v tvare $3^?\cdot2^0$, teda vždy nepárny, a zvyšné členy musia mať všetky vyššie exponenty, teda všetky sú násobkami $2$, teda párne. Súčtom ľubovoľne veľa párnych a jedného nepárneho čísla je vždy číslo nepárne, teda $m$ by muselo byť nepárne. Lenže $m$ sme už zadefinovali ako súčet (resp. rozdiel) dvoch nepárnych čísel $n-3^x$, teda musí byť párne. Dostávame spor, a vidíme, že naozaj budú exponenty nad dvojkou len stúpať.

Ostáva posledný krok, ukázať, že exponenty nad trojkami klesajú. Všetky exponenty po prvom boli predtým súčasťou vyjadrenia čísla $m$, teda musia klesať. Jediné, čo musíme ukázať, je že klesajúcosť sa zachová aj medzi prvým a druhým exponentom. Teda, že prvý exponent, čo je $x$, je vyšší ako druhý. Predstavme si, že by to tak nebolo. Teda druhý člen by vyzeral takto: $3^u\cdot2^v$, kde $u \geq x$ a $v > 0$ (vieme, že exponent nad dvojkou bude kladný, pretože už sme dokázali, že exponenty nad dvojkami naozaj stúpajú). To znamená, že tento člen vieme zdola odhadnúť ako $3^u\cdot2^v \geq 3^u\cdot2 \geq 3^x\cdot2$. Zároveň vieme, že tento člen je súčasťou súčtu kladných čísel, ktorého veľkosť je $m$. Preto platí $m \geq 3^u\cdot2^v$ a teda spojením dvoch nerovností $m \geq 3^x\cdot2$. Tu nám ale vzniká spor – už dávnejšie sme povedali, že $m < 2\cdot3^x$. Teda náš predpoklad nebol správny. To znamená, že určite sa nám nestane, že novopridaný člen $3^x\cdot2^0$ naruší akúkoľvek peknú vlastnosť našej postupnosti, a teda naše vyjadrenie pre nepárne $n$ je vždy správne. Tým sme ukázali pre párne aj nepárne $n$, ako ich s pomocou vyjadrení nižších čísel vyjadriť tiež, a že tieto vyjadrenia vždy spĺňajú zadané podmienky.