Высшая проба 2023, 7 класс, задача 6
( баллов) На столе по кругу лежат монет, пронумерованных числами от до в некотором порядке. За одну операцию разрешается взять какую-то монету с номером и переместить её на позиций в произвольном направлении, сместив при этом промежуточные монеты (например, операция над монетой с номером может быть выполнена одним из двух способов, показанных на рисунке ниже). Докажите, что из любого начального положения можно получить такое, в котором, начиная с некоторого места, монеты лежат по часовой стрелке.
Решение. Покажем, что любую монету, кроме и , некоторой последовательностью операций можно поменять местами с соседней монетой, сохранив при этом порядок остальных монет. Рассмотрим монету , где . Убедимся, что среди следующих подряд идущих монет по часовой стрелке нет монеты . Если это не так, просто выведем за пределы этой области, обменивая её последовательно с какими-то монетами. Теперь совершим нашей монетой операцию по часовой стрелке. Далее поставим монету перед монетой и совершим монетой операцию против часовой стрелки. В итоге монета поменяется местами со следующей за ней по часовой стрелке (рис. ).
Положение остальных монет, кроме монеты , друг относительно друга не поменяется, поэтому монету можно вернуть на место, на котором она была до этих операций. Заметим, что теперь мы умеем менять местами любые две соседние монеты, кроме пары , так как в любой другой паре есть хотя бы одна монета, отличная от и . Тогда легко поставить монеты в нужном порядке: поставим после монеты по часовой стрелке монету , затем за ней монету и т. д. Когда мы поставим на место монету , монета автоматически окажется между монетами и , то есть получится требуемая расстановка.
Другое решение. Рассмотрим некоторый отрезок из монет (т. е. последовательно лежащих монет), среди которых нет монеты . Определим процедуру «вылупления», в ходе которой будем двигать монеты внутри этого отрезка, и докажем, что по окончании процедуры крайняя правая монета отрезка (первая, если идти против часовой стрелки) будет иметь номер не меньше .
Процедура «вылупления» состоит в том, чтобы последовательно брать крайнюю правую монету отрезка, и если её номер меньше , то перемещать её влево с помощью нашей операции. Так как сам отрезок имеет длину , то перемещаемая монета за его пределы не выйдет. Если номер крайней правой монеты оказывается не меньше , то процедура заканчивается. Докажем, что процедура закончится за конечное число шагов. Действительно, предположим, что в ходе процедуры мы сделаем бесконечное число операций. Тогда к некоторым монетам операция должна быть применена бесконечное число раз. Из таких монет выберем монету с наибольшим номером, пусть это . Каждый раз, когда мы перемещаем монету влево, справа от неё (в пределах отрезка) оказываются других монет; ясно, что прежде чем мы опять дойдём до монеты , мы к ним ко всем применим операцию хотя бы по одному разу. Но хотя бы одна из них имеет номер, больший . Значит, между каждыми двумя применениями операции к должно произойти применение операции к монете с номером, большим . Следовательно, таких операций тоже бесконечное количество; тогда существует монета с номером, большим , к которой операция применялась бесконечное число раз. Противоречие с выбором номера . Теперь, когда процедура «вылупления» определена корректно, с её помощью легко получить требуемое. Рассмотрим монету . Все остальные монеты образуют отрезок из монеты. Процедурой «вылупления» добьёмся, чтобы правая из них имела номер (других монет с номером, не меньшим , там нет). Теперь все монеты, кроме и , образуют отрезок из монет; «вылуплением» добьёмся, чтобы с правого конца стояла
монета . Аналогично продолжая процесс, будем последовательно получать монеты , ... в порядке против часовой стрелки, пока не дойдём до и . Это и есть требуемая в условии расстановка
Используется наибольший подходящий критерий.
20 б. Любой верный алгоритм с обоснованием.
6 б. Задача сведена к доказательству следующего утверждения: в ряд стоят монеты от 0 до, причём монеты от 0 дорасположены в порядке возрастания (а монетав произвольном месте этого ряда). Тогда, применяя к этим монетам операции из условия задачи и не выходя за пределы ряда, их можно расположить в порядке возрастания от 0 до.
3 б. Утверждается, но не доказывается или доказывается неверно, что если для некоторого<удалось расположить подряд монеты от 0 до, то монеты из промежутка между монетамииможно удалить так, чтобы ни одна из них не оказалась между какими-то двумя из монет,...,.