XLVIII OM - III - Zadanie 4

Zawody matematyczne:

XLVIII OM, 1996-1997

Etap:

III

Ciąg $a_1, a_2, a_3,\ldots$ jest określony wzorami

$<br /> a_1 = 0, \quad a_n = a_{[n/2]} + (-1)^{n(n+1)/2}\quad \textrm{dla}\ n > 1.<br />$

Dla każdej liczby całkowitej $k \geq 0$ wyznaczyć liczbę numerów $n$ spełniających warunki

$<br /> 2^k \leq n < 2^{k+1}, \qquad a_n = 0.<br />$

Uwaga: $[n/2]$ jest największą liczbą całkowitą nie przekraczającą $n/2$ .

Rozwiązanie

Każdej liczbie całkowitej $n \geq 1$ przyporządkowujemy skończony ciąg symboli dwóch rodzajów: kropek i przecinków. Zapisujemy liczbę $n$ w systemie dwójkowym. Pomiędzy każde dwie kolejne cyfry wstawiamy kropkę, gdy te cyfry są jednakowe, a przecinek, gdy są różne. Jeżeli $n$ spełnia nierówność $2^k\leq n < 2^{k+1}$ , czyli jest (w systemie dwójkowym) liczbą $(k+1)$ -cyfrową, to wstawione w opisany sposób kropki i przecinki tworzą ciąg $k$ -wyrazowy. Będziemy go nazywali {\it kodem} liczby $n$ . Każdy taki ciąg kropek i przecinków jest kodem dokładnie jednej liczby $n$ : na początku ma ona jedynkę, a dalsze cyfry są wyznaczone przez kolejne symbole kodu. Kod $k$ -wyrazowy wyznacza liczbę $(k+1)$ -cyfrową.

Oznaczmy przez $b_n$ liczbę kropek, a przez $c_n$ liczbę przecinków w kodzie liczby $n$ i przyjmijmy $d_n = b_n - c_n$ .

Niech $n$ będzie dowolną liczbą $(k+1)$ -cyfrową ( $k \geq 1$ ). Skreślając jej ostatnią cyfrę otrzymujemy zapis dwójkowy liczby $[n/2]$ . Jeśli ostatnie dwie cyfry liczby $n$ są równe, to $b_n = b_{[n/2]} + 1$ , $c_n = c_{[n/2]}$ . Jeśli ostatnie dwie cyfry liczby $n$ są różne, to $b_n = b_{[n/2]}$ , $c_n = c_{[n/2]} + 1$ . Pierwsza z tych sytuacji ma miejsce, gdy $n \equiv 0$ lub $n \equiv 3\ (\mathrm{mod}\ 4)$ , druga - gdy $n \equiv 1$ lub $n \equiv 2\ (\mathrm{mod}\ 4)$ . Różnica $d_n - d_{[n/2]}$ wynosi $1$ w pierwszym przypadku, zaś $-1$ w drugim przypadku.

Dokładnie takie same wartości przybiera różnica $a_n - a_{[n/2]}$ . Dla $n = 1$ mamy $a_1 = b_1 = c_1 = d_1 = 0$ . Stąd wniosek, że $a_n = d_n$ , czyli $a_n = b_n - c_n$ , dla $n = 1,2,3,\ldots$ . Zatem dla $(k+1)$ -cyfrowej liczby $n$ równość $a_n = 0$ zachodzi wtedy i tylko wtedy, gdy w jej $k$ -wyrazowym kodzie jest tyle samo symboli każdego rodzaju. Liczba takich $k$ -wyrazowych ciągów wynosi ${k \choose {k/2}}$ , gdy $k$ jest liczbą parzystą, oraz $0$ , gdy $k$ jest liczbą nieparzystą. Tyle jest więc numerów $n$ spełniających zadane warunki.