Question

Заполните пропуски так, чтобы получилось верное решение. Докажем оценку в задаче из лекции, а именно, что в клетчатом квадрате 5×5 нельзя провести более 16 диагоналей единичных квадратиков так, чтобы эти диагонали не имели общих точек. Предположим, удалось провести хотя бы 17 диагоналей. Каждая из них имеет 2 конца, расположенных в узлах квадратной сетки (узлом будем называть вершину одной из клеток). Поскольку диагонали не имеют общих точек, каждый узел принадлежит не более чем одной проведённой диагонали. Всего в нашем квадрате узлов. Покрасим некоторые узлы в красный цвет, как показано на рисунке, а остальные — в чёрный. Красных узлов ровно , поэтому и проведённых диагоналей, у которых хотя бы один конец является красным, не более . Существует ровно клеток, в которых можно провести диагональ, соединяющую чёрные узлы. Поскольку всего диагоналей хотя бы 17, то во всех этих клетках должна быть проведена диагональ, соединяющая чёрные узлы. Следовательно, во всех угловых клетках проведена диагональ, как показано на рисунке. Заметим, что узлы, находящиеся в углах квадрата 5×5, не могут быть концом никакой диагонали. Таким образом, концами диагоналей могут являться оставшихся узла. С другой стороны, диагоналей хотя бы 17, поэтому у них суммарно хотя бы конца. Противоречие.