За круглым столом

[wpoms.]

В конференц-зале есть круглый стол с `n` стульями. На конференцию приехали `n` делегатов. Первый делегат выбирает свой стул произвольным образом. Далее, `(k + 1)`-ый делегат садится на `k` мест правее `k`-ого делегата (`1 <= k <= n - 1`). (В частности, второй делегат садится рядом с первым.) Ни один стул не может быть занят более чем одним делегатом. Найдите множество значений `n`, для которых это возможно.

@темы: Комбинаторика, Теория чисел

Comments

[Adjirranirr]

Пусть делегат с номером `m` сел на стул с номером `a_m`; перенумеруем все стулья против часовой стрелки так, чтобы стул, на который сел первый, имел номер `0`. Тогда `a_(m + 1) = a_m + (m + 1) \text{mod} n`, и `a_(m) = \frac{(m + 1) * m} {2} \text{mod} n`.

Для начала, решим другую задачу — пусть количество делегатов неограничено, и на каждый стул могут садиться произвольное их количество. Тогда, при `n`, при которых они не смогут усесться на каждый стул, они не смогут усесться на `n` стульев в исходной формулировке задачи.
Чтобы все стулья оказались заняты, в списке номеров `{a_m}_{m = 1}^{oo}` должен встретиться каждый номер от `0` до `n - 1` включительно. Предположим `n = 2^k * l`, где `l` — нечетное число, не меньшее `3`. Чтобы встретились все возможные различные номера, должны встретиться и все возможные различные номера по модулю `l`. Но `a_l \equiv a_{l - 1} \equiv 0 \text{mod} l`, и все дальнейшие делегаты, в силу цикличности процесса, будут садиться только на занятые по модулю `l` стулья. А так как среди `l` номеров `a_0,\ a_1,\ ...,\ a_{l - 1}` есть одинаковые по модулю `l`, то по принципу Дирихле хотя бы один стул останется свободным.

Таким образом, `n = 2^k`. Очевидно, что при `k = 0` рассадка возможна; предположим, что она возможна и при некотором `k`. Тогда все номера `a_0,\ a_1,\ ...,\ a_{2^k - 1}` различны по модулю `2^k`, и, следовательно, и по модулю `2^{k + 1}`. Так как `a_{2^k} = a_{2^k - 1} + 2^k`, то `a_{2^k} \equiv a_{2^k - 1} \text{mod} 2^k`, но `a_{2^k} != a_{2^k - 1} \text {mod} 2^{k + 1}`.
Предположим `a_{2^k + m - 1} \equiv a_{2^k - m} \text{mod} 2^{k}`, но `a_{2^k + m - 1} != a_{2^k - m} \text{mod} 2^{k + 1}`; тогда `a_{2^k + m - 1} \equiv a_{2^k - m} + 2^k \text{mod} 2^{k + 1}`. Значит, `a_{2^k + m} = a_{2^k + m - 1} + 2^k + m \equiv_{\text{mod}} a_{2^k - m} + 2^k + 2^k + m \equiv_{\text{mod}}` `\equiv_{\text{mod}}a_{2^k - (m + 1)} + 2^k - m + 2^k + 2^k + m \equiv_{\text{mod}} a_{2^k - (m + 1)} + 2^k \text {mod} 2^{k + 1}.
Таким образом, номера `a_{2^k},\ a_{2^k + 1},\ ...,\ a_n` совпадают с номерами `a_{2^k - 1},\ ...,\ a_1,\ a_0` соответственно по модулю `2^k` и отличаются на `2^k` по модулю `2^{k + 1}`; значит, все номера `{a_s}_{s = 0}^{2^{k + 1}}` различны и все делегаты усядутся на места.