avva | задачка

На двух полках стоят разрозненные тома многотомной энциклопедии в произвольном порядке. Хозяин каждое утро ищет два тома, стоящих на разных полках, номера которых отличаются на единицу, и меняет их местами. Через какое-то время все тома оказываются на тех же полках, что и в начале. Доказать, что все тома будут стоять в том же порядке, что и в начале.

Совсем простая, если увидеть правильный путь. Скрывать комменты не буду, так что не читайте, если сами хотите решить.

Threaded | Top-Level Comments Only

From:

aburachil.livejournal.com

Предположим, что нам удалось найти контрпример. Рассмотрим минимальный в следующем смысле пример: сначала выберем энциклопедию с наименьшим количеством томов, а затем игру с этой энциклопедией с наименьшим количеством шагов. Теперь покажем, что либо одно либо другое можно уменьшить, чем и получим искомое противоречие. Для начала заметим, что для фиксированного тома А перестановок (А,А+1) должно быть чётное число (этот не имеет отношения к минимальности и доказывается простой индукцией по А). Рассмотрим две соседние перестановки (1,2) [если бы их вовсе не было, то том 1 нам не был бы не нужен — противоречит минимальности количества томов]. Очевидно, что между ними было чётное число перестановок (2,3), иначе нельзя бы было второй раз поменять 1 с 2 — они были бы на одной полке. Если это чётное число равно нулю, то две исходные перестановки (1,2) можно без всяких последствий выбросить, так как они коммутируют со всеми кроме (2,3) — это было бы противоречие с предположением о минимальности количества ходов. Значит их по крайней мере две. Рассмотрим теперь две соседние из них и повторим рассуждение о чётности и ненулёвости (3,4) между ними. Теперь аккуратно применим в этом месте индукцию, и всё готово.
Ну что — правильно?

From:

aburachil.livejournal.com

У-у-у-пс! Неужто других нет? А Вы говорите --- простая ;-)

From:

tom-ohawk.livejournal.com

иначе говоря сортировка шелла но шаг не меняется?

From:

avva.livejournal.com

Ага, всё верно.

Не знаю, почему других ответов нет, задача действительно несложная. Правда, моё решение ещё заметно проще и тривиальнее Вашего, так что, может, поэтому мне так кажется :)

From:

aburachil.livejournal.com

Интересно --- изложите, коли не влом. Я-то сначала поверила, что всё просто (какая-нибудь детская чётность), но потом до меня допёрло, что если разрешить менять ещё и первый с последним (так сказать, соседи по кругу), то случается облом: (12|34)-(13|24)-(14|23)-(24|13)-(21|43) --- тут вертикальная палочка разграничивает две полки, это вроде пример для четырёхтомника.

From:

nadja-s.livejournal.com

Возьмем какую-нибудь полку и два места A и B на ней. Обозначим N(i) и M(i) номера томов на местах A и B после i шагов. Т.к. N и M на каждом шаге меняются максимум на единицу (причем только одно из них) и M(i) не равно N(i), то знак N(i)-M(i) одинаков для всех i. Значит, можно упорядочить места на полке по принципу "место для тома с самым маленьким номером на этой полке", "место для тома со 2-м самым маленьким номером", ..., "место для тома с самым большим номером", и это упорядочивание не будет зависеть от времени. Значит, если в какой-то момент на полке окажутся те же тома, что и в начале, они попадут на те же места, что и в начале.

From:

max-dnepr.livejournal.com

В конце они стоят в обратном порядке.

From:

avva.livejournal.com

Конечно. Две версии: наглядная и математическая ;)

Наглядная.

Первый шаг: пусть у нас есть какой-то контрпример. На каждой полке исказим не номера томов, а номера их порядковых мест, так, чтобы порядок томов совпадал с порядком их номеров. Например, пусть на каждой полке 20 томов, которые стоят в 20 "слотах". Условимся первым слотом считать не самый левый, а тот, где сейчас стоит том с наименьшим номером; второй слот будет тот, где том со следующим по порядку номером итп. Приклеим к этим слотам бумажки с их номерами, чтобы не забыть. Теперь проведём наш "контрпример" - последовательность обменов. Ясно, что в конце мы получим тома, которые отличаются от начального порядка как по порядку "слева-направо", так и "по бумажкам". Это доказывает, что можно изначально предположить, что на каждой полке тома стоят по возрастанию номеров:
наш контрпример и для этого случая будет контрпримером.

Второй шаг: представим себе нашу энциклопедию в виде нитки, на которой завязаны на одинаковом расстоянии узелки, каждый из которых обозначает том. Нитка ползёт по столу слева направо по двум параллельным прямым, обозначающим полки, и иногда переползает с одной прямой на другую. Например, если верхняя прямая обозначает левую полку, и на ней стоят тома 1,3,4, а на правой тома 2,5,6, то нитка будеет выглядеть так:

1     3---4
 \   /     \
  \ /       \
   2         5---6....

На каждой прямой последовательность чисел совпадает с порядком томов на полке. Теперь обратим внимание, что обменять два тома с соседними номерами всего лишь означает поднять снизу вверх один узелок нитки и опустить сверху вниз соседний. В общем, всё ;)

Математическая версия. Рассматриваем энциклопедию как последовательность чисел, в порядке первой полки, а за ней второй. Пусть T - контрпример, перестановка, являющаяся произведением перестановок типа (i,i+1), где i и i+1 стоят на разных полках.

Первый шаг. Пусть A - произвольная перестановка только первой полки. Ясно, что (A^-1)T(A) = T. Вывод: можно предположить, не теряя общности, что тома на каждой полке стоят в возрастающем порядке.
Второй шаг. Пусть тома изначально стоят на каждой полке в возрастающем порядке. Заметим, что любой обмен (i,i+-1) не меняет этого порядка на каждой полке, т.к. вместо тома i ставится том, который остаётся по порядку между теми томами, между которыми стоял i. Всё.

From:

avva.livejournal.com

Ага, верно. Это то же решение, что я выписал (намного более подробно) выше.

From:

aburachil.livejournal.com

Дык, правильно всё. Но самое крутое решение, несомненно, с дискретной непрерывностью от

nadja_s.

From: (Anonymous)

Эта задача (в немного другой формулировке) первоначально была предложена семиклассникам на Петербургской городской олимпиаде 1995 года. Ее автором является К.П.Кохась.