8 kulek i waga szalkowa

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)?

Hm wydaje mi się że będzie potrzebne dodatkowe ważenia, jeśli wyjdzie ci np że jedna strona jest cięższa, to są 2 warianty:
1 parzysta ilość kulek na jednej szalce = dajesz po połowie, i jak mają równą masę to wtedy wiesz że jak ta strona była lżejsza to dodatkowa kulka jest cięższa i na odwrót (a jak mają równą to znaczy że ważenie pokazało czy jest cięższa czy lżejsza
2 nieparzysta ilość, jedną odkładasz na bok, jak wyjdzie po tyle samo to zamieniasz "nadmiarową" na dowolną inną, jak wyjdzie inaczej to dodatkowa jest "inna" , a jak tyle samo to znaczy że jeśli wiozłeś na początku lżejszą połowę to cięższa kulka jest w tej drugiej, i na odwrót.
wydaje mi się że w najgorszym przypadku dojdzie ci 4 dodatkowe ważenia (2 ważenia w dla jednej połówki początkowej, wyjdzie że nie ta i dodatkowe 2 dla drugiej).

http://www.matemaks.pl/zagadki.php zagadka 4
Da się to rozwiązać w trzech ważeniach. Ta wersja zagadki jest popularna, więc może gdzieś znajdziesz analizę.

To że nie wiadomo czy jedna kula jest cięższa czy lżejsza ma niewielki wpływ na złożoność obliczeniową, bo to można ustalić już po drugim ważeniu.

OFFTOPIC:
Wczoraj widziałem fajną zagadkę, na National Geographic (program "Zagadki Umysłu"):
W pokoju są 3 przełączniki w stanie wyłączonym, w sąsiednim są 3 żarówki każda podłączona do jednego przełącznika. Żarówek nie widać z poza pokoju, w którym są.
Przechodząc TYLKO RAZ z pokoju z przełącznikami do pokoju z żarówkami, przypisz każdej żarówce pasujący do niej przełącznik.

Bardzo stara zagadka... Nie będę odbierał radości innym podając rozwiązanie :D

Afish napisał(a):

http://www.matemaks.pl/zagadki.php zagadka 4
Da się to rozwiązać w trzech ważeniach. Ta wersja zagadki jest popularna, więc może gdzieś znajdziesz analizę.

Znalazłem :]
http://en.wikipedia.org/wiki/Balance_puzzle
W podlinkowanym PDFie jest wszystko wytłumaczone: http://math.uni.lodz.pl/~andkom/Marcel/Kule-en.pdf