XLVI OM - III - Zadanie 1

Wyznaczyć liczbę podzbiorów zbioru $ \{1,2, \ldots , 2n\} $, w których równanie $ x + y = 2n+1 $ nie ma rozwiązań.

Rozwiązanie

Zbiór $ A $, zawarty w zbiorze $ \{1,2,\ldots,2n\} $, będziemy nazywali dobrym, jeśli ma on wymaganą w zadaniu własność; to znaczy, gdy równanie $ x + y = 2n + 1 $ nie ma rozwiązania $ x,y \in A $.

Zbiór $ \{1,2,\ldots,2n\} $ jest sumą następujących rozłącznych podzbiorów dwuelementowych (czyli par liczb):

\[<br />
P_1 = \{1,2n\},\ P_2 = \{2,2n-1\}, \ \ldots,\ P_n = \{n,n+1\};<br />
\]

symbol $ P_j $ oznacza parę $ \{j, 2n+1-j\} $.

Podzbiór $ A $ zbioru $ \{1,2,\ldots,2n\} $ jest dobry wtedy i tylko wtedy, gdy nie zawiera żadnej pary $ P_j $, czyli - równoważnie - gdy dla każdego numeru $ j \in \{1,2,\ldots,n\} $ część wspólna $ P_j \cap A $ jest albo zbiorem pustym, albo zbiorem jednoelementowym $ \{j\} $, albo zbiorem jednoelementowym $ \{2n+1-j\} $. Dobry zbiór $ A $ jest więc jednoznacznie wyznaczony przez wybór jednej z tych trzech opcji dla każdego $ j \in \{1,2,\ldots,n\} $. Stąd wniosek, że liczba dobrych zbiorów wynosi $ 3^n $.

Komentarze

Dodaj nową odpowiedź