Пленники царя Дадона

18

ложения. Однако из двух слоев этого каскада содержит больше половины связи, то есть больше, чем $2^{r-1}$ связи. Эти связи не пересекаются и, следовательно, оставшиеся $r-1$ каскадов должны реализовать разложение пучка этих связи, что невозможно, так как степень этого пучка больше $2^{r-1}$. Полученное противоречие завершает доказательство.

Так как для каскадного разложения произвольной перестановки (не являющейся, как $K_p$, пучком) требуется каскадов не меньше, чем для разложения ее максимального пучка, то справедлива.

Теорема 2. Минимальное число каскадов, необходимое для двустойной реализации перестановки стелени $n$ и молцны $p$, не меньше, чем $\log_2 p$.

Мы получили оценку «снизу» для минимального числа каскадов. Используя очень похожие расчёжения, можно получить оценку «сверху»:

Теорема 3. Произвольная перестановка стелени $n$ допускает $\log_2 n [-\text{kаскадную реализацию}]$.

Задча 4. Докажите теорему 3.

Полученные «верхняя» и «низняя» оценки мало отличются для «толстых» перестановок. Однако для перестановок малой толщины различие веса сушистенено, и возникнет необходимость в более точных оценках. Следующие две задачи дают неокоторое продвижение в этом вопросе, однако точная формула для минимального числа двустойных каскадов, необходимых для разложения данной перестановки, пока неизвестна.

Задча 5. Докажите, что перестановка толщины $p$ допускает $(2 \cdot \log_2 p [-1])$-каскадную реализацию.

Задча 6. Докажите, что перестановка толщины $p$ допускает $(2 \cdot \log_2 \frac{p}{3} [+2])$-каскадную realizацию.

Пленники царя Дадона

Во время набета царь Дадон захватил 100 пленников. Их посадили в одиночные камеры, а по тюремному коридору ходила до зубов вооруженная стража. Каждая камера запиралась на замок; ко всем ста замкам подходил ключ, хранившийся у царя Дадона на порсе. Один поворот ключа отпирал замок, еще один поворот вновь запирал, следующего поворот опять отпирал и т. д.

Ко дня своего рождения царь решил освободить заklюченных, и еще накануне послал человека, который вставил ключ в замок каскадой камеры и поворачивал на один оборот. Все двери оказались отпертыми. Однако день рождения еще не наступил, и выйти из камер было неозможно: вдоль коридора ходила вооруженная стража.

Едва посыльный успел возвратить ключ, как царь Дадон изменил свое решение. Он поручил новому посланцу повернуть ключ в замке каскадой второй камеры. Двери второй, четвертой, шестой и всех остальных четырех камеры оказались вновь запертыми. Следующий сделал по одному обороту в замках третий, шестой, девятой, двенадцатой и т. д. камер. Еще один — в каждой четвертой камере. То же самое повторили следующим посланием царя — до сотого включительного, который повернул ключ лишь в замке сотой камеры.

Наконец день рождения царя настояил. Стража была снять и сдевшие в открытых камерах вышли на свободу.

Сколько пленников отпустил на свободу царь Дадон?