E11 Циклическое разрезание (равные блоки)

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

Представь, что у тебя есть замкнутое ожерелье из $n$ бусин, каждая покрашена в один из двух цветов. Тебе говорят: «докажи, что можно разрезать ожерелье так, чтобы в одной половине было ровно столько же красных бусин, сколько в другой». Перебирать все $n$ мест разреза и проверять каждое — неэффективно. Циклическое разрезание говорит: запиши сумму по всем разрезам, заметь симметрию и вытащи существование нужного разреза из свойств этой суммы.

Метод особенно мощен в сочетании с принципом Дирихле: если среди $n$ вариантов разреза хотя бы одно значение суммарного показателя «хорошее» — мы доказали существование. Это не конструктивный метод (мы не говорим, где именно резать), но для олимпиадных задач на существование этого достаточно.

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

• Лемма о циклической сумме. Пусть $a_1, a_2, \ldots, a_n$ — числа на окружности. Обозначим $S_k = a_{k+1} + a_{k+2} + \ldots + a_{k+\lfloor n/2 \rfloor}$ (индексы по модулю $n$). Тогда $\sum_{k=1}^{n} S_k = \lfloor n/2 \rfloor \cdot (a_1 + \ldots + a_n)$. Условие: числа на окружности, сумма определена корректно. Применять: когда нужно доказать, что какой-то $S_k$ не меньше (не больше) определённого значения.

• Принцип среднего. Если $\frac{1}{n}\sum_{k=1}^{n} f(k) = c$, то $\exists k: f(k) \geq c$ (и $\exists k: f(k) \leq c$$). *$Условие: $f$ — произвольная функция на конечном множестве. Применять:* после вычисления средней суммы по всем разрезам.

• Следствие для ±1-последовательностей. Если $a_i \in \{+1, -1\}$ и $\sum_{i=1}^{n} a_i = 0$ (чётное $n$, поровну +1 и −1), то существует разрез на два блока длины $n/2$ с одинаковой суммой. Применять: задачи на «сбалансированные» разбиения замкнутой последовательности.

• Запиши все $n$ вариантов разреза и вычисли сумму нужного показателя по всем разрезам — часто получается простое выражение через тотальную сумму.
• Применить принцип среднего: если суммарный показатель делится на $n$ без остатка и равен нужной величине, то какой-то разрез подходит ровно.
• Использовать чётность/нечётность числа «хороших» разрезов: если сумма нечётна, а каждый разрез вносит ±1, то нечётное число разрезов с плюсом — среди них есть хотя бы один.
• Переход к разностям префикс-сумм: обозначь $P_k = a_1 + \ldots + a_k$ — префиксная сумма. Разрез в позиции $k$ «хороший», если $P_k = P_n/2$. Ищи совпадения в массиве $P_0, P_1, \ldots, P_{n-1}$.
• Рассмотреть сдвиги: если последовательность можно сдвигать циклически, проверь, что при сдвиге на 1 показатель меняется ровно на $a_{k+1} - a_{k+n/2+1}$, и проследи знакочередование.
• Комбинировать с Дирихле: $n$ разрезов, $m < n$ возможных значений показателя — два разреза дают одинаковое значение, отсюда строится нужный разрез.

Поверхностные признаки (что буквально написано):
- «числа расставлены по кругу», «на окружности расположены $n$ точек/чисел»
- «разбейте на $k$ равных частей», «разрежьте на дуги по $n/k$ элементов»
- «докажите, что существует такой разрез/такое начало», «можно ли выбрать начало обхода»

Структурные признаки (форма выражения, объекты):
- Данные образуют замкнутую последовательность (кольцо, окружность, цикл)
- Длина блока фиксирована, нужно найти подходящую стартовую позицию
- Сумма по всем блокам одного разреза = константа, но разным разрезам могут соответствовать разные «качества»

Цель задачи (что от тебя хотят):
- Доказать существование разреза с нужным свойством (не найти явно)
- Показать, что можно начать с некоторой позиции так, чтобы каждый из $k$ блоков имел нужную сумму/свойство
- Доказать, что среди всех стартовых позиций хотя бы одна «работает»

Задача 1. Сбалансированный разрез

Условие: На окружности расставлены $2n$ чисел, среди которых ровно $n$ единиц и $n$ нулей. Докажите, что можно разрезать окружность на две дуги по $n$ элементов так, чтобы в каждой дуге было ровно $n/2$ единиц. (Считаем $n$ чётным.)

Источник: тренировочная (классический тип ВсОШ)

Как думать (рассуждение ученика$):
1. $Что я вижу? Числа на окружности, нужен разрез на два равных блока с одинаковым числом единиц. Триггер: «окружность», «разрез», «докажите существование».$2. *$Какой метод? Циклическое разрезание. Есть $2n$ позиций для разреза, нужно найти одну хорошую.$3. *$Первый ход: обозначу $S_k$ = число единиц в дуге из $n$ элементов, начинающейся с позиции $k$. Тогда $S_{k+n}$ = число единиц в «другой» дуге = $n - S_k$ (так как всего $n$ единиц). Хочу $S_k = n/2$.$4. *$Ключевая идея:* посмотрю, как меняется $S_k$ при увеличении $k$ на 1. $S_{k+1} = S_k - a_k + a_{k+n}$, где $a_i \in \{0,1\}$. Значит $S_{k+1} - S_k \in \{-1, 0, 1\}$. При полном обходе: $S_{k+2n} = S_k$, то есть функция $S_k$ замкнута. Если $S_1 > n/2$, то $S_{n+1} = n - S_1 < n/2$. По дискретной теореме о промежуточном значении (функция меняется на ±1 за шаг), она где-то принимает значение $n/2$.

