Городская олимпиада по математике среди физ-мат школАлматы, 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$