Komentarz

LX OM - II - Zadanie 5

Wyznaczyć wszystkie liczby całkowite $ n\geqslant 4 $ o następującej własności: Spośród dowolnych $ n $
różnych 3-elementowych podzbiorów zbioru $ n $-elementowego można wybrać dwa podzbiory, które mają dokładnie
jeden element wspólny.

Rozwiązanie

Niech $ A_1, A_2, \cdots , A_k $ będą różnymi 3-elementowymi podzbiorami ustalonego zbioru $ n $-elementowego.
Przypuśćmy ponadto, że dowolne dwa z tych zbiorów albo są rozłączne, albo mają dokładnie dwa wspólne elementy.

Oznaczmy $ \mathcal{A} = \{A_1,A_2, \cdots ,Ak\} $ i wprowadźmy następujące oznaczenie:
$ X\sim Y $ wtedy i tylko wtedy, gdy przekrój $ X\cap Y $ jest zbiorem niepustym (a więc mającym co najmniej
2 elementy),

dla (niekoniecznie różnych) zbiorów $ X,Y \in \mathcal{A} $.

Dla dowolnych zbiorów $ X,Y,Z \in \mathcal{A} $ zachodzą następujące własności:

  1. $ X \sim X $;
  2. jeżeli $ X \sim Y $ , to $ Y \sim X $;
  3. jeżeli $ X \sim Y $ oraz $ Y \sim Z $, to $ X \sim Z $.

Istotnie, własności 1) i 2) są oczywiste, a by uzasadnić własność 3), wystarczy spostrzec, że z faktu,
iż zbiory $ X, Y , Z $ mają 3 elementy, a przekroje $ X \cap Y $ i $ Y \cap Z $ mają przynajmniej 2 elementy, wynika,
iż przekrój $ X \cap Z $ jest zbiorem niepustym. Na mocy przyjętego na początku rozwiązania założenia przekrój ten
zawiera zatem przynajmniej 2 elementy, co oznacza, że $ X \sim Z $.

Własności 1)—3) dowodzą, że zbiory $ A_1, A_2, \cdots , A_k $ można podzielić na parami rozłączne
klasy równoważności w taki sposób, by dowolne dwa zbiory $ X, Y $ należące do tej samej klasy spełniały
relację $ X \sim Y $ , natomiast dowolne dwa zbiory należące do różnych klas tej relacji nie spełniały.

Niech $ \mathcal{B}_1, \mathcal{B}_2, \cdots , \mathcal{B}_m $ będą tak zadanymi klasami równoważności oraz niech
$ C_i $ $ (i =1,2, \cdots ,m) $ będzie sumą wszystkich zbiorów należących do klasy \mathcal{B}_i. Wówczas zbiory
$ C_1, C_2, \cdots , C_m $ są parami rozłączne, bowiem zbiory należące do różnych klas są rozłączne.
Ponadto każdy z tych zbiorów zawiera przynajmniej 3 elementy, gdyż jest sumą zbiorów 3-elementowych.

Dla każdego zbioru $ C_i $ rozpatrzmy następujące trzy możliwości:

  1. Zbiór $ C_i $ ma dokładnie 3 elementy.
  2. Zbiór $ C_i $ ma dokładnie 4 elementy.
  3. Zbiór $ C_i $ ma przynajmniej 5 elementów.

W przypadku 1. rodzina $ \mathcal{B}_i $ składa się z jednego zbioru, mianowicie z tego zbioru
$ A_j $ $ (j =1,2, \cdots ,k) $, który jest równy zbiorowi $ C_i $.

W przypadku 2. każdy zbiór należący do rodziny $ \mathcal{B}_i $ jest 3-elementowym podzbiorem 4-elementowego
zbioru $ C_i $. Zatem w rodzinie tej znajdują się najwyżej 4 zbiory.

Rozpatrzmy z kolei przypadek 3.. Wybierzmy różne zbiory $ X,Y \in \mathcal{B}_i $. Są to zbiory 3-elementowe,
których przekrój $ X\cap Y $ ma 2-elementy, a więc suma $ X \cap Y $ jest zbiorem 4-elementowym. To oznacza, że w
rodzinie $ \mathcal{B}_i $ istnieje zbiór $ Z $ zawierający element, który nie należy do sumy $ X \cap Y $ .
Stąd wniosek, że 2-elementowe przekroje $ X \cap Y $ , $ X \cap Z $, $ Y \cap Z $ muszą się pokrywać, a więc
można napisać

