Эйлер 2026 · Математика · 8 кл., №4 — решение

Условие

В электронную таблицу, где две строки и $n$ столбцов, в произвольном порядке записаны все натуральные числа от 1 до 2n (в каждой клетке — одно число). В полдень каждого дня компьютер случайным образом выбирает столбец, где число из верхней строки больше числа из нижней, и меняет эти два числа местами, а затем случайным образом переставляет числа в верхней строке. В момент, когда в каждом столбце верхнее число оказывается меньше нижнего, процесс заканчивается. Докажите, что такой процесс не может происходить дольше, чем $n^2$ дней.

О задаче · 8 класс

Олимпиада: Олимпиада имени Леонарда Эйлера, XVIII олимпиада
Этап: Региональный этап
Предмет / класс: Математика · 8 класс
Дата: 2–3 февраля 2026

Выполни несколько допустимых обменов и перестановок на маленькой таблице. Попробуй найти число, которое обязательно меняется в одну сторону.

Здесь нужен обоснованный словесный ответ. Запиши свой вывод и доводы до открытия помощи.

Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Исследуй задачу

Самостоятельное исследованиеСледи за суммой

Пробуй свои варианты. Разбор останется закрытым.

Своя гипотеза

Следи за суммой

Выбирай столбец и перестановку верхней строки в малом примере n=3. Следи за суммой после каждого дня.

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

Подсказка 1

Что не меняется от перестановки верхней строки, но меняется при обмене чисел одного столбца?

Подсказка 2

Оцени наибольшую и наименьшую сумму n чисел из набора от 1 до 2n. На сколько минимум она уменьшается за один день?

Разобрать решение по шагам

Выбираем величину для наблюдения

Будем считать сумму чисел верхней строки. Если верхнее число $x$ больше нижнего $y$ то после их обмена сумма уменьшается на $x-y$ Все числа целые и различные, поэтому $x-y\ge1$ Последующая перестановка чисел в верхней строке сумму не меняет.

Находим весь запас уменьшения

Максимальная сумма сверху получается из $n$ самых больших чисел:

(n+1)+\ldots+2n=\frac{n(3n+1)}2.

Минимальная — из $n$ самых маленьких:

1+\ldots+n=\frac{n(n+1)}2.

Их разность равна

\frac{n(3n+1)-n(n+1)}2=n^2.

Больше n² обменов не получится

Каждый день процесса уменьшает сумму хотя бы на единицу. Если бы обменов стало больше $n^2$ сумма опустилась бы ниже своего возможного минимума. Значит, не позже чем после $n^2$ обменов допустимых столбцов не останется. Никакое везение при случайном выборе не требуется: доказательство охватывает все варианты.

Проверка

Начальный запас суммы не больше n². Каждый допустимый обмен уменьшает его хотя бы на 1, а перестановка не восстанавливает потерю. Это верно для любого порядка выборов.

Ответ

Процесс не может продолжаться дольше $n^2$ дней.

Ответ

Процесс не может продолжаться дольше $n^2$ дней.

Главная идея

За случайными перестановками следи за суммой, которую перестановка не меняет, а обмен обязательно уменьшает.

Если элементы постоянно переставляют, ищи величину для всего набора, которую перестановки не меняют.

Где легко ошибиться

Следить за отдельным столбцом: перестановка верхней строки разрушает его историю. Сумма всей строки переживает любую перестановку.

Источник и авторство

Олимпиада имени Леонарда Эйлера · XVIII олимпиада, сезон 2025/26 · региональный этап · первый день · 2–3 февраля 2026 · математика · 8 класс. Официальная задача 4, 7 баллов.

Условия задач (PDF организатора) ↗ · Решения организатора, день 1 ↗ · Решения организатора, день 2 ↗ · Архив олимпиады ↗

Условие — из официального файла организатора. Подсказки, объяснение и модели — Popov Academy. Авторский разбор Popov Academy.

Продолжить тему: Преобразования и процессы →

Тема, знания и приёмы

Преобразования и процессы · Начальный вход

Сумма последовательных чисел
Целые положительные разности

Приёмы решения: Инвариант или монотонная величина · Оценка и достижимость

Задать вопрос по задаче →