LIX OM - I -Zadanie 4

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

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

$ (1)\qquad w(A)= a_1 -a_2 +a_3 -\dots +(-1)^{k+1} a_k. $

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

$ B_1,B_2, \dots , Bm, \{n\},B_1 \cup \{n\},B_2 \cup \{n\}, \dots , B_m \cup \{n\} $

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

$ \begin{split} w(B_i) &= c_1 -c_2 +c_3 -\dots +(-1)^{k+1} c_k, \\ w(B_i \cup \{n\}) &= n-c_1 + c_2 -\dots +(-1)^{k+2} c_k, \end{split} $

zatem

$ (2) \qquad w(B_i)+w(B_i \cup \{n\})= n. $

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

$ w(B_1)+w(B_1 \cup \{n\})+\dots +w(B_m)+w(B_m \cup \{n\})= m\cdot n. $

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

$ (3)\qquad S = k_1 +k_2 +\dots + k_n, $

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

$ (4) \qquad 2^{j-1} \left(\binom{n-j-1}{0} + \binom{n-j-1}{2} + \binom{n-j-1}{4} + \hdots \right), $

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