Jak na wyświetlaczu

* Wydział Matematyki, Informatyki i Mechaniki, Uniwersytet Warszawski

Redaktorka autorskiego działu Deltoid, który ukazywał się w Delcie w latach 2009–2019.

W artykule Kto da mniej? z \(\Delta^{10}_{17}\) 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. \(\square\)

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 \(1\;111\;111\;111\) monet, gdyby były prawdziwe, ważyłoby \(11\;111\;111\;110\) gramów, a z odważniczkiem waga wyświetlałaby wynik \(11\;111\;111\;111\) gramów.

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

Ogólniej, \(n\)-ta 1 od końca zmienia się na \({\textcolor{#E60046}{\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 \({\textcolor{#E60046}{\mathbf{2}}}\), liczone od prawej strony, to numery fałszywych worków. \(\square\)

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+\ldots+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.

Wielomian \(w(x)\) to wyrażenie postaci
\(a_nx^n+a_{n-1}x^{n-1}+\ldots\) \(+a_1x+a_0\),
gdzie \(n\) jest ustaloną liczbą całkowitą nieujemną, współczynniki \(a_0, a_1, a_2, \ldots, a_n\) są ustalonymi liczbami oraz \(a_n \neq 0\). Za \(x\) można podstawiać dowolne liczby rzeczywiste i wyznaczać w ten sposób wartości wielomianu. Na przykład wielomian \(w(x) = 4 x^3 + 17 x + 2\) dla \(x=1\) przyjmuje wartość \(w(1) = 4+17+2=23\).

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}+\ldots+a_2+a_1+a_0 =k.\] Oznacza to, że każdy ze współczynników \(a_i\) (dla \(i=0,1,\ldots,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}+\ldots+a_2 \cdot(10^m)^2+a_1\cdot 10^m +a_0 =\] \[= a_n \cdot10^{mn}+a_{n-1}\cdot 10^{m(n-1)}+\ldots+a_2 \cdot10^{m\cdot2}+a_1 \cdot10^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) = 4 x^3 + 17 x + 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) =\) \({\textcolor{#E60046}{4}} \cdot 100^3 + {\textcolor{#E60046}{0}} \cdot 100^2 + {\textcolor{#E60046}{17}} \cdot 100 + {\textcolor{#E60046}{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:

Czytelników Zaawansowanych zachęcam do zastanowienia się nad wariantem tej samej zagadki, w którym Jaś może pytać o wartości wielomianu dla dowolnych liczb, niekoniecznie tylko całkowitych.

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. \(\square\)

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.