Matematyka.pl

Wielu z Was pewnie zna wersję zagadki z 12 kulami i 3 ważeniami, gdzie waga innej kuli nie jest znana (może być ciężka lub lżejsza od pozostałych).

Natomiast jest też wersja tej zagadki z 2 ważeniami, również gdy waga innej kuli nie jest znana. Tylko właśnie nie wiem/nie pamiętam, ile kul było w tym wariancie zagadki. 8? 9? 6?

(Z ciekawości - ktoś zna liczbę kul, dla której da się rozwiązań wariant z 4 ważeniami)?

który wariant: ma być stwierdzone czy różna kula jest lżejsza/cięższa
czy nie ?

Powermac, wiki podaje jakiś przykład dla 2 ważeń, ale nie podaje maksymalnej liczby kul, w których można znaleźć inną, tzn.:

The problem has a simpler variant with three coins in two weighings

Tu podają 3, a na pewno można znaleźć rozwiązanie również dla 4. Ja pytam, dla ilu maksymalnie można.

Pasman, nie jestem pewny, o co pytasz. Moje pytanie dotyczy takiej zagadki: jedna kula ma inną wagę, ale nie wiadomo, jaką. Rozwiązanie ma jedynie wskazać, która kula jest inna, nie musi wcale ustalić, jaką wagę (względem innych) ma ta inna kula.

proponuję takie rozwiązanie:
kula o dowolnym numerze może mieć masę "większą" lub "mniejszą".
układ n kul ma wobec tego 2n stanów.
waga daje 3 wyniki, wobec tego przy k pomiarach ma \(\displaystyle{ 3^k}\) stanów.

wobec tego musi być spełniona nierówność:
\(\displaystyle{ 3^k >= 2n}\)

warunek ten jest konieczny, natomiast niekoniecznie wystarczający.

Zauważmy, że jednym ważeniem można znaleźć intruza wśród maksymalnie trzech (bierzemy dwie. Jak różnią się masą to sprawa jest jasna, jeśli nie - to ta trzecia. Tym tropem dzień doszedłem, że możemy przy dwóch ważeniach zlustrować nawet siedem monet ( bierzemy 3 na szalkę jedną trzy na drugą i jeśli szalki są nierówne redukujemy zadanie do problemu z jednym ważeniem. Jeśli nie-winna jest niezbadana kula. Jest rekurencja
\(\displaystyle{ k_{1} =3}\)
\(\displaystyle{ k_{n+1}=2k_{n} +1}\)

Jak przy trzech kulkach zrobisz jedno ważenie i wyjdzie nierówno, to jak wskażesz "intruza"? Nie wiesz przecież czy jest on lżejszy, czy cięższy od reszty.

pasman pisze:warunek ten jest konieczny, natomiast niekoniecznie wystarczający.

To znaczy, że to jest górne ograniczenie maksymalnej liczby kul, wśród których można znaleźć intruza? Czyli dla 2 ważeń wiemy na pewno, że maksymalna liczba kul jest \(\displaystyle{ \Leftarrow \frac{ 3^{2} }{2} = \frac{9}{2}}\), czyli jest ona niewiększa niż 4? Bo jeśli tak, to dla 4 na pewno da się rozwiązać, czyli szukaną przeze mnie wartością byłoby 4.