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

$ (1) \qquad A_{i_1} \cup \ldots \cup A_{i_5} \ne A $

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

$ (2) \qquad A_{j_1} \cup \ldots \cup A_{j_6} = A $

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} \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\}$ .