Задача 5.8. 100 фишек выставлены в ряд. Разрешено менять местами две фишки, стоящие через одну фишку. Можно ли с помощью таких операций переставить все фишки в обратном порядке?

Решение:

Рассмотрим задачу с точки зрения инварианта. Поставим фишкам номера от 1 до 100. В начальном состоянии фишка с номером \(i\) находится на \(i\)-й позиции.

Разрешенная операция — обмен двух фишек, стоящих через одну. Это означает, что мы можем поменять местами фишку на позиции \(k\) с фишкой на позиции \(k+2\).

Рассмотрим четность позиции. Каждая операция меняет местами фишки, находящиеся на позициях разной четности. Например, если мы меняем фишки на позициях \(k\) и \(k+2\), то:

• Если \(k\) — четное, то \(k+2\) — тоже четное.
• Если \(k\) — нечетное, то \(k+2\) — тоже нечетное.

Это означает, что фишка, изначально находящаяся на четной позиции, всегда останется на четной позиции. Аналогично, фишка с нечетной позиции всегда будет на нечетной позиции.

В обратном порядке фишки должны быть расставлены так: фишка 100 на 1-й позиции, 99 на 2-й, ..., 1 на 100-й.

Рассмотрим фишку с номером 100. Изначально она стоит на 100-й (четной) позиции. В конечном состоянии она должна стоять на 1-й (нечетной) позиции. Но, как мы показали, фишка, находящаяся на четной позиции, никогда не может перейти на нечетную позицию с помощью данных операций.

Следовательно, переставить все фишки в обратном порядке невозможно.

Ответ: Нет, нельзя.