7. Klaus, Mikuláš, Santa vzorové riešenie

V zadaní sa nám objavuje prečudesná podmienka o počtoch darčekoch, ktoré majú deti vyhliadnuté. Označme si túto podmienku \((\star)\). Čo nám asi chce povedať? Skúste si pohľadať niekoľko \(n\)-tíc čísel \(d_1,\, d_2,\, \dots,\, d_n\) pre rôzne hodnoty \(n\), ktoré podmienku \((\star)\) spĺňajú. Isto si všimnete, že aby podmienka \((\star)\) platila, musia byť počty chcených darčekov veľké. To nám naznačuje, že asi nebude problém rozdať darčeky. Budeme len musieť poriadne zdôvodniť, že je to možné.

Jeden zo spôsobov, ako môžeme ukázať, že darčeky ide rozdať, je opísať priamo postup, ktorým ich má Ježiško rozdať. Skúsme teda celkom priamočiary postup. Ježiško si zoradí deti podľa počtu darčekov, ktorý si želajú. Teda tak, aby platilo \(d_1 \le d_2 \le \dots \le d_n\). V takomto poradí im bude dávať darčeky z tých, ktoré majú jednotlivé deti vyhliadnuté. Presnejšie, keď príde na rad \(i\)-te dieťa, Ježiško mu dá niektorý z jeho vyhliadnutých \(d_i\) darčekov, ktorý ešte nedal inému dieťaťu.

Avšak, bude takéto rozdávanie vždy fungovať? Čo ak sa stane, že prídeme takto k dieťaťu, ktorého všetky darčeky sme dali už iným deťom. Musíme ukázať, že sa niečo takéto nestane. Keď dávame darček \(i\)-temu dieťaťu, rozdali sme už \(i-1\) darčekov. Ak by \(i\)-te dieťa chcelo aspoň \(i\) darčekov, teda \(d_i \ge i\), tak by nám to zaručilo, že by každému dieťaťu ostal aspoň jeden darček.

Skúsme to ukázať sporom. Čo ak by nejaké dieťa, povedzme \(j\)-te v poradí, chcelo \(d_j < j\) darčekov? Pozrime sa, čo sa stane s podmienkou \((\star)\). Vďaka nášmu usporiadaniu vieme, že deti s číslom \(k\) menším ako \(j\) chcú tiež menej ako \(j\) darčekov. Preto \(1/d_k > 1/j\). Z našej podmienky tak dostaneme \[\frac{1}{d_1} + \frac{1}{d_2} + \dots + \frac{1}{d_j} + \frac{1}{d_{j+1}} + \dots + \frac{1}{d_n} \ge \frac{1}{d_1} + \frac{1}{d_2} + \dots + \frac{1}{d_j} > \underbrace{\frac1j + \frac1j + \dots \frac1j}_{j\text{-krát}} = \frac j j = 1.\] Dostali sme teda \(1/d_1 + 1/d_2 + \dots + 1/d_n > 1\), čo je spor. Preto teda pre každé \(i\), \(1 \le i \le n\) platí \(d_i \ge i\) a Ježiško vie darčeky rozdať vyššie opísaným spôsobom.

Riešenie matematickou indukciou

O tom, čo musia spĺňať čísla \(d_1,\, d_2,\, \dots,\, d_n\), sa dá veľa zistiť. Napríklad, že musí existovať dieťa, ktoré chce aspoň \(n\) darčekov. Takéto dieťa si môžeme odmyslieť, lebo ak \(n - 1\) zvyšným deťom rozdáme darčeky, isto odmyslenému dieťaťu ostane nejaký voľný darček. Úloha sa nám zjednodušila, stačí nám ukázať, že možno rozdať ostatným \(n-1\) deťom ich vyhliadnuté darčeky. Podmienka \((\star)\) platí aj po odmyslení dieťaťa. Takto by sme mohli pokračovať v odmyslovaní detí, až kým by nám ostalo len jedno dieťa a darček, ktorý chce. Avšak matematika má na to krásny nástroj, ako takéto postupné odmyslovanie exaktne a jednoducho opísať – matematickú indukciu. Jej použitie nám vie uľahčiť riešenie alebo spisovanie mnohých úloh. Poďme si ukázať, ako ju môžeme použiť.

Úlohu vyriešime matematickou indukciou podľa počtu detí \(n\). Ak máme jedno dieťa, chce aspoň jeden darček a ten mu aj vieme dať. Predpokladajme, že pre nejaké \(k\) vieme darčeky rozdať ľubovoľným \(n = k\) deťom, ktoré spĺňajú podmienku \((\star)\). Majme teraz \(k+1\) detí, pre ktoré platí \((\star)\). Medzi nimi existuje dieťa, ktoré chce aspoň \(k+1\) darčekov (dôkaz prenechávame čitateľovi, je podobný ako v prvom riešení). Pre ostatných \(k\) detí stále platí podmienka \((\star)\), keďže sme z jej ľavej strany len zobrali jeden kladný člen. Preto podľa indukčného predpokladu vie Ježiško rozdať každému z týchto \(k\) detí darček, ktorý chce. Taktiež spomedzi \(k + 1\) darčekov, ktoré chce zvyšné dieťe, existuje niektorý, ktorý ešte žiadne dieťa nedostalo a ten mu vieme dať.

Riešenie cez Hallovu vetu

Skúsenejší riešiteľ si všimne, že túto úlohu môžeme formulovať pomocou teórie grafov¹. Máme graf, v ktorom vrcholy predstavujú deti a darčeky. Hranou spojíme každé dieťa s tými darčekmi, po ktorých túži. V takomto grafe sú rozdelené vrcholy na dve časti – deti a darčeky. Žiadna hrana nespája dva vrcholy z rovnakej časti. Takýto graf sa nazýva bipartitiný. Našou úlohou je ukázať, že v takomto bipartitnom grafe, ktorý spĺňa podmienku \((\star)\) existuje párenie pokrývajúce množinu detí, t. j. taká množina hrán \(M\), že žiadne dve hrany nemajú spoločný vrchol a z každého vrchola z množiny detí vychádza hrana z množiny \(M\).

Problém, kedy takéto párenie existuje je dobre preštudovaný. Opisuje ho Hallova veta², ktorá vraví, že v bipartitnom grafe s partíciami \(A\), \(B\) existuje párenie pokrývajúce všetky vrcholy množiny \(A\) práve vtedy, keď ľubovoľná podmnožina množiny \(A\) má aspoň toľko susedov ako prvkov. Pre vyriešenie úlohy nám teda stačí overiť, či náš graf spĺňa túto Hallovu podmienku. Poďme na to.

Pre spor predpokladajme, že existuje \(k\) takých detí, že počet darčekov, ktoré má každé z nich vyhliadnuté, je menej ako \(k\). Označme si počty darčekov, ktoré tieto deti chcú, ako \(d'_1,\, d'_2,\, \dots,\, d'_k\). Keďže všetky tieto čísla sú menej ako \(k\), platí \[ \frac{1}{d_1} + \frac{1}{d_2} + \dots + \frac{1}{d_n} \ge \frac{1}{d'_1} + \frac{1}{d'_2} + \dots + \frac{1}{d'_k} > \frac kk = 1,\] čím opäť dostávame spor. Preto náš graf spĺňa Hallovu podmienku a podľa Hallovej vety v ňom existuje úplné párenie, čo sme chceli dokázať.