Закл 2025

Оценка. Предположим, что какое-то из выписанных на листке чисел больше скажем, Тогда наибольшее из чисел не меньше что больше – противоречие (НОД двух чисел, не превосходящих не превосходит ). Значит, каждый из написанных ов не превосходит потому количество различных ов не может превышать

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

Заметим, что условие равносильно тому, что

или же Рассмотрим граф, вершины которого — записанные на доску числа, а ребро проводится между двумя числами, которые отличаются на Согласно условию задачи, в таком графе ровно 760 рёбер. Каждая компонента связности этого графа представляет собой путь и состоит из вершин-чисел вида …, Предположим, что в этом графе компонент связности. Тогда в нём рёбер, поэтому Поскольку то в какой-то компоненте связности хотя бы 46 вершин, поэтому какие-то две из этих вершин — это числа и Тогда

следовательно,

что и требовалось.

Пусть пара многочленов и — важная. Рассмотрим пары остатков от деления на 100 чисел и где — всевозможные пары целых чисел от 0 до 99. Согласно условию задачи, все такие пары остатков разные. Поскольку всего пар чисел то каждая пара остатков от деления на 100 достигается ровно один раз. Значит, достигаются все 4 возможные пары чётностей чисел Поскольку чётность значения многочлена с целыми коэффициентами в точке зависит только от чётности чисел и мы получаем, что пары значений

дают все четыре возможные пары чётностей. Однако заметим, что для пар многочленов и

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

Положим Введём систему координат так, что все вершины единичных кубиков будут иметь целые координаты от 0 до

Начнём с примера, показывающего, что количество чёрных кубиков действительно может быть равно У каждого кубика рассмотрим его вершину, ближайшую к началу координат (её координаты принимают значения от 0 до ). Пусть кубик чёрный, если хотя бы две координаты этой вершины чётны, и белый иначе. Ясно, что тогда в любом кубе будет ровно 4 чёрных и 4 белых кубика. При этом количество чёрных кубиков, у которых все три соответствующих координаты чётны, равно а количество кубиков, у которых чётны ровно две координаты, равно поэтому общее количество чёрных кубиков будет равно

Осталось доказать, что этот пример оптимальный. Пусть куб сложен из чёрных и белых кубиков так, что выполнены условия задачи. Назовём кубик тёмным или светлым, если он является соответственно чёрным или белым в приведённом выше примере.

Для каждой точки с координатами в большом кубе назовём её - и -рангом соответственно числа

Назовём рангом этой точки число Иначе говоря, - или -ранг точки — это расстояние от неё до ближайшей грани большого куба, перпендикулярной соответствующей оси, а её ранг — это просто расстояние от неё до ближайшей грани большого куба.

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

Скажем, что кратность единичного кубика — это количество его отмеченных вершин (столько раз этот кубик учтён в ). Тогда равна разности суммы всех кратностей чёрных кубиков и суммы кратностей всех белых кубиков. Поэтому нам достаточно доказать, что если такая разность неположительна, то количество чёрных кубиков не превосходит

Пусть и — это -, - и -ранги центра некоторого кубика; пусть для определённости Тогда нетрудно видеть, что

• если то кратность этого кубика равна 4;

• если

  

  где чётно, то кратность кубика меньше 4, и он тёмный;

• если

  

  где нечётно, то кратность кубика больше 4, и он светлый.

Итак, кратности всех тёмных кубиков не больше 4, а всех светлых — не меньше 4.

Пусть теперь

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

поскольку в приведённом выше примере значение было равно 0.

Если теперь в рассматриваемой раскраске чёрных кубиков, то

поскольку Это противоречие показывает, что что и требовалось доказать.

Обозначим записанные по кругу числа …, Вася будет следить лишь за десятью числами, которые он разобьёт на пары: …, За один ход Петя может уменьшить не более, чем одно из этих 10 чисел. Если Петя уменьшил одно из чисел пары Вася в ответ добавит 1 к числам …, Если же Петя не уменьшил ни одно из этих 10 чисел, Вася сделает любой разрешённый ход. Таким образом, после пары ходов Пети и Васи сумма чисел в каждой из пяти Васиных пар не уменьшится. Поскольку изначально пять сумм в парах положительны, то после каждого Васиного хода сумма в каждой из этих пяти пар будет положительной, поэтому в каждой из пар будет хотя бы одно положительное число. Таким образом, после любого Васиного хода будет хотя бы 5 положительных чисел, что и требовалось.