LIX OM - I -Zadanie 4

Dana jest liczba całkowita $ n \geqslant 1 $. Każdemu niepustemu podzbiorowi $ A $ zbioru $ \{1, 2,\dots ,n\} $
przyporządkowujemy liczbę $ w(A) $ w następujący sposób: Jeżeli $ a_1 >a_2 >\dots >a_k $ są wszystkimi elementami
zbioru A, to

\[<br />
(1)\qquad w(A)= a_1 -a_2 +a_3 -\dots  +(-1)^{k+1} a_k.<br />
\]

Obliczyć sumę wszystkich $ 2n-1 $ otrzymanych liczb $ w(A) $.

Rozwiązanie

Sposób I

Dla $ n = 1 $ rozważana suma jest równa 1. Przyjmijmy więc, że $ n \geqslant 2 $.

Niech $ B_1, B_2, \dots , B_m $ będą wszystkimi niepustymi podzbiorami zbioru $ \{1, 2,\dots ,n-1\} $.
Wówczas $ m =2^{n-1} -1 $ oraz

\[<br />
B_1,B_2, \dots , Bm, \{n\},B_1 \cup \{n\},B_2 \cup \{n\}, \dots , B_m \cup \{n\}<br />
\]

są wszystkimi niepustymi podzbiorami zbioru $ \{1, 2,\dots ,n\} $.

Ustalmy wartość $ i\in \{1,2,\dots ,m\} $. Niech $ c_1 >c_2 >\dots >c_k $ będą wszystkimi elementami zbioru $ B_i $. Nietrudno spostrzec, że

\[<br />
\begin{split}<br />
w(B_i) &= c_1 -c_2 +c_3 -\dots +(-1)^{k+1} c_k, \\<br />
w(B_i \cup \{n\}) &= n-c_1 + c_2 -\dots +(-1)^{k+2} c_k,<br />
\end{split}<br />
\]

zatem

\[<br />
(2) \qquad w(B_i)+w(B_i \cup \{n\})= n.<br />
\]

Wypisując równość (2) dla $ i =1,2,\dots ,m $ i sumując stronami uzyskujemy

\[<br />
w(B_1)+w(B_1 \cup \{n\})+\dots +w(B_m)+w(B_m \cup \{n\})= m\cdot n.<br />
\]

Wobec tego suma, którą należy wyznaczyć, jest równa $ w({n})+ m\cdot n = n+(2^{n-1} -1)\cdot n = n\cdot 2^{n-1} $.

Sposób II

Niech $ A_1, A_2, \dots , A_m $ ($ m =2^n - 1 $) będą wszystkimi niepustymi podzbiorami zbioru
$ \{1,2,\dots ,n\} $. Utwórzmy tabelę o $ m $ wierszach i $ n $ kolumnach. W każde pole tej tabeli wpisujemy
liczbę zgodnie z następującą zasadą: Jeżeli $ a_1 >a_2 >\dots >a_k $ są wszystkimi elementami zbioru
$ A_j $ (gdzie $ j =1,2,\dots ,m $), to w pole znajdujące się w $ j $-tym wierszu oraz $ a_i $-tej kolumnie
wpisujemy liczbę $ (-1)^{i+1}a_i $. W pozostałe pola tej tabeli wpisujemy zera.

Na mocy warunku (1) suma liczb znajdujących się w $ j $-tym wierszu tabeli wynosi $ w(A_j) $. To oznacza, że suma
$ S $, która należy obliczyć w zadaniu, jest równa sumie wszystkich liczb w tabeli. Zatem

\[<br />
(3)\qquad S = k_1 +k_2 +\dots + k_n,<br />
\]

gdzie $ k_i $ jest sumą liczb znajdujących się w $ i $-tej kolumnie.

Dla każdego ze zbiorów $ A_1, A_2, \dots , A_m $ liczba $ n $ jest bądź jego największym elementem, bądź też do
niego nie należy. Ponadto liczba tych zbiorów, które zawierają liczbę $ n $, jest równa liczbie podzbiorów
zbioru $ \{1,2,\dots ,n-1\} $, czyli liczbie $ 2^{n-1} $. Wynika stąd, że w $ n $-tej kolumnie tabeli znajduje
się $ 2^{n-1} $ liczb $ n $, a pozostałe liczby są zerami. Zatem $ k_n = n\cdot 2^{n-1} $.

Wykażemy z kolei, że $ k_1 = k_2 = \dots  = k_{n-1} = 0 $.

Ustalmy wartość $ j \in \{1,2,\dots ,n - 1\} $. Każda liczba występująca w $ j $-tej kolumnie jest równa
0, $ j $ albo $ -j $. Musimy wykazać, że liczb $ j $ jest tyle samo, co liczb $ -j $. Zauważmy, że w $ i $-tym wierszu
rozważanej kolumny znajduje się liczba $ j $ wtedy i tylko wtedy, gdy do zbioru $ A_i $ należy liczba $ j $
oraz parzysta liczba liczb większych od $ j $ (wybranych z $ (n - j - 1) $-elementowego zbioru
$ \{j +1,j +2,\dots ,n-1,n\} $); liczby mniejsze od $ j $ nie mają na to wpływu. Zatem liczba liczb
$ j $ w $ j $-tej kolumnie tabeli jest równa

\[<br />
(4) \qquad 2^{j-1} \left(\binom{n-j-1}{0} + \binom{n-j-1}{2} + \binom{n-j-1}{4} + \hdots \right),<br />
\]

przy czym ostatni składnik w powyższej sumie wynosi $ \binom{n-j-1}{n-j-1} $ albo $ \binom{n-j-1}{n-j-2} $
w zależności od parzystości liczby $ n - j -1 $. Podobnie dowodzimy, że liczba liczb $ -j $ w $ j $-tej kolumnie
jest równa

\[<br />
(5) \qquad 2^{j-1} \left(\binom{n-j-1}{1} + \binom{n-j-1}{3} + \binom{n-j-1}{5} + \hdots \right),<br />
\]

Liczby (4) i (5) są równe, gdyż na mocy wzoru dwumianowego ich różnica wynosi
$ 2^{j-1} \cdot (1-1)n-j-1 = 0 $. To kończy dowód równości $ k_j = 0 $.

Z udowodnionych zależności otrzymujemy na mocy (3), że $ S = n\cdot 2^{n-1} $.

Komentarze

Dodaj nową odpowiedź