Nie ma podforum dla zagadek więc wrzucam tutaj.
Problem w którym mamy 8 kulek i jedną kulkę cięższą (bądź lżejszą) jest powszechnie znany w Googlu :P
Natomiast ciężko mi znaleźć (tzn słabo szukałem :P ) rozwiązanie dla wariantu gdzie jest 8 kulek i jedna waży mniej lub więcej, tzn nie wiadomo w którą stronę jest różnica. Mi wyszło że 3 ważenia wystarczą by wykryć tą kulkę wraz z informacją czy jest lżejsza czy cięższa.
Pytanie główne natomiast jest takie: jaka jest złożoność problemu (tego trudniejszego), tzn dla X kulek jaka jest minimalna liczba ważeń by wykryć kulkę o odstającej wadze?
Dla problemu gdzie wiemy czy kulka jest cięższa czy lżejsza wydaje mi się, że minimalna liczba kroków to sufit(log_3(x)). Pytanie jaka jest liczba kroków dla trudniejszego wariantu (tzn nie wiemy czy odstająca kulka jest cięższa czy lżejsza)?