Азия-тынық мұхит математикалық олимпиадасы, 2006 жыл

Әртүрлі 12 түсті таңдау арқылы цирктағы $n$ клоун киінеді және боянады. Сонымен қатар әр клоунға кем дегенде 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.