Азиатско-Тихоокеанская математическая олимпиада, 2006 год

В цирке есть $n$ клоунов, которые одеваются и гримируются путем выбора из 12 различных имеющихся цветов. При этом каждому клоуну необходимо использовать не менее 5 различных цветов. Однажды директор цирка потребовал, чтобы никакие два клоуна не использовали одинаковый набор цветов, и никакие более чем 20 клоунов не могли использовать любой из цветов одновременно. Найдите наибольшее из возможных значений числа $n$ клоунов, так чтобы требование директора стало возможным.

Комментарий/решение

Пронумеруем клоунов числами 1, 2, ... , n и цвета - числами 1, 2, ... , 12. Рассмотрим {0,1}-матрицу 12 x n, в которой на пересечении i-ой строки и j-ого столбца стоит 1 тогда и только тогда, когда i-ый клоун использует j-ый цвет. Тогда, с одной стороны, в этой матрице единиц не более 20*12, а с другой - не менее 5n. Значит, n<=20*12/5=48. В качестве примера можно взять матрицу, в которой первые 12 строк получаются сдвигом 111110000000 на 0, 1, ... , 11 вправо по циклу, вторые 12 строк- сдвигом 111101000000, третие- сдвигом 111011000000, четвертые- сдвигом 110111000000.