Question

Заполните пропуски так, чтобы получилось верное решение.


Докажем оценку в задаче из лекции, а именно, что в клетчатом квадрате 5×5 нельзя провести более 16 диагоналей единичных квадратиков так, чтобы эти диагонали не имели общих точек.


Предположим, удалось провести хотя бы 17 диагоналей. Каждая из них имеет 2 конца, расположенных в узлах квадратной сетки (узлом будем называть вершину одной из клеток). Поскольку диагонали не имеют общих точек, каждый узел принадлежит не более чем одной проведённой диагонали.


Всего в нашем квадрате

"какое-то число" узлов. Покрасим некоторые узлы в красный цвет, как показано на рисунке, а остальные — в чёрный.




Красных узлов ровно

"какое-то число"

, поэтому и проведённых диагоналей, у которых хотя бы один конец является красным, не более

"какое-то число"

. Существует ровно

"какое-то число"

клеток, в которых можно провести диагональ, соединяющую чёрные узлы. Поскольку всего диагоналей хотя бы 17, то во всех этих клетках должна быть проведена диагональ, соединяющая чёрные узлы. Следовательно, во всех угловых клетках проведена диагональ, как показано на рисунке.




Заметим, что узлы, находящиеся в углах квадрата 5×5, не могут быть концом никакой диагонали. Таким образом, концами диагоналей могут являться

"какое-то число"

оставшихся узла. С другой стороны, диагоналей хотя бы 17, поэтому у них суммарно хотя бы

"какое-то число"

конца. Противоречие.