XVIII ZMPB - Zadanie 9

Zawody matematyczne:

XVIII ZMPB, 2007

W pewnym stowarzyszeniu należy wybrać zarząd. Każdy członek wskazał 10 kandydatów do zarządu, ale będzie zadowolony, jeżeli przynajmniej jeden z nich znajdzie się w zarządzie. Dla dowolnych sześciu członków stowarzyszenia można utworzyć dwuosobowy zarząd, zadowalający wszystkich sześciu. Dowieść, że można wybrać 10-osobowy zarząd, zadowalający wszystkich członków stowarzyszenia.

Rozwiązanie

Niech $a$ będzie jednym z członków stowarzyszenia, a $A=\{a_1,a_2,\ldots,a_{10}\}$ zbiorem jego kandydatów do zarządu. Jeżeli zbiór kandydatów wskazanych przez każdego innego członka ma niepuste przecięcie ze zbiorem $A$ , wówczas zarząd złożony z osób $a_1$ , $a_2$ , $\ldots$ , $a_{10}$ będzie zadowalał wszystkich członków stowarzyszenia.

Przyjmujemy w związku z tym w dalszej częsci rozumowania, że istnieje taki członek stowarzyszenia $b$ , że zbiór $B=\{b_1,b_2,\ldots,b_{10}\}$ wskazanych przezeń kandydatów jest rozłączny ze zbiorem $A$ .

Oznaczmy

$ \begin{split} A_1=\{a_1,a_2,\ldots,a_5\},\quad&\quad A_2=\{a_6,a_7,\ldots,a_{10}\},\\ B_1=\{b_1,b_2,\ldots,b_5\},\quad&\quad B_2=\{b_6,b_7,\ldots,b_{10}\}. \end{split} $

Udowodnimy, że przynajmniej jeden z 10-osobowych zbiorów

$ A_1\cup B_1,\qquad A_1\cup B_2,\qquad A_2\cup B_1,\qquad A_2\cup B_2 $

tworzy zarząd zadowalający wszystkich członków stowarzyszenia.

Przypuśćmy, że tak nie jest; istnieją więc członkowie $x$ , $y$ , $z$ , $t$ , niezadowoleni odpowiednio z zarządów $A_1\cup B_1$ , $A_1\cup B_2$ , $A_2\cup B_1$ , $A_2\cup B_2$ . Zgodnie z założeniami istnieje zarząd złożony z dwóch osób $v$ i $w$ , który zadowala każdego z sześciu członków $a$ , $b$ , $x$ , $y$ , $z$ , $t$ . Ponieważ zarząd ten zadowala członków $a$ i $b$ , więc jedna z osób $v$ , $w$ należy do zbioru $A$ , a druga - do zbioru $B$ . Dla ustalenia oznaczeń niech $v\in A$ oraz $w\in B$ . Zatem

$ v\in A_i\quad\hbox{oraz}\quad w\in B_j\qquad\hbox{dla pewnych }i,j\in\{1,2\}. $

Wynika stąd, że zbiór $\{v,w\}$ zawiera się w zbiorze $A_i\cup B_j$ . Jednak zarząd $A_i\cup B_j$ nie zadowala jednego z członków $x$ , $y$ , $z$ , $t$ , wbrew temu, że każdy z tych czterech członków jest zadowolony z zarządu $\{v,w\}$ .

Otrzymaliśmy sprzeczność, z której wynika teza zadania.