LIV OM - II - Zadanie 6

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

$ \begin{array}{rcl} f (0,0) &=& 0;\\ f (2x, 2y) &=& f (2x +1,2y + 1) = f (x, y),\\ f(2x +1,2y) &=& f(2x, 2y +1)= f(x,y) + 1\ \textrm{dla}\ x,y \geq 0. \end{array} $

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

$ f (a,x) + f (b,x) = n. $

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

$ \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)} $

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

$ f(x,y)=\sum_{i=0}^{k-1} |c_i-d_i|. $

(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

$ f (0,0) = f (1,1) = 0 \ \textrm{oraz}\ f (0,1) = f (1,0) = 1. $

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:

$ 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)}. $

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

$ 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)}, $

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

$ f(x,y)=\sum_{i=0}^{k-1} |c_i-d_i|. $

Dowód lematu został zakończony.

Przechodzimy teraz do rozwiązania zadania. Niech

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

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

$ \sum_{i=0}^{k-1} |c_i-a_i| +|c_i-b_i| - |b_i-a_i|=0. $

$ a_i \neq b_i \ \textrm{lub}\ a_i = b_i = c_i . $

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.