Международная олимпиада 2021, Санкт-Петербург, Россия, 2021 год

Чип и Дейл собрали на зиму 2021 орешек. Чип пронумеровал орешки числами от 1 до 2021 и вырыл 2021 маленькую ямку вокруг их любимого дерева. На следующее утро он обнаружил, что Дейл положил в каждую ямку по орешку, ничуть не беспокоясь о порядке. Расстроившись, Чип решил переупорядочить орешки посредством следующей последовательности из 2021 действия: во время $k$-го действия он меняет местами орешки, соседние с орешком под номером $k$. Докажите, что найдётся такое число $k$, что во время $k$-го действия поменялись местами орешки с номерами $a$ и $b$ такими, что $a < k < b$.

Комментарий/решение

Этот процесс занимает ровно 2021 шаг. Сразу после k-го хода рассмотрим ситуацию

где мы также покрасили грецкий орех k в красный цвет, так что на k-м шаге осталось k единиц. Для краткости некрасный орех называют черным. Пример показан ниже, где 2021 заменен на 6.

Утверждение: на каждом этапе грецкий орех, который становится красным, находится между двумя некрасными или двумя красными грецкими орехами.

Доказательство. По определению.

С другой стороны, если имеется 2021 грецких орехов, то получается паритетное препятствие этому

упрощенный процесс:

Доказательство. После первой ступени идет блок черных грецких орехов 2020 года. 9

Утверждение: после первого шага всегда имеется последовательный блок черных грецких орехов положительной четной длины.

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

Замечание. Утверждение верно, если 2021 заменить любым нечетным числом, и ложно для любого четного числа.

Мотивация исходит из следующей перефразировки проблемы:

Начните со всех нулей и на каждом шаге меняйте 0 между двумя совпадающими числами.

от 0 до 1.

Хотя на первый взгляд может показаться, что аргумент раскраски (или 0/1) теряет информацию, я думаю, что он должен быть эквивалентен исходному процессу; «лишняя» информация сводится к выбору того, какой орех покрасить в красный цвет на каждом этапе.

Предположим, от противного, что такого k не существует.

Этот процесс занимает ровно 2021 шаг. Сразу после k-го хода рассмотрим ситуацию

где мы также покрасили грецкий орех k в красный цвет, так что на k-м шаге осталось k единиц. Для краткости А.

некрасный орех называется черным. Пример показан ниже, где 2021 заменен на 6.

Начальный 1

2 4

5

3 6

1

2 6

5

3 4

1

5

2

6

3 4

1

2 5

4

3

6

1

3 5

4

2 6

1

5 3

4

2 6

1

3 5

4

2 6

Утверждение: на каждом этапе грецкий орех, который становится красным, находится между двумя некрасными или двумя

красные грецкие орехи.

Доказательство. По определению.

С другой стороны, если имеется 2021 грецких орехов, то получается паритетное препятствие этому

упрощенный процесс:

Утверждение — После первого шага всегда идет последовательный блок черных грецких орехов.

положительная четная длина.

Доказательство. После первой ступени идет блок черных грецких орехов 2020 года.

После этого обратите внимание, что блок черных грецких орехов длиной 2 нельзя менять. Тем временем

для четных длин не менее 4, если внутрь положить красный грецкий орех, брусок четной длины

разбивается на блок нечетной длины и блок четной длины.

Замечание. Утверждение верно при замене 2021 на любое нечетное число и ложно для любого

четное число.

Задача имеет очень очень легкое решение.

От обратного. В начале красим все как О. После каждой операции красим орех $k$ как Х. Допускаем что операция на орехи ХОО или ООХ не выполняется - что эквивалентно условию задачи. Будем оценивать количество ХХ- 2 подряд идущих ореха над которыми проведена операция. Пусть кол-во равно Н до того как пройдет операция над тремя орехами. После операции, Н либо не меняется когда орехи покрашены из ООО в ОХО, либо увеличивается на 2 когда они покрашены из ХОХ в ХХХ. Тогда четность Н сохраняется.

Изначально она равна 0, а в конце 2021. Противоречие, хотя бы одна операция была проведена на ООХ или ХОО.

Мое изначальное решение:

Красим как в решении сверху. Допустим что можно из ОООО....ООО дойти до ХХХХ....ХХХ так что операция не проведена на ООХ или ХОО. Будем решать обратную, эквивалентную задачу:

Постараемся дойти из ХХХХ...ХХХ до ОООО...ООО следующими ходами: из ОХО красим орехи в ООО и из ХХХ в ХОХ. Докажем что до ОООО...ООО не доберемся. После первого хода всего один О и остальные ХХХ.

Утверждение- ненулевые последовательные орехи ХХ...Х (назовем лентой) четной длины нельзя покрасить данными операциями в О так чтобы было меньше 2-ух орехов Х. Для удобства покажем любую ленту Х...Х как ОХ...ХО. Дальше по индукции:

База для ОХХО разбором убедимся что нельзя довести его до менее чем 2-ух орехов Х.

Шаг: пусть данное верно для 2,...,2m. Докажем что для ленты ХХ..Х длины 2m+2 утверждение тоже верно. Берем ОХХ...ХХО с 2m+2 последовательными Х. Операции вне пределов ОХ..ХО не влияют на него. Если провести операцию то мы не можем красить крайние Х, тогда лента распадается на две ленты ХХ..Х, одна четной и одна нечетной длин. При этом четную ленту нельзя довести до меньше 2-ух орехов.

После 1ой операции у нас лента Х..Х длины 2020- значит до О..О не доберемся. А если из Х...Х до О...О данными операциями не доберемся, то из О...О до Х...Х тоже.

Если решали задачу и подбирали для 3, 4, 5 вместо 2021- то могли заметить что для 3 и 5 задача такая же но для 4 можно легко построить контр-пример. Из этого подсказка что нечетность чего-то решает. Надо лишь что-то посчитать какое-то количество которое имеет четность с 2021 но при этом по операциям должно сохранять для 0.

Для четного количества орехов 2а всегда есть контр-пример: красим ямы в черный и белый чередуя, в черные ложим половину чисел 1 до а, остальные в белый. По операциям в черных числа всегда не больше а, а в белых всегда больше а. Каждое число тогда либо больше, либо меньше своих соседей.