Wyobraź sobie, że jesteś w wysokim budynku z kotem. Kot może przetrwać upadek z okna na niskim piętrze, ale zginie, jeśli zostanie wyrzucony z wysokiego piętra. Jak obliczyć najdłuższy spadek, jaki kot może przeżyć, przy jak najmniejszej liczbie prób?
Oczywiście, jeśli masz tylko jednego kota, możesz wyszukiwać tylko liniowo. Najpierw wyrzuć kota z pierwszego piętra. Jeśli przeżyje, rzuć go od drugiego. W końcu po wyrzuceniu z piętra f kot umrze. Wtedy wiesz, że podłoga f-1 była maksymalną bezpieczną podłogą.
Ale co, jeśli masz więcej niż jednego kota? Możesz teraz spróbować jakiegoś wyszukiwania logarytmicznego. Powiedzmy, że budynek ma 100 pięter i masz dwa identyczne koty. Jeśli wyrzucisz pierwszego kota z 50 piętra i zginie, to wystarczy przeszukać 50 pięter liniowo. Możesz zrobić to jeszcze lepiej, jeśli za pierwszym podejściem wybierzesz niższe piętro. Powiedzmy, że zdecydowałeś się rozwiązać ten problem na 20 piętrach naraz, a pierwsze fatalne piętro ma numer 50. W takim przypadku twój pierwszy kot przetrwa loty z piętra 20 i 40, zanim umrze z piętra 60. Wystarczy sprawdzić indywidualnie piętra od 41 do 49. To w sumie 12 prób, co jest znacznie lepsze niż 50, których potrzebowałbyś, gdybyś próbował użyć eliminacji binarnej.
Ogólnie rzecz biorąc, jaka jest najlepsza strategia i najgorsza złożoność w przypadku n-piętrowego budynku z 2 kotami? A co z n podłogami i m kotami?
Załóżmy, że wszystkie koty są równoważne: wszystkie przeżyją lub zginą w wyniku upadku z danego okna. Ponadto każda próba jest niezależna: jeśli kot przeżyje upadek, nic mu nie stanie.
To nie jest praca domowa, chociaż być może kiedyś rozwiązałem ją do zadania szkolnego. To tylko kapryśny problem, który przyszedł mi do głowy dzisiaj i nie pamiętam rozwiązania. Dodatkowe punkty, jeśli ktoś zna nazwę tego problemu lub algorytm rozwiązania.