XLVIII OM - III - Zadanie 4

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.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź