Jak na wyświetlaczu

W artykule Kto da mniej? z ${\mathrm{\Delta }}_{17}^{10}$ przedstawiłam następującą zagadkę:

Mamy 10 worków z monetami. W dokładnie jednym z nich wszystkie monety są fałszywe, w pozostałych workach wszystkie są prawdziwe. Prawdziwa moneta waży 10 gramów, a fałszywa 11. Ile ważeń na wadze elektronicznej trzeba wykonać, aby wykryć worek z fałszywymi monetami?

Wystarczy, oczywiście, dziesięć ważeń: po jednej monecie z każdego worka. A nawet o jedno mniej, bo jeśli pierwszych dziewięć monet jest prawdziwych, dziesiąta musi być fałszywa. Można też sprytniej: wziąć na przykład po jednej monecie z pięciu worków i zobaczyć, czy razem ważą one 50 gramów, czy 51. Takie pomysły pozwalają zawężać grupę podejrzanych worków i ograniczyć się do czterech ważeń (zachęcam do sprawdzenia).

Ciągle jednak nie jest to rozwiązanie optymalne, wystarczy bowiem jedno ważenie! Niech na wadze leżą:

Tych 55 monet, gdyby były prawdziwe, ważyłoby $55\cdot 10=550$ gramów. Waga pokazuje wynik o $n$ gramów większy wtedy i tylko wtedy, gdy leży na niej $n$ falsyfikatów. Ostatnia cyfra wyświetlacza wskazuje więc numer szukanego worka. $◻$

Rozważmy teraz ogólniejszą wersję tej samej zagadki:

Mamy 10 worków z monetami. W niektórych workach wszystkie monety są fałszywe, w pozostałych wszystkie są prawdziwe. Prawdziwa moneta waży 10 gramów, a fałszywa 11. Ile ważeń na wadze elektronicznej trzeba wykonać, aby wykryć worki z fałszywymi monetami?

Niestety poprzednia metoda tym razem nie zadziała. Jeśli naszych 55 monet teraz waży np. o 7 gramów za dużo, to falsyfikaty mogą równie dobrze być w workach o numerach 2 i 5, jak i w workach 1, 2 i 4 lub w jeszcze innych.

Nadal jednak wystarczy jedno ważenie. Niech tym razem na wadze leżą:

Tych $1111111111$ monet, gdyby były prawdziwe, ważyłoby $11111111110$ gramów, a z odważniczkiem waga wyświetlałaby wynik $11111111111$ gramów.

Jeśli przykładowo w worku numer 3 są fałszywe monety, to wynik jest o 100 g za duży: $11111111\mathbf{2}11$. Jeśli ponadto np. w worku 7 też są fałszywe monety, mamy jeszcze o ${10}^6$ g więcej: $1111\mathbf{2}111\mathbf{2}11$. Z kolei fałszywa moneta z worka numer 1 daje dodatkowo o 1 g więcej: $1111\mathbf{2}111\mathbf{2}1\mathbf{2}$.

Ogólniej, $n$-ta 1 od końca zmienia się na $\mathbf{2}$ wtedy i tylko wtedy, gdy w $n$-tym worku są fałszywe monety. Waga znów na swoim wyświetlaczu wskazuje odpowiedź, mianowicie: miejsca zajmowane przez $\mathbf{2}$, liczone od prawej strony, to numery fałszywych worków. $◻$

Czytelnik Realista może czuć się słusznie zaniepokojony propozycją ważenia naraz ponad miliarda monet. Szczęśliwie liczbę tę łatwo zredukować, przeprowadzając analogiczne rozumowanie z użyciem systemu dwójkowego zamiast dziesiętnego. Ważymy wówczas już tylko $1+2+2^2+\dots +2^9=1023$ monety, a przeanalizowanie związanych z tym dalszych niewielkich modyfikacji pozostawiam dociekliwym.

Kolejna zagadka, na pierwszy rzut oka zupełnie inna, ma jednak z poprzednią zaskakująco wiele wspólnego.

