7. príklad - Vzorové riešenie

Označíme si príchute pudingov A, B, C, D, E a F. Pozrime sa teraz na možnosť, keď je počet porotcov deliteľný 5. Teraz môžeme prvým piatim dať postupne príchute ABCDE a toto zopakovať pre každú ďalšiu päticu. V tejto postupnosti pre ľubovoľný puding platí, že nasledujúca aj predchádzajúca štvorica pudingov obsahuje rovnaké pudingy v rovnakom poradí a neobsahuje zvolenú príchuť pudingu.

Pozrime sa teraz na prípad, kde je počet porotcov deliteľný 6. Prvým 6 porotcom dáme postupne príchute ABCDEF a tieto príchute zopakujeme pre každú ďalšiu šesticu. Táto postupnosť vyhovuje zadaniu z rovnakého dôvodu ako pri možnosti s počtom porotcov deliteľnom 5.

Povedzme, že sa počet porotcov dá rozdeliť na 2 úseky, kde dĺžka prvého je deliteľná 5 a dĺžka druhého je deliteľná 6. Teraz sa na tieto úseky môžeme pozrieť ako na 2 rôzne situácie a rozdeliť príchute tak, ako sme si ukázali vyššie. Jediná možnosť, kde sa mohlo toto rozdelenie "pokaziť" je pri porotcoch, ktorí sú na hranici medzi jednotlivými úsekmi. Tam príchute vyzerajú nasledovne ABCDE ABCDEF a ABCDEF ABCDE. Tuto sa pravidlo zo zadania zjavne neporušilo, teda ľubovoľné m, ktoré sa dá zapísať ako súčet 5x a 6y vyhovuje zadaniu.

Pozrime sa, ktoré všetky m sa takto dajú vyskladať. Vyskladať sa dá napríklad m = 20 = 5 \cdot 4, m =21 = 5 \cdot 3 + 6, m = 22 = 5 \cdot 2 + 6 \cdot 2, m = 23 = 5 + 6 \cdot 3 a m = 24 = 6 \cdot 4. Keďže dokážeme vyskladať 5 po sebe idúcich čísel, tak dokážeme vyskladať aj ľubovoľné číslo väčšie ako 24 a to tak, že k jednému z čísel 20 až 24 pripočítame násobok 5. Teda obslúžiť sa dá určite ľubovoľný počet porotcov m, kde m \geq 20. Ostatné m sa dajú vyskladať všetky, okrem 7, 8, 9, 13, 14 a 19. Poďme teda dokázať, že pre tieto počty porotcov sa príchuťe pudingov nedajú rozdeliť podľa zadania.

Keďže príchutí je 6, tak pre m = 7, m = 8 a m = 9 platí, že aspoň 1 príchuť sa bude musieť vyskytovať 2-krát, lebo ak by sa vyskytovala len raz, rozhodcovia by vedeli dostať len 6 pudingov. No ale na to, aby sme vedeli rozhodcom dať 2 pudingy s rovnakou príchuťou, potrebujeme aspoň 2 + 2 \cdot 4 = 10 porotcov, lebo medzi 2 pudingami s rovnakou príchuťou musia byť aspoň 4 iné pudingy. Teda počty porotcov 7, 8 a 9 nevyhovujú zadaniu.

Pre m = 13 a m = 14 sa musí nejaká príchuť vyskytovať medzi pudingami aspoň 3-krát, keby sa každá príchuť vyskytovala 2-krát mali by sme dokopy len 2 \cdot 6 = 12 pudingov. Na to, aby sme rozhodcom vedeli dať aspoň 3 pudingy s rovnakou príchuťou treba aspoň 3 + 3 \cdot 4 = 15 porotcov, lebo medzi 2 pudingami s rovnakou príchuťou musia byť aspoň 4 iné pudingy. Teda počty porotcov 13 a 14 nevyhovujú zadaniu.

Pre m = 19 sa musí nejaká príchuť vyskytovať aspoň 4-krát, lebo keby sa každá príchuť vyskytovala len 3-krát, tak by sme vedeli obslúžiť len 18 porotcov. Na to, aby sme rozhodcom vedeli dať aspoň 4 pudingy s rovnakou príchuťou treba aspoň 4 + 4 \cdot 4 = 20 porotcov, lebo medzi 2 pudingami s rovnakou príchuťou musia byť aspoň 4 iné pudingy. Teda porotcov nemôže byť ani 19.

Odpoveď: Rozdať pudingy Jerguš dokáže pre všetky počty rozhodcov m (väčšie ako 4), okrem 7, 8, 9, 13, 14 a 19.