Opravovatelia

Baška [email protected]

Mišo M. [email protected]

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$.}$, 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$.