Текст статьиКожевников П. А. Числа в таблицах и ограничения на суммы // Квант. — 2025. — № 9. — С. 34—39.
Цель этой статьи — рассказать об интересном приёме, придуманном
11-классником из Казани Артуром Абзалиловым на Всероссийской олимпиаде при решении трудной задачи 4 для 11 класса (эта задача была включена в «Задачник
«Кванта» под номером М2849). На самом деле этот приём позволяет решить
гораздо более общие задачи со сходной постановкой. Решение Артура на олимпиаде было отмечено специальным призом.
А начнём разговор со следующей несложной «одномерной» задачи.
Задача 1a.Клетки прямоугольника $1\times10$ надо заполнить
неотрицательными числами, не превосходящими 5; при этом сумма чисел в любом
прямоугольнике $1\times3$ не должна превосходить 7. Найдите максимально
возможное значение суммы $S$ всех чисел.
Читатель может решить задачу самостоятельно или обратиться к следующему
упражнению.
Упражнение 1. В условиях задачи 1а получите оценку
сверху на $S$, разбив прямоугольник $1\times10$ подходящим образом на прямоугольники.
А как вам понравится следующее «решение» задачи 1а?
«Решение». Чтобы сделать $S$ наибольшим, надо сделать все суммы
в прямоугольниках $1\times3$ максимально возможными, т. е. равными 7. Тогда
наша расстановка должна быть 3-периодической, т. е. в клетках, отстоящих
друг от друга на 3 (на 3 хода в соседнюю клетку), должны стоять одинаковые
числа. Остаётся рассмотреть 3-периодические расстановки, т. е. расстановки
вида $x$, $y$, $z$, $x$, $y$, $z$, $x$, $y$, $z$, $x$, где $x+y+z\le7$. Но с такими расстановками разобраться уже просто:
$$
S=4x+3y+5z\le x+3(x+y+z)\le5+3\cdot7=26.
$$
Пример, в котором $S=26$, получается, например, при $x=5$, $y=2$, $z=0$.
Вторая часть в «решении» верна: если все суммы в прямоугольниках
$1\times3$ равны между собой, то расстановка 3-периодическая. В самом деле,
пусть в некоторой паре клеток, находящихся на расстоянии 3 друг от друга,
записаны числа $a$ и $d$, а в двух клетках между ними записаны числа $b$ и $c$, т. е. имеется фрагмент $a$, $b$, $c$, $d$; тогда из условия равенства
сумм $a+b+c=b+c+d$ следует $a=d$. И далее с 3-периодическими расстановками
разобрались в самом деле легко.
А вот с начальным рассуждением (сведением к 3-периодической расстановке)
определённо что-то не так... Для начала сделаем наблюдение, которое уже должно насторожить: есть много 3-периодических расстановок, в которых суммы
во всех прямоугольниках $1\times3$ равны 7, но $S\lt26$, причём «выиграть» у таких расстановок может даже непериодическая расстановка, у которой сумма
любых трёх подряд идущих чисел существенно меньше 7. И главное — фраза «НАДО
сделать все суммы в прямоугольниках $1\times3$ максимально возможными»
содержит грубую ошибку: 3-периодичность не является необходимым условием для достижимости максимального значения $S=26$. В следующем упражнении мы предлагаем читателю найти соответствующие примеры.
Упражнение 2. В условиях задачи 1а приведите пример
3-периодической расстановки, для которой сумма любых трёх подряд идущих
чисел равна 7, а общая сумма $S=21$;
непериодической расстановки, в которой $S=23$, а суммы во всех
прямоугольниках $1\times3$ не превосходят 6;
непериодической расстановки, в которой $S=26$.
Итак, в приведённом «решении» есть математические ошибки, причём
исправить их видимо труднее, чем решить задачу 1а «с нуля». Кстати, в настоящее время на запрос дать решение задачи 1а искусственный интеллект,
если он недостаточно мощный и тренированный, выдаёт ошибочные рассуждения, в чём-то похожие на приведённые в «решении».
Тем не менее, факт о том, что в условиях задачи 1а среди расстановок
с максимальной суммой $S$ обязательно найдётся 3-периодическая, верный.
Сейчас мы докажем этот факт в более общей ситуации (см. ниже задачу 1),
но главное, не просто докажем, а научимся вполне конкретным способом из произвольной расстановки получать периодическую расстановку, не нарушая
условий задачи и не уменьшая общую сумму $S$. Это и будет шаг
оптимизации, предложенный А. Абзалиловым. Конечно, задачу 1 несложно решить и без этого (аналогично упражнению 1), но вскоре при решении более сложных задач 2 и 3 мы сможем по-настоящему оценить полезность
этого шага.
Задача 1.Пусть даны натуральные числа $a\le A$, а $m$ и $s$ —
данные положительные числа. В клетки прямоугольника $1\times A$ надо
расставить неотрицательные числа, не превосходящие $m$. Расстановку назовём
допустимой, если сумма чисел в любом прямоугольнике $1\times a$ не превосходит $s$. Найдите максимально возможное значение суммы $S$ всех чисел
в допустимой расстановке.
Лемма 1.В данной допустимой расстановке выделим $a$ подряд
идущих чисел с наибольшей суммой. Теперь заменим исходную расстановку так:
оставим эти $a$ подряд идущих чисел на своих местах, остальные числа сотрём
и далее продолжим расстановку влево и вправо с периодом длины а (пример — на рисунке 1). Тогда:
полученная новая расстановка допустимая;
при этом общая сумма в ней не меньше, чем в исходной расстановке.
Рис. 1
Доказательство леммы 1. Пусть числа в исходной расстановке
образуют последовательность $x_1$, $x_2$, $\ldots$, $x_A$. Пусть выбранные
$a$ чисел — это числа $x_{k+1}$, $x_{k+2}$, $\ldots$, $x_{k+a}$ и их сумма
равна $x$. Так как исходная расстановка допустимая, то $x\le s$.
1) В новой $a$-периодической расстановке сумма чисел в любом
прямоугольнике $1\times a$ будет равна $x$, значит, новая расстановка
допустимая.
2) Теперь оценим общую сумму в новой расстановке. Сделаем это отдельно
для прямоугольника $1\times k$, находящегося слева от $x_{k+1}$, $\ldots$,
$x_{k+a}$ (для прямоугольника, находящегося справа, доказательство
аналогично). В исходной расстановке на первых $k+a$ местах были числа $x_1$,
$x_2$, $\ldots$, $x_{k+a}$. Обозначим $y_1$, $y_2$, $\ldots$, $y_{k+a}$
числа, стоящие на этих местах в новой $a$-периодической расстановке
(рис. 2).
Рис. 2
Разделим $k$ на $a$ с остатком: $k=ta+r$ ($0\le r\lt a$). В силу
максимальности суммы $x$ имеем
$$
\begin{aligned}
x_1+\ldots+x_a&\le x=y_1+\ldots+y_a,\\
x_{a+1}+\ldots+x_{2a}&\le x=y_{a+1}+\ldots+y_{2a},\\
{\ldots}\,{\ldots}&\,{\ldots}\,{\ldots}\,{\ldots}\,{\ldots}\\
x_{(t-1)a+1}+\ldots+x_{ta}&\le x=y_{(t-1)a+1}+\ldots+y_{ta},\\
x_{ta+1}+\ldots+x_{ta+a}&\le x=y_{ta+1}+\ldots+y_{ta+a},
\end{aligned}
$$
В последнем равенстве уберём равные слагаемые $x_{k+1}=y_{k+1}$, $\ldots$,
$x_{ta+a}=y_{ta+a}$ и после этого сложим все равенства. Получим требуемое:
$$
x_1+\ldots+x_k\le y_1+\ldots+y_k.
$$
Лемма 1 доказана.
Самое важное сделано. Теперь мы знаем, что для решения задачи 1 достаточно разобраться с а-периодическими расстановками. В следующем
упражнении мы предлагаем убедиться, что это совсем несложно, и довести
задачу 1 до ответа для конкретных значений параметров.
Упражнение 3. В задаче 1 найдите максимальное
значение $S$ при $A=101$, $a=7$, $m=3$, $s=10$.
Перед тем, как перейти к «двумерному» разговору, предлагаем ещё два упражнения, которые, впрочем, далее не потребуются.
Упражнения
4. Покажите, что доказательство леммы 1 будет
работать, если сумму $x_{k+1}+\ldots+x_{k+a}$ брать наибольшей не среди всех
сумм по $a$ подряд идущих чисел, а лишь среди сумм вида
$x_{k+1}+\ldots+x_{k+a}$, где $k\equiv0~(\text{mod}~a)$ или $k\equiv A~(\text{mod}~a)$.
5. Как изменится ответ в задаче 1, если
параметры $m$ и $s$ одновременно умножить на $\lambda\gt0$?
Сформулируем двумерный вариант задачи — для таблиц $A\times B$ ($A$
строк, $B$ столбцов; здесь и далее при указании размеров всегда будет важен
порядок, скажем, прямоугольники $2\times3$ и $3\times2$ считаем разными).
Задача 2.Пусть $a\le A$, $b\le B$ — данные натуральные числа,
а $m$ и $s$ — данные положительные числа. В клетках таблицы $A\times B$
расставляются числа из отрезка $[0;m]$. Расстановку назовём допустимой, если
сумма чисел в любом клетчатом прямоугольнике $a\times b$ не превосходит $s$.
Найдите наибольшее возможное значение суммы $S$ всех чисел в допустимой
расстановке.
Задача 2 не представляет сложности, если $A\mathrel{\vdots}a$ и $B\mathrel{\vdots}b$, но в общем случае весьма непроста. Читатель может
попробовать свои силы и до нашего обсуждения решить задачу 2 в следующих частных случаях.
Упражнение 6. Решите задачу 2 для $A=B=7$,
$a=b=2$, $m=9$ и а) $s=5$; б) $s=15$.
Обсудим понятие периодичности в двумерном случае, т. е. для расстановок чисел в прямоугольнике. Расстановку чисел назовём
$a$-периодической по вертикали, если в любой паре клеток,
находящихся в одном столбце на расстоянии $a$, стоят равные числа. В $a$-периодической по вертикали расстановке при сдвиге прямоугольника
$a\times b$ по вертикали набор чисел в нём не поменяется, а значит, и сумма
чисел в нём не изменится. Аналогично определим $b$-периодические расстановки
по горизонтали. Наконец, скажем, что расстановка $(a,b)$-периодическая, если
она является одновременно $a$-периодической по вертикали и $b$-периодической
по горизонтали. Ясно, что в $(a,b)$-периодической расстановке во всех
клетчатых прямоугольниках $a\times b$ сумма чисел одна и та же.
В следующем упражнении мы увидим, что обратное утверждение неверно (в
отличие от одномерного случая).
Упражнение 7. Расставьте в бесконечной клетчатой
таблице какие-нибудь числа так, чтобы в любом прямоугольнике $2\times2$
сумма чисел была одна и та же, но расстановка:
не являлась 2-периодической по горизонтали;
не являлась ни 2-периодической по горизонтали, ни 2-периодической по вертикали.
Теперь обсудим задачу 2. Сейчас мы снова применим оптимизационные шаги
А. Абзалилова, чтобы в условиях задачи 2 свести произвольную
допустимую расстановку к допустимой $(a,b)$-периодической расстановке, не уменьшая общую сумму $S$.
Лемма 2.В условиях задачи 2 в данной допустимой расстановке
выделим $b$ подряд идущих столбцов с наибольшей суммой в них. Теперь заменим
исходную расстановку так: оставим неизменными все числа в этих $b$ подряд
идущих столбцах, остальные числа сотрём, а далее продолжим $b$-периодично по горизонтали (пример — на рисунке 3). Тогда:
полученная новая расстановка допустимая;
при этом общая сумма в ней не меньше, чем в исходной расстановке.
Рис. 3
Доказательство леммы 2. Обозначим сумму чисел в $i$-м столбце
через $x_i$; так у нас получается последовательность сумм $x_1$, $x_2$,
$\ldots$, $x_B$. Пусть выбранные $b$ столбцов (с наибольшей общей суммой) —
столбцы с номерами $k+1$, $k+2$, $\ldots$, $k+b$.
1) Каждый прямоугольник $a\times b$ в новой ($b$-периодической по горизонтали) расстановке может быть перенесён по горизонтали в прямоугольник, лежащий в столбцах $k+1$, $k+2$, $\ldots$, $k+b$, т. е. сумма
в нём совпадает с суммой в некотором прямоугольнике $a\times b$ из старой
расстановки. Значит, новая расстановка допустимая.
2) Далее, поймём, что произошло с последовательностью столбцовых сумм
$x_1$, $x_2$, $\ldots$, $x_B$ и с общей суммой $S$. В последовательности
$x_1$, $x_2$, $\ldots$, $x_B$ был выбран блок из $b$ подряд идущих чисел с наибольшей суммой, и далее этот блок был продолжен влево и вправо до $b$-периодической последовательности. Но это преобразование в точности
совпадает с преобразованием последовательности, которое мы рассматривали в «одномерной» лемме 1! Значит, мы уже знаем (из доказательства
леммы 1), что при таком преобразовании общая сумма
$x_1+x_2+\ldots+x_B=S$ не уменьшится. Лемма 2 доказана.
Итак, с помощью леммы 2 мы перешли к новой допустимой расстановке,
которая является $b$-периодической по горизонтали. С полученной расстановкой
проделаем аналогичный «вертикальный» шаг из леммы 2 и получим
расстановку, $a$-периодическую по вертикали. Но, как легко видеть, при выполнении второго шага $b$-периодичность по горизонтали сохранится. Итак,
главная часть решения задачи 2 — сведение к $(a,b)$-периодической
расстановке — состоялась.
Остаётся найти максимальное значение общей суммы $S$ лишь для $(a,b)$-периодических допустимых расстановок. Давайте убедимся на примере с конкретными значениями параметров (как на рисунке 4), что это совсем
несложно.
Пусть на пересечении первых двух строк и первых трёх столбцов стоят числа
$x_{11}$, $x_{12}$, $x_{13}$, $x_{21}$, $x_{22}$, $x_{23}$, далее числа во всех клетках определяются исходя из $(2,3)$-периодичности. Видим, что $x_11$
и $x_12$, встречаются в таблице по $5\cdot4=20$ раз, $x_{13}$ встречается
$5\cdot3=15$ раз, $x_{21}$ и $x_{22}$ встречаются по $4\cdot4=16$ раз,
$x_{23}$ встречается $4\cdot3=12$ раз. Тогда
$$
S=20x_{11}+20x_{12}+16x_{21}+16x_{22}+15x_{13}+12x_{23}.\tag{*}
$$
Это выражение надо максимизировать при ограничениях $0\le x_{ij}\le3$ и $x_{11}+x_{12}+x_{13}+x_{21}+x_{22}+x_{23}\le s=10$. Это уже ясно: сумму
$S=10$ надо «распределить», отдавая по порядку наибольшее возможное значение
переменным в порядке убывания коэффициентов в сумме (*). Конкретно в нашем
случае максимальное $S$ достигается при $x_{11}=x_{12}=3$, $x_{13}=x_{23}=0$
и $x_{21}+x_{22}=4$ (неважно, как эта 4 распределена между $x_{21}$ и $x_{22}$, поскольку коэффициенты в сумме (*) при них равны; годится,
например, $x_{21}=x_{22}=2$ или $x_{21}=3$, $x_{22}=1$). Итак, максимальное
значение $S$ равно 184.
Упражнение 8. В задаче 2 вместо преобразования
таблицы из леммы 2 можно попробовать сделать следующее: выбрать
прямоугольник $a\times b$ с наибольшей суммой и продолжить расстановку чисел
$(a,b)$-периодически, начиная с этого прямоугольника. Приведите пример,
показывающий, что при таком преобразовании общая сумма $S$ может уменьшиться
(т. е. такое преобразование не работает для решения).
Задача 3.Пусть $a\le A$, $b\le B$, $c\le C$ — данные
натуральные числа, а $m$ и $s$ — данные положительные числа. В единичных
кубиках параллелепипеда $A\times B\times C$ расставляются числа из отрезка
$[0;m]$. Расстановку назовём допустимой, если сумма чисел в любом клетчатом
параллелепипеде $a\times b\times c$ не превосходит $s$. Найдите наибольшее
возможное значение суммы $S$ всех чисел в допустимой расстановке.
Свести произвольную расстановку к $(a,b,c)$-периодической снова помогут
оптимизационные шаги, аналогичные рассмотренным выше. Теперь для того чтобы
сделать расстановку периодической вдоль одного из направлений (скажем,
вертикального направления — параллельного ребру $C$), рассмотрим
последовательность сумм $x_1$, $x_2$, $\ldots$, $x_C$ в слоях $A\times
B\times 1$. В этой последовательности выберем $c$ подряд идущих чисел с наибольшей суммой. Теперь заменим исходную расстановку чисел так: оставим
неизменными все числа в выбранных слоях и далее продолжим эту расстановку
$c$-периодично по вертикали. После того, как пришли к периодической
расстановке по одному направлению, повторяем шаги для других направлений.
Таким образом придём к $(a,b,c)$-периодической допустимой расстановке, в которой общая сумма не меньше, чем сумма в исходной расстановке. Читатель
может провести рассуждения подробно и убедиться, что этот приём срабатывает
так же, как и в задаче 2.
Для $(a,b,c)$-периодических расстановок для конкретных значений
параметров решить задачу 3 уже несложно. Рассуждения будут аналогичны
рассмотрению примера к задаче 2. Аналогично задаче 3 формулируется
и решается задача про расстановку чисел в многомерном массиве.
Наконец, поймём, что задача М2849 сводится к задаче 3. Напомним
исходную формулировку.
М2849.Дано натуральное число $N$. Куб с ребром $2N+1$ сложен
из $(2N+1)^3$ единичных кубиков, каждый из которых либо чёрный, либо белый.
Оказалось, что среди любых 8 кубиков, имеющих общую вершину и образующих куб $2\times2\times2$, не более 4 чёрных кубиков. Какое
наибольшее количество чёрных кубиков могло быть использовано?
От раскраски перейдём к расстановке чисел: в белом кубике ставим «0», в чёрном «1». Получается такая формулировка:
Дано натуральное число $N$. В единичных кубиках куба $(2N+1)^3$
расставлены числа $0$ или $1$ так, что в любом кубе $2\times2\times2$ сумма
чисел не превосходит $4$. Какова наибольшая возможная сумма $S$ всех
чисел?
Это почти частный случай задачи 3, с тем отличием, что в задаче 3 мы позволяли расставлять вещественные числа из данного
отрезка, а здесь — только числа из конечного множества $\{0,1\}$. Но это принципиально ничего не меняет: если дискретное множество $\{0,1\}$ заменить
на отрезок $[0;1]$, то рассуждения в оценке сохраняются, а в оптимальном
примере числа всё равно будут целыми: 0 или 1.
Итак, в этой задаче, как и в задаче 3, мы показываем, что максимальное значение $S$ достаточно искать лишь для $(2,2,2)$-периодических
расстановок. Ради полноты, проведём полностью рассуждение с $(2,2,2)$-периодическими расстановками и получим ответ.
Пусть в $(2,2,2)$-периодической расстановке в угловом кубике
$2\times2\times2$ стоят числа $x_{ijk}$, где $i$, $j$, $k$ — номера слоёв по трём направлениям, $i$, $j$, $k\in\{1,2\}$ (эти 8 чисел полностью
определяют $(2,2,2)$-периодическую расстановку). Видим, что $x_{111}$
встречается в большом кубе $(N+1)^3$ раз, $x_{211}$, $x_{122}$, $x_{212}$
встречаются по $N(N+1)$ раз, $x_{221}$, $x_{122}$, $x_{212}$ — по $N^2(N+1)$
раз, наконец, $x_{222}$ встречается $N^3$ раз. Тогда мы максимизируем
линейное выражение
$$
S=(N+1)^3x_{111}+N(N+1)^2(x_{211}+x_{121}+x_{112})+N^2(N+1)
(x_{221}+x_{122}+x_{212})+N^3x_{222}
$$
при заданных ограничениях: все переменные из отрезка $[0;1]$, а их сумма не превышает 4. Коэффициенты в этом выражении упорядочены так:
$$
(N+1)^3\gt N(N+1)^2\gt N^2(N+1)\gt N^3,
$$
поэтому $S$ достигает максимального значения
$$
S=(N+1)^3+3N(N+1)^2
$$
при $$
\colsep{0pt}{\begin{array}{lllllllll}
x_{111}&{}={}&x_{211}&{}={}&x_{112}&{}={}&x_{121}&{}={}&1,\\
x_{221}&{}={}&x_{122}&{}={}&x_{212}&{}={}&x_{222}&{}={}&0.
\end{array}}
$$
Задача решена.
МетаданныеКожевников П. А. Числа в таблицах и ограничения на суммы // Квант. — 2025. — № 9. — С. 34—39.