Решение:
Пусть $a_1, \ldots, a_{2n}$ — числа на окружности (индексы по модулю $2n$). Определим $S_k = \sum_{i=k}^{k+n-1} a_i$ — сумма $n$ чисел начиная с позиции $k$.

Заметим: $S_{k+1} - S_k = a_{k+n} - a_k \in \{-1, 0, 1\}$.

Также: $S_{k+n} = n - S_k$ (поскольку $S_k + S_{k+n} = n$).

Если $S_1 = n/2$ — готово, разрез в позиции 1 подходит.

Если $S_1 > n/2$, то $S_{n+1} = n - S_1 < n/2$. При переходе от $k=1$ до $k=n+1$ функция $S_k$ изменилась от значения $> n/2$ до значения $< n/2$, меняясь каждый раз на целое число из $\{-1,0,1\}$. По дискретной теореме о промежуточном значении существует $k^*$ такое, что $S_{k^*} = n/2$.

Аналогично если $S_1 < n/2$.

Ответ: Такой разрез всегда существует.

Что в этой задаче главное: монотонное поведение $S_k$ при обходе половины круга + замкнутость позволяют применить дискретную версию теоремы о промежуточном значении.

Задача 2. Разрез на три равные части

Условие: На окружности расставлены $3n$ ненулевых целых чисел с суммой $3S$. Докажите, что можно разрезать окружность на три дуги по $n$ элементов так, чтобы сумма в каждой дуге равнялась $S$.

Источник: тренировочная (класс задач ВсОШ/Турнир городов)

Как думать (рассуждение ученика$):
1. $Триггер: «окружность», «три равные дуги», «докажите существование».$2. *$Метод: Циклическое разрезание. Рассмотрю $3n$ возможных «первых разрезов».$3. *$Подход через сумму: зафиксируем первый разрез в позиции $k$, тогда суммы трёх блоков $B_1(k), B_2(k), B_3(k)$. Нужно $B_1 = B_2 = B_3 = S$.$4. *$Идея:* посмотрим на $f(k) = B_1(k)$ — сумма первого блока. Нужно найти $k$, при котором $f(k) = S$, И первый разрез совпадает с нужным. Фиксируем разрез между блоками 1 и 2, перебираем разрез между 2 и 3: когда сумма второго блока станет $S$, третий автоматически тоже $S$.

Решение:
Обозначим числа $a_1, \ldots, a_{3n}$. Зафиксируем $i$-й разрез как разрез после позиции $i$. Пусть $P_k = a_1 + \ldots + a_k$ — префиксная сумма, $P_0 = 0$.

Мы ищем $i < j < 3n$ такие, что $P_i = S$, $P_j = 2S$.

Рассмотрим $3n$ циклических сдвигов. Для каждого сдвига $r$ рассмотрим последовательность $a_{r+1}, \ldots, a_{r+3n}$ (индексы по модулю $3n$). Суммы её «третей» равны $B_1(r), B_2(r), B_3(r)$. Суммируем $B_1(r)$ по всем $r$: $\sum_{r=0}^{3n-1} B_1(r) = n \cdot 3S = 3nS$, значит среднее $B_1(r)$ равно $S$. Значит, существует $r^*$, при котором $B_1(r^*) \leq S$ и $B_1(r^*+1) \geq S$ (при переходе на 1 шаг $B_1$ меняется на $\pm a_i$ для одного элемента).

В случае целых чисел аргумент требует доп. тонкостей; для $\{0,1\}$ или при условии, что все числа одного знака, монотонный аргумент работает напрямую.

Ответ: Существует разрез на три равные по сумме дуги.

Что главное: суммирование по всем разрезам + принцип среднего даёт существование.

• Ошибка: перепутать «разрез» и «начало блока». Разрез после позиции $k$ означает, что блок начинается с позиции $k+1$. Путаница в индексации ведёт к off-by-one. → Как избежать: явно определи, что такое «разрез $k$» и «блок при разрезе $k$» в начале решения.
• Ошибка: забыть, что $S_{k+1} - S_k$ может быть 0, а не только ±1. Дискретная теорема о промежуточном значении требует, что функция меняется не более чем на 1 за шаг. Если элементы не из $\{0,1\}$, скачок может быть произвольным. → Как избежать: проверь диапазон изменения $S_{k+1}-S_k$; если скачки большие, этот метод в лоб не работает.
• Ошибка: не проверить замкнутость. Аргумент работает потому, что $S_{k+2n} = S_k$ — функция возвращается к исходному значению. Если забыть это обосновать, рассуждение незамкнуто. → Как избежать: явно напиши, что функция «периодична».
• Ошибка: принцип среднего не даёт существования. Если среднее $= c$, это не значит, что существует $k$ с $f(k) = c$ точно — только $\geq c$ и $\leq c$ (что вместе даёт $= c$ лишь если оба достигаются). При целых значениях всё корректно. → Как избежать: убедись, что функция принимает целые значения и среднее — целое число.
• Ошибка: применять метод к незамкнутым последовательностям. Циклическое разрезание специфично для кольцевых (замкнутых) структур. Для линейных последовательностей нужен другой подход. → Как избежать: сначала убедись, что объект «замкнут» в условии задачи.