\[<br /> X = \{p,q,x\},\quad Y = \{p,q,y\}, \quad Z = \{p,q,z\},<br /> \]

gdzie elementy $ p, q, x, y, z $ są różne. Weźmy teraz pod uwagę dowolny zbiór $ S $ należący do rodziny
$ \mathcal{B}_i $ i różny od zbiorów $ X, Y , Z $. Wówczas $ S $ nie jest zbiorem $ \{x,y,z\} $, gdyż ten ostatni
ma dokładnie jeden element wspólny ze zbiorem $ X $. Wobec tego przynajmniej jeden z elementów $ x, y, z $
nie należy do zbioru $ S $. Przyjmijmy, nie zmniejszając ogólności dalszego rozumowania, iż jest to element $ x $.
Skoro przekrój $ X\cap S $ jest zbiorem 2-elementowym oraz $ x \notin S $, musimy mieć $ X \cap S = \{p,q\} $.
Ale to, wobec dowolności wyboru $ S $, oznacza, że każdy zbiór należący do rodziny $ \mathcal{B}_i $
zawiera elementy $ p $ i $ q $. Stąd wniosek, że liczba elementów tej rodziny nie przekracza liczby elementów zbioru
$ C_i $ pomniejszonej o 2.

Udowodniliśmy w ten sposób, że każda z rodzin $ \mathcal{B}_i $ zawiera najwyżej tyle zbiorów, ile jest
elementów w zbiorze $ C_i $, przy czym równość może mieć miejsce tylko wtedy, gdy zbiór $ C_i $ ma 4 elementy.

Ponadto zbiory $ C_1, C_2, \cdots , C_m $ są parami rozłączne, a ich suma zawiera się w ustalonym na
początku rozwiązania zbiorze $ n $-elementowym, więc suma liczb elementów tych zbiorów nie przekracza $ n $.
Tym bardziej suma liczb elementów rodzin $ \mathcal{B}_1, \mathcal{B}_2, \cdots , \mathcal{B}_m $ nie przekracza
$ n $, przy czym równość jest możliwa tylko w przypadku, gdy każdy ze zbiorów $ C_i $ oraz każda z rodzin
$ \mathcal{B}_i $ $ (i =1,2, \cdots ,m) $ ma dokładnie 4 elementy,

Jednakże każdy ze zbiorów $ A_1, A_2, \cdots , A_k $ należy do dokładnie jednej z tych rodzin. Stąd wniosek,
że $ k \leqslant n $, przy czym równość może mieć miejsce tylko wtedy, gdy każda z rodzin $ \mathcal{B}_i $
$ (i =1, 2, \cdots ,m) $ ma dokładnie 4 elementy oraz suma ilości elementów tych rodzin jest równa $ n $.
Jest to możliwe tylko wtedy, gdy zachodzi równość $ n=4m $. Jeśli zatem istnieje układ $ n $ trójelementowych
podzbiorów zbioru $ n $-elementowego, z których żadne dwa nie mają dokładnie jednego elementu wspólnego,
to liczba $ n $ jest podzielna przez $ 4 $.

Implikacja odwrotna również jest prawdziwa: jeżeli $ n =4s $ dla pewnej liczby całkowitej $ s \geqslant 1 $,
to definiujemy zbiory $ A_1, A_2, \cdots , A_{4s} $ warunkami

\[<br /> \begin{split}<br /> A_{4j-3} = \{4j -2,4j -1,4j\},&\quad A_{4j-1} = \{4j -3,4j -2,4j\},\\<br /> A_{4j-2} = \{4j -3,4j -1,4j\},&\quad A_{4j} = \{4j -3,4j -2,4j -1\}<br /> \end{split}<br /> \]

dla $ j =1,2, \cdots ,s $. Wówczas dowolne dwa z określonych wyżej zbiorów albo są rozłączne, albo mają
dokładnie dwa wspólne elementy.

Odpowiedź: Liczba $ n \geqslant 4 $ spełnia warunki zadania wtedy i tylko wtedy, gdy nie jest
podzielna przez 4.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz