Zadanie
Vlak zastavil v Margecanoch, kde všetkých cestujúcich vysadili z vlaku, pretože na koľajnice sa vysypal piesok, a tak nemohli pokračovať v ceste, kým sa neodprace. Vedúci sa preto rozhodli, že kým budú čakať na odpratanie piesku z koľajníc, tak si na parkovisku pred stanicou spolu s účastníkmi zatancujú.
Dievčatá aj chlapci sa zoradili podľa výšky, pochytali sa za ruky a vytvorili páry tak, že najvyššie dievča bolo s najnižším chlapcom, druhé najvyššie s druhým najnižším a tak ďalej. Potom spustili hudbu a všetky páry začali spolu mocne tancovať. Nikto nevedel predpovedať, k čomu toto jašenie povedie, výsledok mohol byť úplne akýkoľvek.
Dokážte, že ľubovoľné kladné celé číslo sa dá vyjadriť v tvare \[3^{u_1}\cdot2^{v_1}+3^{u_2}\cdot2^{v_2}+\cdots+3^{u_k}\cdot2^{v_k},\] kde \(k\) je kladné celé číslo a \(u_1>u_2>\cdots>u_k\geq0\) a \(0\leq v_1<v_2<\cdots<v_k\) sú nezáporné celé čísla.
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.
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ť.