Городская олимпиада по математике среди физ-мат школАлматы, 2013 год

Прямоугольная решетка состоит из 4 горизонтальных и 7 вертикальных прямых. Некоторые узлы решетки покрашены, общее количество таких узлов равно 14. Докажите, что найдется хотя бы один прямоугольник с вершинами в покрашенных узлах со сторонами параллельными линиям решетки.

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

Чтобы получился прямоугольник , нужно, чтобы в двух столбцах имелись узлы с одинаковыми номерами строк.

Лемма 1. 4 закрашенных узла гарантируют прямоугольник.

Доказательство. Пусть в $j $-том столбце имеется 4 закрашенных узла. Пусть в $k $-том столбце 2 закрашенных узла под номерами строк $m $ и $n $. Но $m, n\in {1,2,3,4}=> $можно найти одинаковые номера строк и образовать прямоугольник. Если же в столбцах будет по 1 закрашенному узлу , то сумма всех узлов будет $4+6 <14$

Лемма 2. Два столбца по 3 закрашенных узла гарантируют прямоугольник.

Доказательство. Пусть в $i $-том и $j $-том столбцах имеется по 3 закрашенных узла. Пусть в $i $-том столбце закрашены узлы номер $a,b,c $, где $a,b,c\in {1,2,3,4} $. Даже если один из закрашенных узлов будет номер $d $ , то два оставшихся узла будут из множества $a, b, c $. На таких узлах и натянется прямоугольник.

Лемма 3. 3 закрашенных узла в столбце гарантируют прямоугольник.

Доказательство. Пусть в $i $-том столбце закрашены узлы номер $a,b,c $. По леммам 2 и 1 имеем ,что в остальные столбцы можно закрашивать 1 или 2 узла. Чтобы не образовывался прямоугольник, один из закрашенных узлов в каждом столбце, кроме $i $-того , должен стать номер $d $. Иначе, номера узлов $i $-того столбца и произвольных двух совпадут, и образуется прямоугольник. Тогда мы разместим 9 элементов : 3 в столбце $i $, 6 в строке $d $. Оставшиеся 5 элементов разместим по 3 строкам. Обязательно найдется 2 узла на одной строке (по теореме Дирехле ), и прямоугольник замкнется с одноименными узлами строки $d $

Лемма 4. Если размещать в столбцах по 2 узла, то это гарантирует прямоугольник.

Доказательство : Вариантов закраски узлов $6$:$1-2;1-3;1-4;2-3;2-4;3-4$ . А столбцов 7. Отсюда следует, что хотя бы один из вариантов повторится. А это значит, что в повторных узлах образуется прямоугольник.

Суммируя леммы 1-4, можно сказать, что прямоугольник будет при любой расстановке 14 узлов на 28 узловой сетке $4\times 7$