Hľadanie ťažšej guličky z 27 rovnako vyzerajúcich
Predstavme si úlohu, kde máme celkovo 27 guličiek rovnakej veľkosti a farby. Z nich je 26 guličiek s identickou hmotnosťou a práve jedna je ťažšia. Naším cieľom je pomocou dvojramenných váh túto ťažšiu guličku nájsť a zároveň zistiť, koľko najmenší počet vážení je na to potrebný.
Teoretický základ – entropia a rozlíšenie výsledkov
Pri riešení takéhoto problému je užitočné využiť koncept entropie, ktorá vyjadruje množstvo informácie potrebnej na identifikáciu jednej položky zo súboru.
- Entropia rovnomerného rozdelenia pre 27 možností je:
H(1/27, …, 1/27) = log2 27 = 3 · log2 3
Toto číslo reprezentuje počet bitov informácie potrebných na jednoznačné určenie ťažšej guličky medzi 27 možnosťami.
Možnosti výsledkov jedného váženia
Pokiaľ použijeme na váženie dvojramenné váhy, každé váženie dáva jeden z troch možných výsledkov:
- ľavá miska je ťažšia,
- pravá miska je ťažšia,
- oba diely váh sú v rovnováhe.
Tým pádom jednému váženiu zodpovedá entropia:
- H(1/3, 1/3, 1/3) = log2 3
Výpočet minimálneho počtu vážení
Pretože každé váženie môže poskytnúť informáciu zodpovedajúcu log2 3 bitov, a pre identifikáciu ťažšej guličky potrebujeme získať 3 · log2 3 bitov informácie, vyplýva z toho, že na vyriešenie problému postačia:
- 3 váženia
Inými slovami, minimálny počet vážení, ktorý zaručí nájdenie ťažšej guličky medzi 27 kusmi, je práve tri.
Praktický význam výsledku a efektivita vážení
Tento výsledok poukazuje na efektívnosť použitia trojveľkostného systému výsledkov váženia oproti jednoduchému binárnemu rozlíšeniu. Teda namiesto tradičného „áno/nie“ rozhodnutia, váženie poskytuje tri možné stavy, čím znižuje potrebný počet krokov na nájdenie ťažšej guličky.
V praxi to znamená, že správnym rozdelením guličiek do skupín a strategickým vážením sa dá presne a rýchlo identifikovať ťažšia gulička bez zbytočného počítania a skúšania.
