Úloha 5.u2: Rušičky (5 b)

Zadáno v čísle 24.5.

Řešeno v čísle 24.7.

Zadání

Máme 32 očíslovaných krabiček, z nichž 16 obsahuje rušičku. Každý den můžeme vzít libovolnou sadu krabiček a otestovat, zda je mezi nimi alespoň jedna rušička. Za kolik dnů dokážeme určit, které krabičky obsahují rušičky? Zajímá nás jak nejhorší případ, tak i průměr. Část bodů je možné získat i za neoptimální řešení; naopak třeba důkaz toho, že to nejde o moc rychleji, představuje možnost získat bonusové body.

Řešení

Vypadá to, že příslib části bodů za neoptimální řešení nestačil a nenalezení optimálního řešení odradilo velkou část řešitelů. Což je celkem škoda, protože nalezení optimálního řešení opravdu nebylo zapotřebí. Níže jsou různá pozorování, která bylo možno učinit, setřízená přibližně od nejsnadnějších po nejsložitější. Za každé z nich bylo možné získat nějaké body.

Je zjevné, že v nejlepším případě se nám může podařit celý úkol vyřešit za jediný den – stačí nám mít to štěstí vybrat 16 krabiček a pak zjistit, že mezi nimi rušička není. Vzhledem k tomu, že možností, jak vybrat 16 krabiček z 32, je ${32 \choose 16}~ =~ 601\; 080\; 390$, a jen jedna z nich je ta správná, není dobrý nápad na to spoléhat.

Druhé celkem základní pozorování je, že to určitě můžeme vyřešit za nejhůře 31 dnů: Každý den zkusíme jednu krabičku a tu poslední už odvodíme podle toho, zda nám schází šestnáctá rušička, nebo prázdná krabička.

31 dnů se možná nezdá jako moc dobrý výsledek, ale je možné ukázat, že to zase o tolik lépe nepůjde. Existuje 601 080 390 možných rozdělení krabiček mezi ty s rušičkou a ty bez. Vzhledem k tomu, že se každý den dozvíme jen to, zda mezi námi vybranými krabičkami byla alespoň jedna rušička, nebo ne, tak si to taky můžeme představit tak, že výběrem podmnožiny krabiček pro měření rozdělujeme všechna možná rozmístění rušiček do dvou hromádek podle toho, jaký výsledek dávají při našem měření. Po provedení měření pak jednu z těchto hromádek můžeme vyřadit a celý proces opakovat, dokud nám nezbude jen jedno možné rozmístění rušiček.

Je snadné nahlédnout, že pokud budeme mít smůlu, tak vždy vyřadíme tu menší hromádku. Pro minimalizaci nejhoršího případu chceme tedy dělit na poloviny. Opakovaným dělením čísla 601 080 390 zjistíme, že i kdyby se nám to dokonale dařilo, stejně se nám může stát, že budeme potřebovat 30 měření.

Opatrnější formulace předchozího argumentu (ať už rozmyšlením si toho, že půlení optimalizuje i průměrný případ, nebo přes teorii informace) pak vede k dolnímu odhadu $\log _2 601\; 080\; 390$, tedy přibližně 29,16 dne na průměrný případ.

Když se zamyslíme nad možnými průběhy našeho testování krabiček po jedné, tak si všimneme, že nejen že dokážeme vždy „uhodnout“ poslední krabičku, ale občas bude předem jasné, jak dopadne několik posledních krabiček. Z 601 080 390 rozložení rušiček má $2{30 \choose 16}$ stejné poslední dvě krabičky, a tudíž budeme moci předem určit, jaké ty dvě krabičky budou. Pokud takhle uvážíme všechny možné počty stejných krabiček na konci, tak snížíme námi dosažený průměrný případ pod 30,18, tedy na méně než 1,2 dne navíc oproti teoretickému optimu.

Domnívám se, že tento rozdíl se dá zmenšit. Možná existuje lepší postup a téměř určitě se dá zvýšit ten dolní odhad. Pokud by si s tím někdo z vás chtěl ještě chvilku hrát a našel zajímavé zlepšení, tak to prosím zkuste sepsat a pošlete nám to – dostanete za to od nás na soustředění čokoládu.

Matej