LX OM - II - Zadanie 5

Zawody matematyczne:

LX OM, 2008-2009

Etap:

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:

$X \sim X$ ;
jeżeli $X \sim Y$ , to $Y \sim X$ ;
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:

Zbiór $C_i$ ma dokładnie 3 elementy.
Zbiór $C_i$ ma dokładnie 4 elementy.
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ć

$ X = \{p,q,x\},\quad Y = \{p,q,y\}, \quad Z = \{p,q,z\}, $

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

$ \begin{split} A_{4j-3} = \{4j -2,4j -1,4j\},&\quad A_{4j-1} = \{4j -3,4j -2,4j\},\\ A_{4j-2} = \{4j -3,4j -1,4j\},&\quad A_{4j} = \{4j -3,4j -2,4j -1\} \end{split} $

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.