Областная олимпиада по математике, 2008 год, 10 класс

В таблице размером $5 \times n$, где $n \in N$, каждая клетка покрашена красным или синим цветом. Определите наименьшее возможное значение $n$ такое, что для любой раскраски таблицы можно выбрать 3 строки и 3 столбца, для которых 9 клеток, образованных при их пересечении, имеют одинаковый цвет.

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

Ответ: $ 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 раза