LIV OM - II - Zadanie 6

Każdej parze liczb całkowitych nieujemnych $ (x,y) $ jest przyporządkowana liczba $ f (x,y) $ zgodnie z warunkami:

\[<br />
\begin{array}{rcl}<br />
f (0,0) &=& 0;\\<br />
f (2x, 2y) &=& f (2x +1,2y + 1) = f (x, y),\\<br />
f(2x +1,2y) &=& f(2x, 2y +1)= f(x,y) + 1\ \textrm{dla}\ x,y \geq 0.<br />
\end{array}<br />
\]

Niech $ n $ będzie ustaloną liczbą całkowitą nieujemną i niech $ a $, $ b $ będą takimi liczbami całkowitymi nieujemnymi, że $ f (a,b) = n $. Rozstrzygnąć, ile jest liczb $ x $ spełniających równanie

\[<br />
f (a,x) + f (b,x) = n.<br />
\]

Rozwiązanie

Udowodnimy następujący lemat dający inny opis funkcji $ f $.

Lemat

Niech $ k $ będzie liczbą całkowitą dodatnią oraz niech $ x $, $ y $ będą liczbami całkowitymi nieujemnymi mniejszymi od $ 2^k $. Niech

\[<br />
\overline{c_{k-1} c_{k-2}\ldots c_2 c_1 c_0}_{(2)}\ \textrm{oraz}\ \overline{d_{k-1} d_{k-2}\ldots d_2 d_1 d_0}_{(2)}<br />
\]

będą zapisami dwójkowymi odpowiednio liczb $ x $ i $ y $, przy czym dopuszczamy zera początkowe. Wówczas

\[<br />
f(x,y)=\sum_{i=0}^{k-1} |c_i-d_i|.<br />
\]

(Zatem $ f (x,y) $ jest liczbą miejsc dwójkowych, na których liczby $ x $ i $ y $ mają różne cyfry.)

Dowód lematu

Przeprowadzimy dowód indukcyjny ze względu na $ k $. Dla $ k = 1 $ teza lematu wynika bezpośrednio z równości

\[<br />
f (0,0) = f (1,1) = 0 \ \textrm{oraz}\   f (0,1) = f (1,0) = 1.<br />
\]

Niech $ k $ będzie taką liczbą całkowitą, dla której teza lematu jest prawdziwa oraz niech $ x $, $ y $ będą dowolnymi liczbami całkowitymi nieujemnymi mniejszymi od $ 2^{k+1} $. Zapiszmy liczby $ x $, $ y $ w układzie dwójkowym:

\[<br />
x=\overline{c_kc_{k-1} c_{k-2}\ldots c_2 c_1 c_0}_{(2)}\ \textrm{oraz}\ y=\overline{d_kd_{k-1} d_{k-2}\ldots d_2 d_1 d_0}_{(2)}.<br />
\]

Z założenia indukcyjnego wynika, że teza lematu jest spełniona dla liczb

\[<br />
x_0=\overline{c_kc_{k-1} c_{k-2}\ldots c_2 c_1}_{(2)}\ \textrm{oraz}\ y_0=\overline{d_kd_{k-1} d_{k-2}\ldots d_2 d_1}_{(2)},<br />
\]

mamy więc $ f (x_0, y_0) = |c_1 - d_1| + |c_2 - d_2|  +\ldots + |c_k - d_k| $. Ponadto $ x = 2x_0 + c_0 $ oraz $ y = 2y_0 + d_0 $, skąd na mocy warunków podanych w treści zadania wynika, że $ f (x,y) = f (x_0,y_0) + |c_0 - d_0| $. Zatem

\[<br />
f(x,y)=\sum_{i=0}^{k-1} |c_i-d_i|.<br />
\]

Dowód lematu został zakończony.

Przechodzimy teraz do rozwiązania zadania. Niech

\[<br />
a=\overline{a_{k-1} a_{k-2}\ldots a_2 a_1 a_0}_{(2)},\<br />
b=\overline{b_{k-1} b_{k-2}\ldots b_2 b_1 b_0}_{(2)},\<br />
x=\overline{c_{k-1} c_{k-2}\ldots c_2 c_1 c_0}_{(2)}\ .<br />
\]

Wówczas równość $ f (a,x)+ f (b,x) = f (a, b) $ jest równoważna równości

\[<br />
\sum_{i=0}^{k-1} |c_i-a_i| +|c_i-b_i| - |b_i-a_i|=0.<br />
\]

Ponieważ liczby $ |c_i - a_i| + |c_i - b_i| - |b_i - a_i| $ mogą przyjmować tylko wartości $ 0 $ (gdy $ a_i \neq b_i $ lub $ a_i = b_i = c_i $) lub $ 2 $ (gdy $ a_i = b_i \neq c_i $), zatem dla $ i = 0, 1, 2, \ldots, k-1 $ zachodzi warunek

\[<br />
a_i \neq b_i  \ \textrm{lub}\   a_i = b_i = c_i .<br />
\]

Możemy więc przy ustalonych $ a $ i $ b $ opisać wszystkie liczby $ x $ spełniające równanie $ f (a,x)+f (b,x) = f (a,b) $. Na tych pozycjach zapisu dwójkowego, na których liczby $ a $ i $ b $ mają różne cyfry, liczba $ x $ może mieć cyfrę dowolną. Na tych pozycjach, na których cyfry liczb $ a $ i $ b $ są takie same, liczba $ x $ musi mieć cyfrę taką jak liczby $ a $ i $ b $. Przy konstrukcji liczby $ x $ możemy więc dowolnie dobrać cyfry na $ f(a, b) $ pozycjach.

Liczba rozwiązań danego w zadaniu równania jest więc równa $ 2^n $.

Komentarze

Dodaj nową odpowiedź