«Квант» — научно-популярный физико-математический журнал (издаётся с 1970 года)
Старый сайт журнала: kvant.ras.ru

Задача М1074

Условие задачи (1987, № 11) Задача М1074 // Квант. — 1987. — № 11. — Стр. 22; 1988. — № 3. — Стр. 25—26.

Дана стопка из $2n+1$‍‍ карточек, с которой разрешается производить следующие две операции:

  1. сверху снимается часть карточек и перекладывается вниз с сохранением порядка;
  2. верхние $n$‍‍ карточек с сохранением порядка выкладываются в $n$‍‍ промежутков между нижними $n+1$‍‍ карточками.

Докажите, что с помощью указанных операций из исходного расположения карточек в стопке нельзя получить более $2n(2n+1)$‍‍ различных расположений карточек.

Д. В. Фомин

Ленинградская городская математическая олимпиада (1987 год)


Решение задачи (1988, № 3) Задача М1074 // Квант. — 1987. — № 11. — Стр. 22; 1988. — № 3. — Стр. 25—26.

Занумеруем карточки сверху вниз числами 0, 1, $\ldots$‍,$2n$‍‍ и выложим их последовательно в вершинах правильного многоугольника $A_0A_1\ldots A_{2n}$‍‍ (рис. 1). Тогда операции (А) отвечает поворот всего набора карточек вокруг центра многоугольника на угол, кратный $\dfrac{360^\circ}{2n+1}$‍,‍ а при операции (Б) карточки из вершин $A_0$‍,$A_1$‍,$\ldots$‍,$A_{n-1}$‍‍ перекладываются, соответственно, в вершины $A_1$‍,$A_3$‍,$\ldots$‍,$A_{2n-1}$‍,‍ а из вершин $A_n$‍,$A_{n+1}$‍,$\ldots$‍,$A_{2n}$‍‍ — в вершины $A_2$‍,$A_4$‍,$\ldots$‍,$A_{2n}$‍‍ (рис. 2). Таким образом, после операции (Б) карточки, которые первоначально были соседними, будут стоять через одну. Если же между двумя карточками было заключено $k$‍‍ сторон многоугольника (всегда можно считать $k\le n$‍),‍ то в результате операции (Б) между ними окажется $2k$‍‍ сторон. В частности, расстояния между карточками 0 и 1, 1 и 2, $\ldots$‍,$2n$‍‍ и 0 будут оставаться равными между собой при выполнении операций (А) и (Б) в любом числе и порядке. Поэтому расстановка всех карточек полностью задаётся положением карточек 0 и 1: если 0 находится в вершине $A_i$‍,‍ а 1 — в вершине $A_j$‍,‍ то 2 — в такой вершине $A_k$‍,‍ что $A_iA_k=A_iA_j$‍,‍ 3 — в такой вершине $A_l$‍,‍ что $A_kA_l=A_iA_j$‍,‍ и т. д. (рис. 3). Место для карточки 0 можно выбрать $2n+1$‍‍ способами, для карточки 1 остаётся $2n$‍‍ мест. Следовательно, число возможных расположений не превосходит $2n(2n+1)$‍.

Рис. 1
Рис. 1
Рис. 2
Рис. 2
Рис. 3
Рис. 3

Чтобы получить точное число расположений, надо здесь множитель $2n$‍‍ заменить на число различных остатков от деления степеней двойки на $2n+1$‍.‍ (При каждом применении операции (Б) число сторон многоугольника между карточками 0 и 1, отсчитываемое в заданном направлении, нужно удвоить и взять остаток от деления на $2n+1$‍.)

Д. В. Фомин, В. Н. Дубровский


Метаданные Задача М1074 // Квант. — 1987. — № 11. — Стр. 22; 1988. — № 3. — Стр. 25—26.

Предмет
Математика
Условие
Решение
,
Номера

1987. — № 11. — Стр.  [условие]

1988. — № 3. — Стр.  [решение]

Описание
Задача М1074 // Квант. — 1987. — № 11. — Стр. 22; 1988. — № 3. — Стр. 25‍—‍26.
Ссылка
https://www.kvant.digital/problems/m1074/