Gorzka Trucizna

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.

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!