Задача 4. Диагонали в тетради

Где могут сойтись четыре диагонали

Концы диагоналей — вершины клеток, то есть точки, где пересекаются линии сетки. Назовём их узлами.

Какие диагонали могут кончаться в данном узле? Только диагонали клеток, у которых этот узел — вершина. И из каждой такой клетки — ровно одна: вторая диагональ клетки соединяет две другие её вершины.

• В углу доски одна клетка — там кончается не больше одной диагонали.
• В узле на краю доски две клетки — не больше двух диагоналей.
• Во внутреннем узле сходятся четыре клетки — там могут кончаться четыре диагонали, по одной из каждой клетки.

Значит, условие задачи касается только внутренних узлов: в каждом из них хотя бы одна из четырёх диагоналей, идущих в этот узел, не проведена. Внутренних линий сетки по $8$ в каждом направлении, поэтому внутренних узлов

Считаем непроведённые диагонали

В каждой из $81$ клетки можно провести две диагонали, всего $2\cdot 81=162$. Непроведённую диагональ назовём пропуском. Удобнее считать пропуски: чем их меньше, тем больше диагоналей проведено.

По шагу 1 в каждом из $64$ внутренних узлов должен кончаться хотя бы один пропуск.

У пропуска два конца. Поэтому один пропуск обслуживает не больше двух внутренних узлов, а у края доски — даже меньше, ведь там один его конец лежит на краю.

Значит, пропусков не меньше чем

а проведённых диагоналей не больше чем

Как догадаться до примера

Чтобы получилось ровно $130$, пропусков должно быть ровно $32$. Тогда у них ровно $32\cdot 2=64$ конца — столько же, сколько внутренних узлов. Значит, у каждого пропуска оба конца внутренние, а два пропуска никогда не кончаются в одном узле.

Удобно брать пропуски парами: оставим клетку пустой — обе её диагонали станут пропусками и вместе обслужат все четыре вершины клетки. Нужно выбрать пустые клетки так, чтобы их вершины были как раз всеми $64$ внутренними узлами, причём каждый узел — вершиной только одной пустой клетки.

Внутренние узлы образуют квадрат $8\times 8$. Разобьём его на $16$ квадратиков из $2\times 2$ узлов: каждый такой квадратик — это четыре вершины одной клетки. Эти $16$ клеток и оставим пустыми.

Пример на 130 диагоналей

Пронумеруем строки и столбцы доски от $1$ до $9$. Оставим пустыми $16$ клеток на пересечении чётных строк и чётных столбцов (с номерами $2$, $4$, $6$, $8$), а в остальных $81-16=65$ клетках проведём обе диагонали. Всего

диагоналей.

Проверим условие. Пронумеруем горизонтальные линии сетки снизу от $0$ до $9$: строка с номером $k$ лежит между линиями $k-1$ и $k$. Внутренние линии разбиваются на пары $1$ и $2$, $3$ и $4$, $5$ и $6$, $7$ и $8$, и чётная строка $2m$ лежит как раз между линиями своей пары $2m-1$ и $2m$. С вертикальными линиями и столбцами — так же.

Возьмём любой внутренний узел. Его горизонтальная линия входит ровно в одну пару, и эта пара задаёт одну чётную строку; вертикальная линия задаёт один чётный столбец. Значит, узел — вершина ровно одной пустой клетки. Диагональ этой клетки, идущая в узел, не проведена, поэтому в узле кончаются три диагонали, а не четыре. На краю и в углах доски больше двух диагоналей не кончается никогда.

Итак, $130$ диагоналей провести можно, а больше — нельзя по шагу 2.

Второй вариант

Меняется только размер доски: $11\times 11$ вместо $9\times 9$.

Оценка. Всего можно провести $2\cdot 121=242$ диагонали. Четыре диагонали могут сойтись только во внутреннем узле, а их $10\cdot 10=100$. В каждом должен кончаться пропуск, один пропуск обслуживает не больше двух узлов, поэтому пропусков не меньше $\frac{100}{2}=50$ и диагоналей не больше

Пример. Оставим пустыми $25$ клеток на пересечении строк и столбцов с номерами $2$, $4$, $6$, $8$, $10$, а в остальных $121-25=96$ клетках проведём обе диагонали: $2\cdot 96=192$. Внутренние линии сетки разбиваются на пары $1$ и $2$, $3$ и $4$, …, $9$ и $10$, поэтому каждый из $100$ внутренних узлов — вершина ровно одной пустой клетки, и в нём кончаются три диагонали. Значит, ответ — $192$.