[żeniec]

Zara, zara, skoro

... Możemy to zrobić za pomocą testowych myszek.
... Jaką minimalną liczbę myszek trzeba poświęcić,

to dammy miał rację.

A nawet lepiej, przy dozie szczęścia może się obyć bez ofiar.
Bierzemy 999 myszek (ich liczba nie została ograniczona) i każdej dajemy spróbować z jednej butelki.
Padnie jedna lub żadna (gdyby zatruta była akurat ta 1000 butelka).

Chyba że znowy czegoś nie doczytałem

Warunek globalny to nie zabicie nikogo z gości. Mógłbym to powtarzać w każdym zdaniu, ale jest to nieestetyczne. Pytanie więc domyślnie brzmi "Jaką minimalną liczbę myszek trzeba poświęcić (wykorzystać, licząc się z tym, że być może wszystkie umrą), aby z pewnością namierzyć butelkę z zatrutym winem"

---

Jeżeli brać zadanie ultra-dosłownie, to jest ono niewykonalne. Po wyrzuceniu jednej butelki mamy ich 999, więc cel podania 1000 butelek wina jest nieosiągalny.

Jeśli brać jedno zdanie ultra-dosłownie i nie czytać reszty zagadki, to tak

Oczywiście można zadanie przekształcić w "1000 minus te zatrute".

To jest oczywiste dla jednej butelki, ale przestaje być dla liczby nieokreślonej. Wariant jednowymiarowy (999 myszek) prowadzi do dokładnego namierzenia, ale też do maksymalnej liczby ofiar. W wariantach wielowymiarowych możemy ustalić, że wylewamy całą "płaszczyznę" sprawdzania, jeżeli jedna mysz zdechnie. Przy odrobinie szczęścia pozostanie nam parę butelek, które nie były w jakimś podzbiorze zatrucia. Przy odrobinie pecha wylewamy wszystko i kupujemy 1000 butelek na allegro. Ale tu bez podania jakichś górnych pułapów zatrucia vs. wyrzucania trudno o optymalizację.

Ano, zagadka dla dowolnej ustalonej liczby butelek robi się dużo trudniejsza. Jeśli natomiast zawczasu nie znamy liczby zatrutych butelek i mamy mieć pewność, że znaleźliśmy wszystkie, to chyba znowu robi się już prosto.

Co do namierzania w pierwszym wariancie, to nie ma problemu, jeżeli tylko jakoś ponumeruje się butelki, choćby właśnie w systemie dwójkowym, a bity przyporządkowuje się myszom. Bardziej "konstrukcyjnie" wyobrażałem to sobie tak, że mam odcinek ponumerowanych butelek, dzielimy go na dwa równe odcinki (no, z dokładnością do jednej butelki) i butelki z jednego odcina dajemy do posmakowania pierwszej myszce. W kolejnym kroku bierzemy te dwa odcinki i w każdym z nich robimy to samo, tzn. dzielimy na, powiedzmy, lewą i prawą połowę, i lewe połowy dajemy kolejnej myszce. Kontynuujemy aż odcinki są 1-elementowe lub puste.