Dwa dni temu odbył się II etap JTM, na którym pojawiło się następujące zadanie:
Niestety nie byłem w stanie dojść do rozwiązania. Wyszedłem oczywiście od najprostszego, liniowego sprawdzenia po kolei wszystkich monet, a potem starałem się znaleźć jakieś bardziej optymalne rozwiązanie. Pomyślałem nad dzieleniem zbioru tych monet na dwa zbiory o tej samej liczbie monet (i ewentualnie pozostałą jedną monetę w przypadku nieparzystej ich wartości wyjściowej) i porównywanie tych dwóch zbiorów na szalce aż do uzyskania stanu nierównowagi. Byłbym wdzięczny za jakąś wskazówkę, jak się w ogóle zabrać do takiego zadania i co jest w nim istotnego, na co warto by było zwrócić uwagę. Z góry dziękuję za pomoc.Wśród \(\displaystyle{ 3^{22}}\) monet dwie są fałszywe, a pozostałe prawdziwe. Wszystkie monety prawdziwe są tej samej wagi, również obie fałszywe są tej samej wagi, ale mniejszej niż waga prawdziwych. Mamy do dyspozycji wagę szalkową. Wyznaczyć najmniejsze \(\displaystyle{ k}\), dla którego istnieje ciąg \(\displaystyle{ k}\) ważeń gwarantujący wykrycie fałszywych monet.
). Bardzo sprytna metoda, nie pomyślałem, że zestaw