Двойной подсчёт

Пример. Фишку 50 последовательно 99 раз меняем со следующей против часовой стрелки. Получаем требуемое расположение.

Есть несколько способов доказать оценку, ниже мы приведём два из них.

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

В каждый момент времени считаем покрашенной дугу от фишки 100 до фишки 1 по часовой стрелке. Так как фишки 100 и 1 нельзя поменять за один ход, каждая конкретная фишка могла попасть на покрашенную дугу или покинуть покрашенную дугу лишь путём обмена с одной из фишек 1 или 100.

Поскольку изначально и в конце фишка не была на покрашенной дуге, она сделала одинаковое количество входов на покрашенную дугу и выходов с покрашенной дуги. При фишка не могла меняться с фишкой 100, поэтому она могла делать вход или выход только путём обмена с фишкой 1. При входе фишка 1 совершает сдвиг на 1 по часовой стрелке, а при выходе — на 1 против часовой стрелки. Проведём аналогичные рассуждения для фишек которые не могут меняться с фишкой 1.

Тем самым, мы получаем, что фишки 1 и 100 совершают одинаковый сдвиг по и против часовой стрелки, поэтому они остаются на своих позициях. Противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Второй способ. Будем считать сдвиги фишек относительно их начальной позиции, причём сдвиг по часовой стрелке будет считаться с плюсом, против часовой — с минусом. Тогда при обмене двух фишек к сдвигу одной из них прибавляется +1, а другой — Значит, в результате проведённых операций общая сумма сдвигов будет равна 0.

Рассуждаем от противного: пусть при каждая фишка в итоге сдвинута на одну позицию по часовой стрелке, т.е. её сдвиг оказался равным (здесь — целое «число оборотов» по часовой стрелке, в частности при фишка сделала оборотов против часовой стрелки). Тогда суммарный сдвиг всех 100 фишек равен

Поскольку он должен равняться 0, имеем

Поскольку фишки с номерами и где не могли меняться местами, поэтому их сдвиги в любой момент заведомо отличаются меньше чем на 100, значит количества оборотов и равны при Отсюда имеем …, Тогда сумма

— чётна, а значит не равна Противоречие.