Veľmi múdry ale mierne krutý panovník sa dozvedel, že jeden z jeho 1000 sudov vína je otrávený. Účinok jedu sa prejaví až za takmer jeden mesiac, pričom ho stačí vypiť iba kvapku.
O mesiac chce usporiadať oslavu spojenú (okrem iného) s ochutnávaním svojho vína. Má k dispozícii neobmedzený počet ochutnávačov ale pretože je iba mierne krutý, tak ich obetuje minimálne množstvo.
Koľko ochutnávačov potrebuje? Koľko z nich zomrie?
Koľko minimálne potrebuje ochutnávačov potrebuje, ak ich nemá k dispozícii neobmedzene? Koľko z nich zomrie?
Riešenie
Ak by mal dostatok času, stačil by jeden ochutnávač, ktorý by postupne ochutnal každé víno od 1 až po 999 (víno č. 1000 by nebolo treba testovať) alebo pokiaľ by nezomrel. Za daných podmienok by to ale mohlo trvať až 999 mesiacov.
Ak má aspoň 999 ochutnávačov, dá každému ochutnať jedno víno. Ak zomrie jeden ochutnávač, tak vieme, že otrávené víno je to jeho. Ak nezomrie nik, tak otrávené je víno, ktoré nik netestoval. Tento princíp “netestovania” jedného vína je možné použiť aj v ďalších prípadoch.
Ak by mal iba 64 ochutnávačov, tak naukladá vína do obdĺžnika 27 x 37 (= 999).
37 ochutnávačov označí R1, R2, R3, … R37 (riadky). 27 ochutnávačov označí S1, S2, S3, … S27 (stĺpce).
Ochutnávači označení Ri ochutnajú z každého vína v i-tom riadku. Ochutnávači označení Si ochutnajú z každého vína v i-tom stĺpci. Každý ochutnávač R (S) ochutná 27 (37) vín.
Ak zomrú dvaja ochutnávači (Ry a Sx), tak otrávené víno je v políčku so súradnicami [x, y]. Na obrázku je lokalizované víno v riadku 5 a stĺpci 7. Ak nezomrie nik, tak otrávené je netestované víno.
Ak by mal iba 30 ochutnávačov:
Uloží vína do kocky 10 x 10 x 10.
10 ochutnávačov označí R1, R2, R3, … R10. (Hnedá)
10 ochutnávačov označí S1, S2, S3, … S10. (Zelená)
10 ochutnávačov označí H1, H2, H3, … H10 (H – hĺbka, súradnica z, tyrkysová).
Ochutnávači označení Ri (Si, Hi) ochutnajú z každého vína v i-tej súradnici x (y, z).
Každý ochutná 100 vín. Ak by sme jedno víno netestovali, tak po jednom zo skupiny R, S a H by ochutnali 99 vín.
Ak zomrú traja ochutnávači (Ry, Sx a Hz), tak otrávené víno je v políčku so súradnicami [x, y, z]. Ak nezomrie nik, otrávené je netestované víno.
Dôležité
Zatiaľ bolo ukladanie ľahké, lebo sme sudy ukladali
- do radu [1] až [999], teda v jednom rozmere (dimenzii),
- do obdĺžnika [1, 1] až [37, 27], teda v dvoch rozmeroch,
- do kocky [1, 1, 1] až [10, 10, 10], teda v troch rozmeroch.
Stačí byť troška lenivejší alebo múdrejší a prídeme na to, že sudy s vínom nemusíme ukladať do nejakého útvaru naozaj. Stačí ich označiť súradnicami (napr. [21, 7] alebo [3, 6, 7]) a kľudne môžu ostať tam kde sú – v pivniciach zámku. To je veľmi dobré, pretože v blízkej budúcnosti by sme mali troška problém naukladať ich do požadovaného útvaru.
Ak by mal iba 23 ochutnávačov:
„Umiestni“ vína do 4-rozmerného útvaru 6 x 6 x 4 x 7 = priradí im súradnice [1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 1, 3] až [6, 6, 4, 7]. Je to čosi viac, 1008, niektoré políčka (9) budú prázdne.
6 ochutnávačov označí R1, R2, R3, … R6. 6 ochutnávačov označí S1, S2, S3, … S6.
4 ochutnávačov označí H1, H2, H3, H4. 7 ochutnávačov označí N1, N2, N3, … N7.
Ochutnávači N ochutnajú po \(6^2 \times 4 = 144\) vín, ochutnávači H ochutnajú po \(6^2 \times 7 = 252\), ochutnávači R a S ochutnajú po \(6 \times 4 \times 7 = 168\). Samozrejme, mínus prázdne políčka.
Ak zomrú štyria ochutnávači, tak otrávené víno je rovnako ako v predchádzajúcich prípadoch v políčku s ich súradnicami. Ak nezomrie nik, otrávené je netestované víno.
Ak by mal iba 20 ochutnávačov, tak rozmiestni vína do 5-rozmerného útvaru 4 x 4 x 4 x 4 x 4.
Každý ochutnávač vyskúša \(4^4 = 256\) vín. Samozrejme, mínus prázdne políčka.
Ak zomrú piati ochutnávači, tak otrávené víno je rovnako ako v predchádzajúcich prípadoch v políčku s ich súradnicami. Ak nezomrie nik, otrávené je netestované víno.
Ak by mal iba 10 ochutnávačov, tak vytvorí z vín 10-rozmerný útvar 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2.
Každý ochutnávač vyskúša \(2^9 = 512\) vín. Samozrejme, mínus prázdne políčka.
Ak zomrú desiati ochutnávači, tak otrávené víno je v políčku s ich súradnicami. Ak nezomrie nik, otrávené je netestované víno.
10 je minimálne množstvo ochutnávačov, ktorí môžu otestovať za daných podmienok 1000 vín.
Popísané ukladania sú snáď ľahko pochopiteľné ale pri vyšších dimenziách nie sú vždy optimálne, čo sa týka šetrenia ochutnávačov. Skoro vždy ich zomrie toľko aká je dimenzia útvaru, do ktorého ukladáme vína.
Existuje efektívnejšia metóda, môžeme využiť dvojkovú sústavu.
Napríklad, číslo \(368_{10} = 0101110000_2\). V prípade 1000 sudov musíme použiť 10 ochutnávačov (=10 cifier), pretože 9 ciferným dvojkovým číslom očíslujeme len \(2^9 = 512\) sudov.
Ochutnávač č. i, ochutná víno ak je v dvojkovom zápise čísla suda na i-tom mieste 1.
Teda napr. víno zo suda č. 368 dajú otestovať ochutnávačom č. 5, 6, 7 a 9. (Počítame z pravej strany, od číslic s najmenším významom).
Priradenie ochutnávačov k vínam zobrazuje táto tabuľka.
Ochutnávač č. 1 testuje každé druhé víno (zvyšok po delení 2 je vždy 1).
Ochutnávač č. 2 testuje každú druhú dvojicu vín (zvyšok po delení 4 je vždy 2 alebo 3).
Ochutnávač č. 3 testuje každú druhú štvoricu vín (zvyšok po delení 8 je vždy 4 až 7).
Ochutnávač č. \(i\) testuje každú druhú \(2^{i-1}-\)icu vín (zvyšok po delení \(2^i\) je vždy \(2^{i-1}\) až \(2^i-1\)).
Otrávený sud zistíme opačným postupom:
Ak zomrú napr. ochutnávači č. 3, 7, 9, tak poskladáme číslo \(0101000100_2 = 324_{10}\), t. j. otrávený je sud 324.
Pri takomto postupe zomrie z 10 ochutnávačov v priemere 4,932. (Stačí spočítať jednotky v dvojkovom zápise čísel 1 až 999 a súčet predeliť 1000. Výsledok je aj pomerne ľahko odhadnuteľný – v dvojkovom zápise čísla je v priemere polovica 1.) To je dokonca mierne lepší výsledok než pri ukladaní do 5-rozmerného útvaru pri 20 ochutnávačoch (4,995 \( = {{999 \times 5} \over 1000}\)).
Prečo je táto metóda efektívnejšia než ukladanie do 10-rozmerného útvaru?
Obe predsa používajú 10 ochutnávačov a každý ochutná 512 vín (pri 1 025 vínach).
Pri ukladaní do \(d\)-rozmerného útvaru použijeme vždy v \(d\) ochutnávačov pre každé víno (okrem jedného, ktoré netreba otestovať). Teda pri 10-rozmernom útvare každé víno ochutná 10 ochutnávačov.
Pri dvojkovej sústave použijeme (pri 1 025 vínach)
pre 1 víno žiadneho ochutnávača
pre 10 vín po jednom ochutnávačovi
pre 45 vín po dvoch ochutnávačoch
pre 120 vín po troch ochutnávačoch
pre 210 vín po štyroch ochutnávačoch
pre \({10 \choose k}\) vín po \(k\) ochutnávačoch