Táto úloha je voľným pokračovaním úlohy Otrávené víno.
Veľmi múdry ale mierne krutý panovník sa dozvedel, že jeden z jeho 2000 sudov vína je otrávený. Účinok jedu sa prejaví do jedného mesiaca (za deň alebo aj za mesiac), pričom ho stačí vypiť iba kvapku.
O dva mesiace 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
V úlohe Otrávené víno sme vzťah ochutnávač – sud vyjadrili zápisom čísla sudu v dvojkovej sústave, mali sme dva stavy pre ochutnávača: prežil a zomrel. Pre 1000 sudov a jeden mesiac nám stačilo 10 ochutnávačov. Preto by sme týmto spôsobom mohli použiť 10 ochutnávačov a ak do mesiaca všetci prežijú použiť ich na druhých 1000 sudov.
Čo ak máme menej ako 10 ochutnávačov.
Máme tri stavy: prežil (0), zomrel do mesiaca (1) a zomrel v druhom mesiaci (2), ponúka sa trojková sústava.
Na zápis čísla 2000 v trojkovej sústave nám stačí 7 číslic, \(2000_{10}=2202002_3\), teda bude nám stačiť 7 ochutnávačov. Pretože \(2222222_{3}=2186_{10}\), 7 ochutnávačov by stačilo pre 2186 sudov (+1 pretože, jeden sud je určite otrávený a jeden sud testovať netreba).
Napríklad sud číslo 1317 budú testovať:
- Ochutnávač č. 2 na začiatku 1. mesiaca.
- Ochutnávač č. 3 na začiatku 2. mesiaca.
- Ochutnávač č. 5 na začiatku 1. mesiaca.
- Ochutnávač č. 6 na začiatku 2. mesiaca.
- Ochutnávač č. 7 na začiatku 1. mesiaca.
Pretože \(1317_{10}=1210210_3\). Význam číslic stúpa zprava doľava, preto aj ochutnávačov číslujeme takto.
Ak by napríklad zomreli iba ochutnávači č. \(5\) a č. \(6\) v prvom mesiaci a č. \(2\) a č. \(3\) v druhom mesiaci, znamenalo by to, že otrávený je sud č. \(348\), pretože (\(110220_3 = 348_{10}\)).
Nasledujúca tabuľka ukazuje ako by to fungovalo pri dvoch ochutnávačoch a deviatich sudoch.
Ak by ochutnávač č. 1 zomrel v prvom mesiaci, tak to či (a kedy) zomrie ochutnávač č. 2 určí, ktorý sud je otrávený. Napríklad, ak nezomrie, tak je otrávený sud č. 1.
| Číslo suda (desiatková sústava) | Číslo suda (trojková sústava) | Popis – kto a kedy testuje daný sud |
|---|---|---|
| 0 | 00 | Sud sa netestuje. |
| 1 | 01 | Ochutnávač č. 1 na začiatku 1. mesiaca. Ochutnávač č. 2 tento sud netestuje. |
| 2 | 02 | Ochutnávač č. 1 na začiatku 2. mesiaca. Ochutnávač č. 2 tento sud netestuje. |
| 3 | 10 | Ochutnávač č. 1 tento sud netestuje. Ochutnávač č. 2 na začiatku 1. mesiaca. |
| 4 | 11 | Ochutnávač č. 1 na začiatku 1. mesiaca. Ochutnávač č. 2 na začiatku 1. mesiaca. |
| 5 | 12 | Ochutnávač č. 1 na začiatku 2. mesiaca. Ochutnávač č. 2 na začiatku 1. mesiaca. |
| 6 | 20 | Ochutnávač č. 1 tento sud netestuje. Ochutnávač č. 2 začiatku 2. mesiaca. |
| 7 | 21 | Ochutnávač č. 1 na začiatku 1. mesiaca. Ochutnávač č. 2 na začiatku 2. mesiaca. |
| 8 | 22 | Ochutnávač č. 1 na začiatku 2. mesiaca. Ochutnávač č. 2 na začiatku 2. mesiaca. |
Pretože v trojkovom zápise čísla sa striedajú číslice \(0\), \(1\) a \(2\) pravidelne, tak zomrie približne \(66,66\%\) ochutnávačov. Pri sudoch očíslovaných od \(1\) do \(2000\) je v trojkových zápisoch \(9 164\) číslic \(1\) alebo \(2\).
|
1 2 3 4 5 6 7 8 9 |
pocet=0 for i in range(1,2001): while i>0: i, zv = divmod(i,3) if zv>0: pocet+=1 print(pocet) #9164 |
Jeden sud nemusíme testovať, nech je to sud \(1366\). Výber nie je úplne ľubovoľný, v trojkovom zápise musí byť \(7\) nenulových číslic. Takže môžeme očakávať, že v priemere zomrie \(\frac{9164-7}{2000}\approx 4,579\) ochutnávača, čo je asi \(65,407\%\).
Prežitie by šlo ešte vylepšiť použitím prvých 1 999 čísel z 0 až 2 186, ktoré majú v trojkovom zápise najmenej 1 a 2 a tiež by sme mohli využiť informáciu, kto prežil a kto nie po prvom mesiaci.