Zadanie
Vďaka Konštrukčnému Mirovmu Semináru mesto ustálo všetky útoky Kazisveta Matúša Strašného a jeho Katapultu Monštruóznej Sily. O chvíľu obom stranám došlo, že priamym útokom nikto túto vojnu nevyhrá a tak Matúš zahájil blokádu mesta. Aby sa kráľovná Kika vyhla hladomoru, povolala svoju najmúdrejšiu komornú Magdu a dala jej za úlohu nájsť všetky zásoby jedla. Zásoby sú však poschovávané po celom meste podľa veľmi sofistikovaného vzorca tak, aby ich Ákos nenašiel a nezjedol ich. Magda vďaka svojmu umu hravo našla všetky zásoby jedla v meste. Nájdete ich aj vy?
Nájdite všetky trojice kladných celých čísel \((a,b,n)\), pre ktoré platí: \[a!+b!=2^n\]
Máme nájsť všetky trojice kladných celých čísel\((a,b,n)\), čiže \(a,b,n \in \mathbb{N}\), že \(a! + b! = 2^n\). Keďže vidíme, že tam máme dva faktoriály a \(2^n\) tak sa pokúsime nájsť tieto trojice pomocou prvočíselného rozkladu.
Faktoriál je také číslo ktoré vieme zapísať ako \(n! = n \cdot (n-1) \cdot (n-2) \cdot \cdots \cdot 3 \cdot 2 \cdot 1\), čo už samo o sebe vyzerá podobne ako prvočíselný rozklad. Číslo \(2^n\) zas vieme napísať ako \(2^n = 2\cdot2\cdot2\cdot \cdots \cdot2\), čo je prvočíselný rozklad čísla \(2^n\).
Zoberme si dva veľké faktoriály, také že \(a,b \geq 3\). Tie vieme napísať do rovnice ako \(a!+b!=1\cdot2\cdot3\cdot o + 1\cdot2\cdot3\cdot s = 2^n\) kde \(o\) a \(s\) sú zvyšné činitele faktoriálu. Z toho vieme vyňať \(3\) a dostaneme \(3\cdot(1\cdot2\cdot o + 1\cdot2\cdot s) = 2^n\), z čoho ale vyplýva, že číslo \(2^n\) by malo byť deliteľné tromi. To ale nie je pravda, lebo v prvočíselnom rozklade má len dvojky. Takže nám z tohto vyplýva, že \(a\),\(b\) nemôžu byť naraz obidve väčšie ako \(2\).
Teraz sa pozrime na prípad, že BUNV 1 \(a \geq 4\), \(b < 3\). Pre \(b = 2\) dostaneme rovnicu \(a! + 2! = 2^n\), túto môžeme predeliť \(2\). Dostaneme \(\frac{a!}{2} + 1 = 2^{n-1}\). O \(\frac{a!}{2}\) vieme, že je párne, keďže obsahuje ešte minimálne \(4\)-ku v rozklade na súčin. Z toho vyplýva, že \(\frac{a!}{2}+1\) je nepárne, a teda sa nemôže rovnať \(2^{n-1}\) (\(2^{n-1}\) je nepárne len keď \(n = 1\), čo nemá žiadne riešenie, lebo súčet dvoch prirodzených čísel je minimálne \(2\)). Pre \(b = 1\) tiež nesedí parita, dokonca ak je jedno z čísel \(a\), \(b\) rovné \(1\), tak kvôli parite musí byť aj to druhé \(1\).
Takže sme zistili, že obe \(a,b \leq 3\), ale nemôžu byť obe naraz rovné \(3\), a že keď sa len jedno rovná \(1\) tak to nemá riešenie. Z toho máme \(4\) možné kombinácie \(a\) a \(b\), a to \((1,1)\), \((2,2)\), \((2,3)\) a \((3,2)\). Tieto vieme dosadiť a dostaneme z toho trojice \((1,1,1)\), \((2,2,2)\), \((2,3,3)\) a \((3,2,3)\).
Našli sme štyri trojice \((1,1,1)\), \((2,2,2)\), \((2,3,3)\) a \((3,2,3)\), ktoré spĺňajú našu rovnosť a dokázali sme, že žiadne iné neexistujú.
Bez ujmy na všeobecnosti si môžeme vybrať, ktoré z čísel \(a\), \(b\) je menšie. Ak by to bolo naopak, tak len vymeníme značenie, pretože \(a\), \(b\) hrajú rovnakú úlohu v našej rovnici (rovnica je symetrická vzhľadom na výmenu \(a\), \(b\)).↩︎
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ť.
Hugo Bartha
chcem sa opýtať,že pred asi dvoma dnami som videl video kde týpek dokazuje prečo 0! = 1
toto som v svojom riešení neuvažoval aj keď by tak vznikli 3 nové riešenia. ako je to s tým 0! ?
Marek Murin
Ahoj, 0 nepovažujeme za kladné celé číslo. Keby sme pripustili nulu tak n=0 nedáva riešenie nakoľko a!+b!>1. Ak by a=0 tak 1+b!=2^n a teda napravo máme párne číslo a na ľavo bude párne práve vtedy keď b=1 alebo 0. Teda dokopy 3 nové riešenia. :)