Математикадан облыстық олимпиада, 2007-2008 оқу жылы, 10 сынып

Өлшемі $5\times n$ болатын кестенің, мұндағы $n\in \mathbb{N}$, әрбір шаршысы қызыл немесе көк түске боялған. Мына шартты қанағаттандыратын $n$-нің ең аз мүмкін мәнін тап: кестенің қалай боялғанына қарамастан, қиылысуындағы 9 шаршының түсі бірдей болатын етіп, кестенің 3 жолы мен 3 бағанын табуға болады.

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

Ответ: $n=60$

В таблице 5 строк и два цвета. Различных вариантов расположения этих цветов$\frac{5!}{(5-2)!}=20$. Теперь можно выбрать любые 3 строки. Чтобы подобрать три соответстветствующих столбца, достаточно пристроить две такие же таблицы справа. Теперь при любой расстановке возможно подобрать три столбца так, как сказано в условии

У вас ошибка вас ответ лишь показывает что при n=60 условие возможно но не доказано что данный ответ минимален

Ответ: $n=41$

Пусть у нас будет 5столбцов и n строк. Раскраска подойдет нам в том случае когда в пересечении каких-либо 3строк с 3столбцами, образуются 9клеток с одинаковыми цветами. То есть, нам нужно чтобы какая-либо из троек столбцов с одинаковым цветом клеток в одной строке встретилась 3 раза. Количество все возможных троек столбцов равно 10. Заметим, что в каждой строке будет как минимум 3столбца с одинаковыми цветами(неважно какими). Получается, за 40строк количество каждой из троек столбцов с одинаковым цветом клеток в одной строке будет как минимум равно 2(учитывая то, что цвет клеток может быть красным и синим). Учитывая, что новая строка дает одну тройку столбцов с одинаковым цветом клеток в одной строке, то для n=41 любая раскраска таблицы дает 3строки и 3столбца, для которых 9 клеток, образованных при их пересечении, имеют одинаковый цвет.

Для n=40 легко найти контрпример, где каждая тройка будет встречаться ровно по 2 раза