XLVI OM - III - Zadanie 1

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

III

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