Международная олимпиада 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 на любое нечетное число и ложно для любого

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