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

wystarczy jedno "wazenie" nie zaleznie od ilosci kulek. bierzesz upuszczasz je z takiej samej wysokosci (wszystkie naraz) na jakis miekki material na ktorym bedzie widac odksztalcenie. Tam gdzie wgniecenie jest inne to jest nasza kulka (:D)

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

wystarcza 2 wazenia,

Ja znałem wersje z 9 kulkami gdzie 1 cięższa od innych

staszekpk napisał(a):

wystarcza 2 wazenia,

2 ważenia starczą jak wiemy na pewno że albo jedna jest lżejsza, albo jedna jest cięższa. Jak weźmiemy np. po 3 kulki na szalkę to jak jedna ze stron będzie cięższa to kulka może być po obu stronach

MarekR22 napisał(a):

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.

To ma ogromne znaczenie.

Załóżmy przez chwilę, że mamy osiem kulek.

1. Najpierw ważysz pierwsze trzy i drugie trzy - okazuje się, że nie są równe.
2. Normalnie mając wiedzę, że specjalna kulka jest np. cięższa jesteś ograniczony do trzech kulek. W takim wypadku wystarczy porównać dwie dowolne z tych trzech kulek.
3. Jeśli jednak nie masz tej informacji to jedynie wiesz tyle, że w tych sześciu kulkach jedna jest inna od reszty. Potrzebujesz dodatkowego ważenia by to ustalić.

Na szybko myśląc to intuicyjnie przy kulce odstającą w znaną stronę można odrzucić co ważenie zawsze 2/3 kulek, ale przy kulce odstającej w nieznaną stronę stosując identyczną strategię możemy w pesymistycznym scenariuszu odrzucić jedynie 1/3 kulek (gdy szalki się nie wyrównają wiemy że odstająca kulka jest na którejś szalce, ale nie wiemy której). Więc lepszą strategią jest położenie na obu szalkach po 1/4 kulek, bo wtedy wiemy że czy kulka jest na szalkach czy nie i możemy w pesymistycznym scenariuszu odrzucić 1/2 kulek.

No ale ta intuicja jest niepoprawna, co pokazuje podlinkowany artykuł z wiki xD