Strona główna » Algorytmy » Artykuły » Gorzka Trucizna
 

Gorzka Trucizna

Zagadka

W jednej spośród 1000 butelek słodkeigo napoju znajduje się jedna z bardzo gorzką trucizną. Ile potrzeba łyków, aby odnaleźć tę butelkę? Zakładamy, że gorzki smak jest bardzo wyraźny nawet w bardzo drobnych ilościach.

Rozwiązanie

Odpowiedź

Potrzeba jedynie 10 łyków.

Wyjaśnienie

Prawdopodobnie pierwsza myśl zakłada spróbowanie z każdej butelki napoju oddzielnie. Metoda ta może pozwolić znaleźć napój w pierszym łyku, albo i w ostatnim. Z tego względu należy przyjąć najgorszy możliwy przypadek czyli, że trzeba będzie 1000 razy próbować napoju. Istnieje jednak lepsza metoda na znalezienie skażonej butelki.

Zadanie nie precyzuje co to jest łyk napoju. Można jednak przyjąć, że to spróbowanie bardzo małej ilości napoju, która nie musi pochodzić z jednej butelki. Do spróbowania można przygotować mieszankę z wielu butelek. Gorzki smak trucizny jest bardzo wyraźny, więc można wyczuć go nawet jeśli zostanie rozpuszczony w innej cieczy. Na podstawie tych informacji przejdźmy do rozwiązywania zagadki.

W każdym kroku dzielimy butelki na dwie w miarę równe części (dla nieparzystej ilości jedna grupa będzie miała jedną butelkę więcej). Następnie dla jednej z grup zlewamy po bardzo małej ilości (np. kropelce) z każdej butelki. Jeśli otrzymana mieszanka ma gorzki smak to trucizna musi znajdować się w wybranej grupie, a jeśli nie to w drugiej. Schemat ten powtarzamy tak długo, aż zostanie tylko jedna butelka. Dla pewności będzie można spróbować czy zawiera gorzką truciznę, ale może lepiej nie ryzykować..

W poniższej tabelce zostały przedstawione kolejne kroki algorytmu. W celu znalezienie najgorszego przypadku przyjmujemy, że gdy są dwie nierówne grupy to wybieramy tą o większej ilości elementów.

KrokButelekGrupa 1Grupa 2
11000500500
2500250250
3250125125
41256362
5633231
6321616
71688
8844
9422
10211

Jak widać wystarczy dziesięć kroków, aby znaleźć jedną butelkę z trucizną pośród 1000. Algorytm ten przypomina przeszukiwanie binarne ze względu na dzielenie przedziału poszukiwań na dwa. W tym jednak przypadku zawsze trzeba wykonać 10 kroków!