?

Log in

задачка - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка [ноя. 22, 2005|01:11 pm]
Anatoly Vorobey
Милая задачка от ygam'а:

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

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

Comments:
[User Picture]From: aburachil
2005-11-22 12:17 pm
Предположим, что нам удалось найти контрпример. Рассмотрим минимальный в следующем смысле пример: сначала выберем энциклопедию с наименьшим количеством томов, а затем игру с этой энциклопедией с наименьшим количеством шагов. Теперь покажем, что либо одно либо другое можно уменьшить, чем и получим искомое противоречие. Для начала заметим, что для фиксированного тома А перестановок (А,А+1) должно быть чётное число (этот не имеет отношения к минимальности и доказывается простой индукцией по А). Рассмотрим две соседние перестановки (1,2) [если бы их вовсе не было, то том 1 нам не был бы не нужен — противоречит минимальности количества томов]. Очевидно, что между ними было чётное число перестановок (2,3), иначе нельзя бы было второй раз поменять 1 с 2 — они были бы на одной полке. Если это чётное число равно нулю, то две исходные перестановки (1,2) можно без всяких последствий выбросить, так как они коммутируют со всеми кроме (2,3) — это было бы противоречие с предположением о минимальности количества ходов. Значит их по крайней мере две. Рассмотрим теперь две соседние из них и повторим рассуждение о чётности и ненулёвости (3,4) между ними. Теперь аккуратно применим в этом месте индукцию, и всё готово.
Ну что — правильно?
(Ответить) (Thread)
[User Picture]From: aburachil
2005-11-22 12:18 pm
У-у-у-пс! Неужто других нет? А Вы говорите --- простая ;-)
(Ответить) (Parent) (Thread)
[User Picture]From: ygam
2005-11-22 07:42 pm
Я сейчас напишу свое решение, попроще, у себя в журнале.
(Ответить) (Parent) (Thread)
[User Picture]From: aburachil
2005-12-06 07:58 pm

Да вот --- проще некуда ;-)

(Ответить) (Parent) (Thread)
[User Picture]From: avva
2005-11-22 12:34 pm
Ага, всё верно.

Не знаю, почему других ответов нет, задача действительно несложная. Правда, моё решение ещё заметно проще и тривиальнее Вашего, так что, может, поэтому мне так кажется :)
(Ответить) (Parent) (Thread)
[User Picture]From: aburachil
2005-11-22 12:43 pm

ещё заметно проще и тривиальнее

Интересно --- изложите, коли не влом. Я-то сначала поверила, что всё просто (какая-нибудь детская чётность), но потом до меня допёрло, что если разрешить менять ещё и первый с последним (так сказать, соседи по кругу), то случается облом: (12|34)-(13|24)-(14|23)-(24|13)-(21|43) --- тут вертикальная палочка разграничивает две полки, это вроде пример для четырёхтомника.
(Ответить) (Parent) (Thread)
[User Picture]From: max_dnepr
2005-11-22 01:10 pm

Я чего-то не понимаю?

В конце они стоят в обратном порядке.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2005-11-22 01:17 pm

Re: ещё заметно проще и тривиальнее

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

Наглядная.

Первый шаг: пусть у нас есть какой-то контрпример. На каждой полке исказим не номера томов, а номера их порядковых мест, так, чтобы порядок томов совпадал с порядком их номеров. Например, пусть на каждой полке 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. Всё.
(Ответить) (Parent) (Thread)
[User Picture]From: aburachil
2005-11-22 01:51 pm

Re: ещё заметно проще и тривиальнее

Дык, правильно всё. Но самое крутое решение, несомненно, с дискретной непрерывностью от nadja_s.
(Ответить) (Parent) (Thread)
From: tom_ohawk
2005-11-22 12:29 pm
иначе говоря сортировка шелла но шаг не меняется?
(Ответить) (Thread)
[User Picture]From: nadja_s
2005-11-22 12:48 pm
Возьмем какую-нибудь полку и два места A и B на ней. Обозначим N(i) и M(i) номера томов на местах A и B после i шагов. Т.к. N и M на каждом шаге меняются максимум на единицу (причем только одно из них) и M(i) не равно N(i), то знак N(i)-M(i) одинаков для всех i. Значит, можно упорядочить места на полке по принципу "место для тома с самым маленьким номером на этой полке", "место для тома со 2-м самым маленьким номером", ..., "место для тома с самым большим номером", и это упорядочивание не будет зависеть от времени. Значит, если в какой-то момент на полке окажутся те же тома, что и в начале, они попадут на те же места, что и в начале.
(Ответить) (Thread)
[User Picture]From: avva
2005-11-22 01:43 pm
Ага, верно. Это то же решение, что я выписал (намного более подробно) выше.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2005-11-22 05:04 pm

Копирайты не соблюдаете

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



(Ответить) (Thread)
[User Picture]From: ygam
2005-11-22 07:44 pm

Re: Копирайты не соблюдаете

А я ее услышал от друга, математика из Петербурга, который ведет детский математический кружок. Все сходится!
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2005-11-22 08:09 pm

Re: Копирайты не соблюдаете

Спасибо.
(Ответить) (Parent) (Thread)