Задача 4. Диагонали на огромной доске

Сколько концов помещается в узле

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

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

• В углу доски одна клетка — там кончается не больше $1$ диагонали.
• В узле на краю доски (не в углу) две клетки — не больше $2$ диагоналей.
• Вокруг внутреннего узла четыре клетки, но четыре проведённые диагонали с общим концом запрещены условием. Значит, там кончается не больше $3$ диагоналей.

Идея решения — считать не диагонали, а их концы: в каждом узле их помещается ограниченное число.

Считаем все концы

Сосчитаем узлы. Линий сетки по $2024$ в каждом направлении. Углов $4$. На каждой стороне, кроме двух углов, $2022$ узла, поэтому на краю всего

узлов. Внутренних линий по $2022$ в каждом направлении, поэтому внутренних узлов

Сложим самые большие возможные числа концов из шага 1:

У каждой диагонали ровно два конца, поэтому концов вдвое больше, чем диагоналей. Значит, диагоналей не больше чем

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

Чтобы получилось ровно $6\,140\,816$, в шаге 2 нигде не должно быть недостачи: в каждом углу кончается $1$ диагональ, в каждом узле на краю — $2$, в каждом внутреннем узле — ровно $3$.

Значит, все диагонали, идущие в углы и в узлы на краю, проведены, а во внутренний узел не проведена ровно одна из четырёх.

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

Внутренние узлы образуют квадрат $2022\times 2022$. Число $2022$ чётное, поэтому его можно разбить на квадратики из $2\times 2$ узлов. Каждый такой квадратик — четыре вершины одной клетки; эти клетки и оставим пустыми.

Пример на 6 140 816 диагоналей

Пронумеруем строки и столбцы доски от $1$ до $2023$. Оставим пустыми клетки на пересечении чётных строк и чётных столбцов. Чётных номеров от $2$ до $2022$ всего $1011$, так что пустых клеток $1011^2$. В остальных клетках проведём обе диагонали. Всего диагоналей

Здесь мы воспользовались формулой $a^2-b^2=(a-b)(a+b)$.

Проверим условие. Пронумеруем горизонтальные линии сетки сверху вниз от $0$ до $2023$: строка с номером $k$ лежит между линиями $k-1$ и $k$. Внутренние линии $1, 2, \ldots, 2022$ разбиваются на пары: $1$ и $2$, $3$ и $4$, …, $2021$ и $2022$. Чётная строка $2m$ лежит как раз между линиями своей пары $2m-1$ и $2m$. С вертикальными линиями и столбцами — так же.

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

Вершины пустых клеток лежат только на линиях с номерами от $1$ до $2022$, то есть внутри доски. Поэтому в каждом узле на краю кончаются $2$ диагонали, в каждом углу — $1$, и четырёх концов нет нигде.

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

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

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

Оценка. Углов $4$, узлов на краю $4\cdot 1702=6808$, внутренних $1702^2=2\,896\,804$. В углу кончается не больше $1$ диагонали, на краю — не больше $2$, во внутреннем узле — не больше $3$, поэтому концов не больше

а диагоналей не больше $\frac{8\,704\,032}{2}=4\,352\,016$.

Пример. Оставим пустыми $851^2$ клеток на пересечении чётных строк и чётных столбцов (номера $2, 4, \ldots, 1702$), в остальных проведём обе диагонали:

Внутренние линии $1$–$1702$ снова разбиваются на пары, поэтому каждый внутренний узел — вершина ровно одной пустой клетки и в нём $3$ конца; на краю по $2$, в углах по $1$. Значит, ответ — $4\,352\,016$.