XXIII OM - III - Zadanie 5

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

\[<br />
(1) \qquad  A_1, A_2, \ldots, A_{2^n}<br />
\]

wszystkich podzbiorów zbioru $ A $, że

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

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:

\[<br />
(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\},<br />
\]

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\} -<br />
 (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

\[<br />
e_j = \left\{<br />
\begin{array}{cll}<br />
0, & \textrm{gdy} & a_j \not \in A', \\<br />
1, & \textrm{gdy} & a_j      \in A'. \\<br />
\end{array}<br />
\right.<br />
\]

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ą.

Komentarze

Dodaj nową odpowiedź