XXIII OM - III - Zadanie 5

Zawody matematyczne:

XXIII OM, 1971-1972

Etap:

III

Udowodnić, że wszystkie podzbiory zbioru skończonego można ustawić w ciąg, którego kolejne wyrazy różnią się jednym elementem.

Rozwiązanie

Załóżmy, że dany zbiór skończony $A$ ma $n$ elementów. Stosując indukcję względem $n$ udowodnimy, że istnieje taki ciąg

$ (1) \qquad A_1, A_2, \ldots, A_{2^n} $

wszystkich podzbiorów zbioru $A$ , że

$ \begin{split} (2) \qquad \textrm{ dla } & i = 1, 2, \ldots, 2^n \textrm{ jeden ze zbiorów } A_{i+1} - A_i \\ \textrm{ oraz } & A_i - A_{i+1} \textrm{ jest pusty, a drugi - jednoelementowy}. \end{split} $

Dla $n = 1$ ciąg $\emptyset$ , $A$ spełnia oczywiście (2). Załóżmy że dla pewnej liczby naturalnej $n$ istnieje taki ciąg (1) wszystkich podzbiorów zbioru $n$ -elementowego $A$ , który spełnia (2). Udowodnimy, że istnieje ciąg wszystkich podzbiorów zbioru $(n+1)$ -elementowego $A \cup \{b\}$ , który spełnia (2).

Stosujemy indukcję względem $n$ . Jeżeli ciąg (1) wszystkich podzbiorów zbioru $n$ -elementowego $A$ spełnia warunek (2), to następujący ciąg wszystkich podzbiorów zbioru $(n + 1)$ -elementowego $A \cup \{b\}$ spełnia też ten warunek:

$ (5) \qquad A_1, A_2, \ldots, A_{2n}, A_{2n} \cup \{b\}, A_{2n-1} \cup \{b\}, \ldots, A_2 \cup \{b\}, A_1 \cup \{b\}, $

zawiera on bowiem wszystkie zbiory $A_i$ oraz wszystkie zbiory $A \cup \{b\}$ dla $i = 1, 2, \ldots, 2^n$ , tzn. wszystkie podzbiory zbioru $A \cup \{b\}$ . Rozpatrzmy kolejne wyrazy ciągu (5). Z założenia indukcyjnego wiemy, że jeden ze zbiorów $A_{i+1} - A_i$ oraz $A_i - A_{i+1}$ jest pusty, a drugi - jednoelementowy; wynika stąd też, że jeden ze zbiorów ( $A_{i+1} \cup \{b\} - (A_i \cup \{b\}) = A_{i+1} - A_i$ oraz $(A_i \cup \{b\}) - (A_{i+1} \cup \{b\}) = A_i - A_{i+1}$ jest pusty, a drugi - jednoelementowy.

Wreszcie $(A_{2^n} \cup \{b\}) - A_{2^n} = \{b\}$ i $A_{2^n} - (A_{2^n} \cup \{b\}) = \emptyset$ . Zatem ciąg (5) spełnia warunek (2).

Uwaga. Zadanie to ma interesującą interpretację geometryczną. Rozpatrzmy przypadek $n = 3$ . Jeżeli $A = \{a_1, a_2, a_3\}$ , to każdy podzbiór $A'$ zbioru $A$ można utożsamiać z punktem $(e_1, e_2, e_3)$ , którego współrzędne są równe $0$ lub $1$ . Mianowicie określamy

$ e_j = \left\{ \begin{array}{cll} 0, & \textrm{gdy} & a_j \not \in A', \\ 1, & \textrm{gdy} & a_j \in A'. \\ \end{array} \right. $

Punkty takie są wierzchołkami sześcianu wyznaczonego przez wektory jednostkowe osi układu współrzędnych.

Niech $A'$ i $A''$ będą podzbiorami zbioru $A$ . Jeden ze zbiorów $A' - A''$ oraz $A'' - A'$ jest pusty, a drugi - jednoelementowy wtedy i tylko wtedy, gdy punkty odpowiadające zbiorom $A'$ i $A''$ różnią się jedną współrzędną. Punkty takie należą do pewnej krawędzi sześcianu. Zadanie nasze można więc sformułować tak: Istnieje taka łamana utworzona przez pewne krawędzie sześcianu, która przechodzi dokładnie jeden raz przez każdy jego wierzchołek.

W przypadku $n \ne 3$ można podać analogiczną interpretację zadania. Należy tylko zamiast sześcianu rozpatrywać kostkę $n$ -wymiarową.