[bert04]

Ale dałeś jedną godzinę na znalezienie trefnej butelki i jednocześnie tę samą jedną godzinę na swierdzenie zgonu myszki.
Ergo, takie założenie wyklucza sposoby iteracyjne.
Musi być jednorazowa degustacja i szlus.

Teoretycznie można spróbować to zrobić na raz. Zgodnie z zasadą sigma n->x a^n =a^n+1 - 1.

Czyli 1+2+4+8+16+32+64+128+256+512=1023.
Po poprawce mamy 1+2+4+8+16+32+64+128+256+488=1000.
Nadal musimy wykorzystać 10 myszy. I nadal możemy stracić wszystko, jeżeli zatrutych butelek jest więcej niż 9. Ale przy ograniczeniu do 9 zostaje minimum jedna. Maksimum 488, choć oczywiście można zaryzykować i odjąć te nadwyżkowe 23 od innej liczby.

(Edit: nazwijmy to metodą "Gaussową", chyba wiadomo, dlaczego)

---

EDIT: Moje rozwiązanie "binarne" funkcjonuje, jeżeli określimy, że butelek zatrutych jest maksymalnie 9, wtedy w najgorszym przypadku wylewamy 511 (patrz wyżej). Dla 10+ zatrutych butelek jest możliwość, że wszystkie myszy padną. Na ile prawdopodobna, nawet nie chce mi się liczyć. I nawet nie potrafiłbym, statystyka to nie moja działka.

To rozwiązanie zawiera pewien oczywisty błąd, przy 9 martwych myszach zostaje tylko jedna butelka. W podanym przykładzie (0111111111) jest to butelka o numerze 512 (1000000000), cała reszta jest wylewana. Podobnie dla innych rozwiązań, ilość ocalałych butelek będzie potęgą o podstawie 2 a bazie myszy przeżyłych minus jeden (2n-1). Przy czterech martwych myszach, jak w pierwszym przykładzie to byłoby 2^6-1=63.

EDIT 2: ... to dokładnie tyle, co minimalna liczba dla metody "Gaussowej". 1+2+4+8+16+32=63. Natomiast maksymalna liczba to 1000-15=985. Wydaje się więc, że metoda "Gaussowa" w najgorszym przypadku daje takie same wyniki, jak metoda binarna, a w najlepszym pozwala na zachowanie większości zbioru.