Zadanie
Po tom, ako sa princ Ákos vrátil z vojny, zistil, že už nemal čo robiť so životom. Aby sa nenudil, dal si zavolať Jakuba, najslávnejšieho dvorného klauna široko-ďaleko. Avšak Jakub už mal tú česť sa s Ákosom spoznať a veľmi dobre si pamätal, že pán uhorský princ je nielen krvilačný, ale aj veľmi náladový. A tak sa stalo, že klaun dnes pre istotu princovi predvádzal iba svoje slávne čísla.
Hovoríme, že prirodzené \(n\)-ciferné číslo také, že \(3 \leq n \leq 9\), je slávne, ak spĺňa tieto dve podmienky:
číslo obsahuje každú cifru od \(1\) po \(n\) práve raz;
pre každú cifru okrem prvých dvoch platí, že dvojnásobok danej cifry je väčší alebo rovný ako súčet dvoch predošlých cifier.
Ukážte, že žiadne štvorciferné číslo, ktoré je slávne, nemá cifru \(4\) ako druhú v poradí.
Zistite, na ktorých pozíciách sa môže nachádzať cifra \(7\) v sedemcifernom slávnom čísle.
Pri riešení mnohých úloh, túto nevynímajúc, je dobré začať jednoduchými pozorovaniami. Skúsme to.
V našom prípade je dobré zamyslieť sa, kde sa v slávnom čísle môže nachádzať cifra \(1\). Vieme, že \(1\)-ka bude v každom čísle, a teda je to pomerne všeobecný fakt, ktorý nám môže pomôcť. Druhé pravidlo nám hovorí, že pre každú z cifier okrem prvých dvoch platí, že jej dvojnásobok je aspoň taký ako súčet dvoch predošlých cifier. Dvojnásobok \(1\)-ky je číslo \(2\). To je vždy menšie ako súčet akýchkoľvek dvoch iných cifier. Z toho vieme, že jednotka bude na niektorom z prvých dvoch miest. Podobne vieme ukázať, že \(2\)-ka musí byť na prvých dvoch miestach alebo za dvojicou \(1, 3\) v ľubovoľnom poradí. V tomto momente by sme mohli pokračovať s ďalšími ciframi, no my namiesto toho skúsime naše pozorovania využiť.
Prvé zistenie nám veľmi pomôže v časti \(a)\). Ak má byť totiž v štvorcifernom čísle \(4\)-ka druhá, tak cifra \(1\) musí byť na prvom mieste. Ostali nám tak len dve možné čísla – \(1423\) a \(1432\). Ľahko overíme, že ani jedno z nich nie je slávne: v prvom \(2 \cdot 2 < 1 + 4\), zatiaľ čo v druhom \(2 \cdot 2 < 4 + 3\).1
Na úvod riešenia časti \(b)\) je dôležité povedať, že ak pre ľubovoľnú pozíciu nájdeme jedno číslo, ktoré je slávne, iné nám hľadať netreba. Zatiaľ čo ak chceme ukázať, že také neexistuje, potrebujeme to ukázať pre všetky možné čísla. Overme postupne každú pozíciu.
Ak by sa cifra \(7\) mala nachádzať na prvom mieste, za ňou musí byť podľa pozorovania \(1\)-ka. Otázka je, kam môžeme dať \(2\)-ku. Tá už nemôže byť na prvých dvoch miestach, teda ostala len možnosť, že je za dvojicou \(1, 3\). Vieme, že \(1\)-ka je druhá. Z toho musí byť \(3\)-ka na treťom mieste, inak pre \(2\)-ku miesto nenájdeme. Lenže \(2 \cdot 3 < 1 + 7\), takže aj táto možnosť nás vedie k sporu. \(7\)-ka preto na prvej pozícii byť nemôže.
Obe naše pozorovania využijeme aj pre prípad, že by \(7\)-ka bola na druhej pozícii. \(1\)-ka potom musí byť prvá a \(2\)-ku už nemôžeme dať nikam. Teda ani na druhej pozícii \(7\)-ka nebude.
Pre tretiu pozíciu ľahko overíme, že na prvých dvoch musí byť \(1\)-ka aj \(2\)-ka. Kam ale teraz dáme \(3\)-ku? Na štvrtej pozícii byť nemôže a ani na žiadnej ďalšej, lebo jej dvojnásobok je vždy menší ako súčet dvoch čísel, ktoré sú od nej väčšie.2 Takže zase nič.
Ak dáme \(7\)-ku na štvrté miesto, aké číslo môže byť hneď za ňou? Môže to byť len číslo väčšie ako \(4\). Prečo? Dvojnásobok menších čísel je menší ako \(7\). Pre \(4\)-ku to tak nie je, lenže to by musela byť presne pred sedmičkou \(1\)-ka a z pozorovania vieme, že to tak byť nemôže. Preto na piatej pozícii je buď \(5\)-ka alebo \(6\)-ka. Na šiestej pozícii však potom nemôže byť nič menšie ako \(6\), z čoho vyplýva, že máme číslo tvaru \(abc756d\). Lenže \(d\) musí byť opäť aspoň \(6\), čo nie je možné. Teda ani štvrtá pozícia nevyhovuje.
Pre ďalšie pozície nie je náročné3 nájsť slávne čísla. Sú nimi napríklad \(1243756\), \(1234576\) a \(1234567\).
Sedmička sa preto v sedemcifernom slávnom čísle môže nachádzať na piatej, šiestej alebo siedmej pozícii.
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ť.