6. Kaligulove Márnotratné Sporky vzorové riešenie

Pozrime sa najprv, ako vieme manipulovať s cenami, ktoré vieme zaplatiť. Vezmime si dve také ceny – \(x\) a \(y\) a pozrime sa, čo ďalšie vieme zaplatiť. Napríklad vieme zaplatiť ľubovoľný ich násobok. Na zaplatenie \(k \cdot x\) nám stačí dať z každej mince \(k\)-krát viac predavačovi a on nám zas z každej \(k\)-krát viac vydá. Podobne vieme zaplatiť súčet a rozdiel. Na zaplatenie \(x+y\) použijeme všetky mince na zaplatenie \(x\) a \(y\) dokopy a predavač nám dokopy vydá. Vieme zaplatiť aj \(x-y\). Tu prebehne výmena mincí, akoby sme my platili predavačovi \(x\) a on nám \(y\).

Na prvý bod zadania sa nám najviac zíde odčítanie. Keďže nevieme zaplatiť hodnotu \(c\), isto nevieme zaplatiť ani dve hodnoty s rozdielom \(c\). Ako ich nájsť nekonečne veľa? Vezmime si napríklad násobky \(c\). Dva po sebe idúce majú vždy rozdiel \(c\). Jeden z nich teda zaplatiť nevieme. To nám dáva „polovicu“. Keďže násobkov \(c\) je nekonečne veľa, bude nekonečne veľa aj tých, ktoré zaplatiť nevieme.

Prejdime k druhému bodu. Tentokrát sa nám zíde násobenie. Ak totiž vieme zaplatiť \(1\), určite vieme zaplatiť jej ľubovoľný násobok, a teda všetky možné ceny. Stačí nám teda \(b\) zvoliť tak, aby sme vedeli zaplatiť \(1\) a nemusíme riešiť, čo je \(c\) zač. Takáto voľba je napríklad nahradenie \(a_2\) za hodnotu \(a_1+1\). Tu nám dokonca budú stačiť mince \(a_1\) a \(b\) na zaplatenie čohokoľvek.

Iné riešenie (využívajúce Bezoutovu rovnosť).

Bezoutova veta je mocný nástroj, ktorý v podstate priamo určuje, ktoré ceny vieme a ktoré nevieme zaplatiť pre nejakú dvojicu platidiel. Dá sa však priamo indukciou zovšeobecniť, čím dostaneme riešenie našej úlohy. Začnime tým, čo hovorí Bezoutova rovnosť:

Pre každé \(a,\,b \in \mathbb{Z}\) existujú nenulové \(k,\,l \in \mathbb{Z}\) také, že \[k \cdot a + l \cdot b = d,\] kde \(d\) je najväčší spoločný deliteľ \(a,b\). Navyše \(d\) je najmenšie kladné číslo, pre ktoré vieme takéto \(k,\,l\) nájsť.

My máme k dispozícii čísel \(10\), nie len dve. Fakt, že \(k,\,l\) berieme aj záporné, súhlasí s tým, že nám predavač môže vydať. Indukciou ukážeme, ako pridať ďalšie číslo. Majme \(n\) čísel \(a_1,\, a_2,\, \ldots,\, a_n\) s najväčším spoločným deliteľom \(d_n = k_1 a _1 + k_2 a _2 + \ldots + k_n a_n\). Keď pridáme \(a_{n+1}\), vieme isto zapísať najväčšieho spoločného deliteľa \(d_n\) a \(a_{n+1}\) ako \(k \cdot d_n + l \cdot a_{n+1}\), pre vhodné \(k,l\). Platí \[k \cdot d_n + l \cdot a_{n+1} = (k \cdot k_1) a_1 + (k \cdot k_2) a_2 + \ldots + (k \cdot k_n) a_n + l \cdot a_{n+1},\] odkiaľ dostaneme nové koeficienty. Takto zapísané číslo bude skutočne najväčší spoločný deliteľ \(a_1, a_2, \ldots, a_{n+1}\). Keďže delí \(d_n\) aj \(a_{n+1}\), je to spoločný deliteľ všetkých čísel, a keďže nič väčšie nedelí \(d_n\) aj \(a_{n+1}\), nemôže nič väčšie deliť ani \(a_1,\, a_2,\, \ldots,\, a_{n+1}\).

My teda budeme pracovať s verziou Bezoutovej rovnosti pre \(10\) čísel. Pre úplnosť ľahko overíme, že žiadnou voľbou \(k_1,\, k_2,\, \ldots,\, k_{10}\) nedostaneme kladné číslo menšie ako ich najväčší spoločný deliteľ – \(d\). Ten delí všetky čísla v našom súčte, takže bude deliť aj výsledný súčet. A najmenší kladný násobok \(d\) je \(d\) samotné.

Takto upravená veta už priamo rieši našu úlohu. Ceny, ktoré sú násobkom \(d\), isto dokážeme zaplatiť. Ak teda máme nejaké \(c\), ktoré zaplatiť nevieme, určite \(d \neq 1\). Preto nevieme zaplatiť čísla so zvyškom \(1\) po delení \(d\), ktorých je nekonečne veľa. V druhom bode nám naopak stačí spraviť výmenu, aby výsledné platidlá mali najväčší spoločný deliteľ rovný \(1\). Vyhovuje jednak \(b = a_1 + 1\), ale aj \(d_9 + 1\), kde \(d_9\) je najväčší spoločný deliteľ \(a_1,\, a_2,\, \ldots,\, a_9\).