Найдем общее число различных ключей. Для этого посчитаем количество всех используемых в гостинице ключей с учетом их повторений. Если x – общее число различных ключей, то количество всех используемых ключей с учетом их повторений равно 16х, поскольку каждый ключ изготовлен ровно в 16 экземплярах. В то же время, каждый из 176 работников имеет ровно по 5 различных ключей, а значит количество используемых в гостинице ключей с учетом их повторений равно 176×5 = 880. Отсюда, 16х=880 и х=55.
Теперь найдем количество ключей, открывающих номера класса «эконом». Ясно, что ключи имеющихся трех видов связаны так называемой диаграммой Эйлера (см. рис. 2). Пометим получившиеся 7 областей соответствующими числами. Так, например, области 7 соответствуют ключи, открывающие номера всех типов, области 1 – только номера класса «эконом» и т.д.
В соответствии с условием задачи, составим таблицу количества ключей, находящихся в различных областях диаграммы (табл. 2).
Из полученной таблицы легко найти количество ключей в каждой из областей 2,…,7, находя последовательно число элементов сначала в областях 4,5,6, а затем в 2,3. Эти данные запишем в таблицу (табл. 3).
|
Табл. 3
|
|
Область
|
2
|
3
|
4
|
5
|
6
|
7
|
|
Количество
|
7
|
15
|
5
|
3
|
9
|
1
|
Чтобы найти количество ключей, открывающих номера класса «эконом», нужно найти количество ключей, находящихся в области 1U4U5U7. Для этого вычтем из общего числа различных ключей суммарное количество ключей, находящихся в других областях: 55 – (7+9+15) = 24. Итак, количество ключей, открывающих только номера класса «эконом» равно 24.
Найдем минимальное число работников, имеющих ключи, которые открывают номера класса «эконом». Покажем, что это число равно [16·24/5]=77, где [x] – наименьшее целое, больше либо равное x. Расположим данные ключи в табл. 4 размера 16 на 24, в столбцах которой будут экземпляры одного и того же ключа, и покроем ее элементы «пятерками» - наборами, содержащими не более 5 различных ключей.
Табл. 4
В этих терминах задача переформулируется так: найти минимальное число «пятерок», покрывающих построенную таблицу. Начнем покрывать ее с первой строки. Ясно, что минимальное число «пятерок» равно 4, т.к. 24=5·4+4, значит оставшееся число ключей в первой строке равно 4. Теперь выберем во второй строке один отличный от этих 4-х ключей ключ (они образуют «пятерку»), и покроем строку минимальным числом «пятерок» (их ровно четыре), тогда оставшееся число ключей во второй строке равно 3. Продолжим данный процесс, выбирая в очередной строке подходящее число ключей для образования «пятерки» с оставшимися ключами предыдущей строки, и разбивая затем строку на минимальное число «пятерок».
Как видно, набор остатков в каждых последовательно идущих пяти строках будет одинаковым. Всего таких повторений - 3, т.к. 16=5·3+1, а каждое такое повторение строк дает 5·4+4=24 «пятерок». Итого всего «пятерок», приходящихся на 15 строк, будет 24·3=72. Таким образом, остается одна строка (последняя), которая даст 4 «пятерки», и в остатке еще 4 ключа, которые покроет еще одна «пятерка». Отсюда, общее их количество равно 72+4+1=77.
