XXII OM - III - Zadanie 3

Ile co najmniej zamków trzeba założyć do skarbca, aby przy pewnym rozkładzie kluczy z 11-osobowej komisji upoważnionej do otwierania skarbca każdych 6 członków mogło go otworzyć, ale żadnych 5 nie mogło? Określić rozdział kluczy między członków komisji przy minimalnej liczbie zamków.

Rozwiązanie

Przypuśćmy, że dla pewnej liczby naturalnej $ n $ istnieje taki rozkład kluczy do $ n $ zamków wśród $ 11 $-osobowej komisji, że warunki zadania są spełnione. Oznaczmy przez $ A_i $ zbiór zamków, które może otworzyć $ i $-ty członek komisji, gdzie $ i = 1, 2, \ldots, 11 $, i oznaczmy przez $ A $ zbiór wszystkich zamków. Wtedy z warunków zadania wynika, że

\[<br />
(1) \qquad  A_{i_1} \cup \ldots \cup A_{i_5} \ne A<br />
\]

dla dowolnego pięcioelementowego podzbioru $ \{ i_1, \ldots, i_5\} $ zbioru $ \{1, 2, \ldots, 11\} $ oraz

\[<br />
(2) \qquad  A_{j_1} \cup \ldots \cup A_{j_6} = A<br />
\]

dla dowolnego sześcioelementowego podzbioru $ \{j_1, \ldots, j_6\} $ zbioru $ \{1,2,\ldots,  11\} $.

Z (1) wynika, że zbiór $ A - (A_{i_1} \cup \ldots \cup A_{i_5}) $ jest niepusty. Oznaczmy przez $ x_{i_1}, \ldots, x_{i_5} $ jeden z jego elementów, tzn. pewien zamek, którego nie może otworzyć grupa członków komisji o numerach $ i_1, \ldots, i_5 $. Z (2) wynika, że dla każdego $ j \not \in \{i_1, \ldots, i_5 \} $ mamy $ x_{i_1 , \ldots, i_5} \in A_j $.

Przypuśćmy, że $ x_{i_1,\ldots,i_5} = x_{k_1, \ldots, k_5} $ dla pewnych podzbiorów $ \{i_1, \ldots, i_5\} $ i $ \{k_1, \ldots, k_5\} $. Gdyby podzbiory te były różne, to na przykład $ i_t \not \in \{ k_1, \ldots, k_5 \} $. Wobec tego $ x_{k_1, \ldots, k_5} \in A_{i_t} $; ale z drugiej strony $ x_{1_i,\ldots, i_5}<br />
 \not \in A_{i_t} $. Uzyskana sprzeczność dowodzi, że $ \{i_1, \ldots,i_5\} = \{ k_1, \ldots, k_5 \} $.

Inaczej mówiąc różnym zbiorom pięcioelementowym $ \{i_1, \ldots, i_5\} $ odpowiadają różne zamki. Zatem liczba zamków jest nie mniejsza od liczby podzbiorów pięcioelementowych zbioru $ 11 $-elementowego, cżyli $ n \geq  \binom{11}{15} = 462 $.

Udowodnimy z kolei, że jeżeli do skarbca założymy $  \binom{11}{5} $ zamków, to można tak rozdzielić klucze do nich wśród członków $ 11 $-osobowej komisji, aby były spełnione warunki zadania.

Przyporządkujmy każdemu z $  \binom{11}{5} $ zamków w sposób wzajemnie jednoznaczny podzbiór pięcioelementowy zbioru $ \{1, 2, \ldots, 11\} $. Jeżeli zamkowi odpowiada podzbiór $ \{i_1, \ldots, i_5\} $, to klucze do niego otrzymują wszyscy członkowie komisji o numerach różnych od $ i_1, \ldots, i_5 $.

Wykażemy, że żadnych pięciu członków komisji nie otworzy pewnego zamka, a więc i skarbca. Istotnie, członkowie komisji o numerach $ i_1, \ldots, i_5 $ nie mają klucza do zamku, któremu odpowiada podzbiór $ \{i_1, \ldots, i_5\} $.

Wykażemy, że każdych sześciu członków komisji otworzy dowolny zamek, a więc i skarbiec. Jeżeli członkowie komisji mają numery $ j_1, \ldots, j_6 $ i chcą otworzyć zamek, któremu odpowiada podzbiór $ \{i_1, \ldots, i_5\} $, to jedna z sześciu liczb $ j_1, \ldots, j_6 $ nie należy do tego pięcioelementowego podzbioru, np. $ j_t \not \in \{i_1, \ldots, i_5 \} $. Wobec tego członek komisji o numerze $ j_t $, ma klucz do zamka odpowiadającego podzbiorowi $ \{i_1, \ldots, i_5\} $.

Zatem najmniejszą liczbą spełniającą warunki zadania jest $  \binom{11}{5} = 462 $.

Komentarze

Dodaj nową odpowiedź