Zbiór zadań, (kombinacje)
Zadanie 16
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?
Rozwiązanie
Niech dla pewnej liczby naturalnej n istnieje taki rozkład kluczy do n zamków wśród 11-osobowej komisji, że spełnione są warunki zadania. Wówczas dla każdych pięciu członków komisji istnieje taki zamek, którego żaden z nich nie może go otworzyć. Różnym podzbiorom pięcio-elementowym zbioru wszystkich członków komisji odpowiadają różne zamki, których członkowie tych piątek nie mogą go otworzyć. Suma dwóch różnych podzbiorów pięcioelementowych zawiera co najmniej sześć elementów, a każdych sześciu członków komisji może otworzyć dowolny zamek.
Stąd wniosek, że liczba zamków jest nie mniejsza od liczby podzbiorów pięcio-elementowych zbioru jedenasto-elementowego.
Najmniejszą liczbą spełniającą warunki zadania jest .
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>