ВсОШ 2022, 10 класс — задача 9; 11 класс — задача 8
В вершины правильного -угольника поставили фишек, на которых написаны номера , именно в таком порядке по часовой стрелке. За ход разрешается обменять местами некоторые две фишки, стоящие в соседних вершинах, если номера этих фишек отличаются не более чем на . При каком наименьшем серией таких ходов можно добиться расположения, в котором каждая фишка сдвинута на одну позицию по часовой стрелке (по отношению к своему начальному положению)?
(С. Берлов)
Ответ
Ответ. .
Решение. Пример. Фишку последовательно раз меняем со следующей против часовой стрелки. Получаем требуемое расположение.
Есть несколько способов доказать оценку, ниже мы приводим два из них.
Первый способ. Предположим, что при некотором требуемая расстановка получена.
В каждый момент времени считаем покрашенной дугу от фишки до фишки по часовой стрелке. Так как фишки и нельзя поменять за один ход, каждая конкретная фишка () могла попасть на покрашенную дугу или покинуть покрашенную дугу только путём обмена с одной из фишек или .
Поскольку изначально и в конце фишка не была на покрашенной дуге, она сделала одинаковое количество входов на покрашенную дугу и выходов с покрашенной дуги. При фишка не могла меняться с фишкой , поэтому она могла делать вход или выход только путём обмена с фишкой . При входе фишка совершает сдвиг на по часовой стрелке, а при выходе — на против часовой стрелки. Проведём аналогичные рассуждения для фишек , которые не могут меняться с фишкой .
Тем самым, мы получаем, что фишки и совершат одинаковый сдвиг по и против часовой стрелки, поэтому они останутся на своих позициях. Противоречие.
Второй способ. Будем считать сдвиги фишек относительно их начальной позиции, причём сдвиг по часовой стрелке будет считаться с плюсом, против часовой — с минусом. Тогда при обмене двух фишек к сдвигу одной из них прибавляется , а другой — . Значит, в результате проведённых операций сумма сдвигов будет равна .
Рассуждаем от противного: пусть при каждая фишка в итоге сдвинута на одну позицию по часовой стрелке, т. е. её сдвиг оказался равным (здесь — целое «число оборотов» по часовой стрелке, в частности при фишка сделала оборотов против часовой стрелки). Тогда суммарный сдвиг всех фишек равен . Поскольку он должен равняться , имеем .
Поскольку , фишки с номерами и , где , не могли меняться местами, поэтому их сдвиги в любой момент заведомо отличаются меньше чем на , значит «количества оборотов» и равны при . Отсюда имеем , , ..., . Тогда сумма — чётна, а значит не равна . Противоречие.
Замечание 1. Последнее рассуждение можно видоизменить следующим образом.
Отсюда , , ..., , , , ..., , таким образом, все равны . Тогда .
Замечание 2. Завершить сведение к противоречию можно и по-другому, заменив последний абзац решения на такое рассуждение.
Покрасим красным фишки, для которых , и синим — фишки, для которых . Ясно, что на каком-то ходе синяя и красная фишки должны будут поменяться, поскольку разность их сдвигов не менее . Поскольку , пара фишек и — одного цвета, аналогично пары фишек и , ..., и , и , и , ..., и — одного цвета. Таким образом, все фишки одного цвета. Мы знаем, что , поэтому среди чисел есть как неотрицательные, так и отрицательные, т. е. имеются как красные, так и синие фишки — противоречие.
Только верный ответ.
Баллы за пример и оценку суммируются.
Приведён верный пример.
Есть полное доказательство оценки.
При отсутствии полного доказательства оценки баллы за продвижение (1) не суммируются с баллами за (2а), (2b), (2c); баллы за (2а), (2b), (2c) суммируются.
(1) Присутствует идея отслеживать принадлежность фишек дуге – (или взаимное расположение тройки фишек ).
(2а) Рассмотрены сдвиги и показано, что сумма сдвигов равна .
(2b) В предположении, что фишки в итоге сместились на по часовой стрелке, записано равенство на сумму «количества оборотов».
(2c) Показано, что фишки с разным «количеством оборотов» или с «количеством оборотов» разного знака обязательно менялись местами на каком-то ходе.