XVIII ZMPB - Zadanie 9

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

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

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

\[<br /> A_1\cup B_1,\qquad A_1\cup B_2,\qquad A_2\cup B_1,\qquad A_2\cup B_2<br /> \]

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

\[<br /> v\in A_i\quad\hbox{oraz}\quad w\in B_j\qquad\hbox{dla pewnych }i,j\in\{1,2\}.<br /> \]

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.

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

Komentarze

Dodaj nową odpowiedź