Jaś i Małgosia grają w następującą grę. Małgosia wymyśla sobie pewien niezerowy wielomian o współczynnikach całkowitych nieujemnych. Jaś może pytać o wartości tego wielomianu dla dowolnie wybranych liczb całkowitych. Wygra, gdy poda cały wzór wielomianu. Czy może tego dokonać? Jeśli tak, ile pytań musi zadać?

Pokażemy, że Jaś jest w stanie poznać cały wielomian już po dwóch pytaniach. Na początek Jaś pyta o $w(1)$ i Małgosia podaje mu wartość $k$, obliczoną ze wzoru $$w(1)=a_n+a_{n-1}+\dots +a_2+a_1+a_0=k.$$ Oznacza to, że każdy ze współczynników $a_i$ (dla $i=0,1,\dots ,n$) jest równy co najwyżej $k$ (bo wszystkie $a_i$ są nieujemne). Niech $m$ będzie liczbą cyfr liczby $k$. Wówczas każdy ze współczynników $a_i$ ma najwyżej $m$ cyfr.

Następnie Jaś pyta o $w({10}^m)$ i poznaje wartość $$w({10}^m)=a_n\cdot ({10}^m{)}^n+a_{n-1}\cdot ({10}^m{)}^{n-1}+\dots +a_2\cdot ({10}^m{)}^2+a_1\cdot {10}^m+a_0=$$ $$=a_n\cdot {10}^{mn}+a_{n-1}\cdot {10}^{m(n-1)}+\dots +a_2\cdot {10}^{m\cdot 2}+a_1\cdot {10}^m+a_0.$$ Okazuje się, że ta liczba pokazuje Jasiowi po kolei wszystkie współczynniki wielomianu $w(x)$, jak na wyświetlaczu. Zobaczmy na przykładzie, dlaczego tak jest.

Powiedzmy, że Małgosia wymyśliła sobie wielomian $w(x)=4x^3+17x+2$. Wówczas $w(1)=4+17+2=23$ i ten wynik poznaje Jaś po pierwszym pytaniu. Wobec tego współczynniki wielomianu są najwyżej dwucyfrowe (bo ich suma to 23). Jaś w drugim pytaniu pyta zatem o $w({10}^2)$. Małgosia oblicza:

$w(100)=$ $4\cdot {100}^3+0\cdot {100}^2+17\cdot 100+2,$ czyli

4 00 00 00

0 00 00

17 00

+ 2

4 00 17 02

i podaje Jasiowi ten wynik. Zauważmy, że powyższe dodawanie zawsze odbywa się bez przenoszenia, bo każdy ze współczynników $a_i$ ma najwyżej $m$ cyfr. Dlatego właśnie Jaś może po kolei odczytać wszystkie współczynniki wielomianu:

Pozostaje zauważyć, że Jaś nie może zagwarantować sobie zwycięstwa po jednym pytaniu. Dla każdej liczby całkowitej $x_1$, o którą mógłby spytać, istnieją bowiem dwa różne wielomiany, które mogła wybrać Małgosia, dające tę samą wartość $w(x_1)$, a więc nierozróżnialne dla Jasia po tym jednym pytaniu. Są to mianowicie: wielomian stały $w(x)=|x_1|+1$ oraz wielomian $w(x)=x+(|x_1|+1-x_1)$, oba niezerowe i o współczynnikach całkowitych dodatnich. Podsumowując, Jaś nie może zapewnić sobie zwycięstwa jednym pytaniem, ale dwoma już tak. $◻$

Na zakończenie proponuję jeszcze jedną zagadkę, w której też można zastosować pomysł wyświetlacza prezentującego poszukiwaną informację.

Złośliwy czarodziej rzucił urok na jedną z 1000 beczek z winem – każdy, kto wypije choćby kroplę, zzielenieje w ciągu doby. Codziennie rano dysponujemy dokładnie 10 dzielnymi (i niezielonymi) rycerzami gotowymi ponieść ryzyko. Ile dni potrzeba, aby wykryć zaczarowaną beczkę?

Warto dodać, że odpowiedź ,,trzy dni” nie jest poprawna, a rozwiązanie zainteresowani odnajdą w tekście wspomnianym na początku niniejszego artykułu.