Zagadka tygodnia
Mamy do dyspozycji dwie identyczne szklane kule oraz jeden 100-piętrowy budynek. Wiadomo, że spadając na ziemię z poziomu pewnej określonej kondygnacji (i wszystkich co znajdują się wyżej), kula się roztrzaskuje. Fatalnym może się okazać upadek zarówno z pierwszego, jak i z setnego piętra.
Pytanie: ile razy trzeba zrzucić kulę, by jednoznacznie ustalić piętro, poczynając od którego ona się rozbija?
Można oczywiście sprawdzać wszystkie piętra po kolei, poczynając od pierwszego. Wówczas maksymalna liczba prób wynosi 99.
Można też uciec się do bisekcji, tj upuścić kulkę z 50 piętra, tym samym obniżając liczbę prób do 50.
Wreszcie można zastosować taką strategię: rzucać pierwszą kulkę z 10, 20, 30, ... piętra, a następnie, po tym jak się rozleci, za pomocą drugiej sprawdzać poprzednie 9 pięter. To daje nam max. 19 rzutów. W najgorszym przypadku, gdy poszukiwany poziom znajduje się pod numerem 99.
Nieźle.
Ale! istnieje lepsze rozwiązanie. Jakie?