задачка (математическое)

[avva]

Вот рассказали забавную задачку - я думал, что знаю все задачки про сто арестантов, но оказалось, что не все. Задачка не очень сложная, но и не совсем тривиальная. Комментарии не скрываю.

Update: в комментариях есть несколько правильных решений; первым правильное решение запостил kaathewise.

--------------
100 узников сидят в 100 тюремных камерах, которые расположены в ряд. В одной камере всегда сидит ровно один узник.

У каждого узника есть любимая камера, в которой ему бы больше всего хотелось сидеть. При этом у разных узников любимые камеры могут совпадать. Если узнику не довелось сидеть в своей любимой камере, то он предпочитает остальные в соответствии с расстоянием до любимой. Например, если у узника любимая камера номер 25, то на втором месте - камеры 24 и 26, на третьем 23 и 27, и так далее.

На данный момент все узники рассажены по камерам каким-то образом. Известно, что существует такой способ их пересадить, чтобы увеличилось количество добра и никто не ушел обиженный. Иными словами, в результате пересадки ни один из узников не попадает на худшее с своей точки зрения место, и по крайней мере один узник попадает на лучшее.

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

Comments

[kaathewise.livejournal.com]

Видимо, так:
Не будем рассматривать всех узников, которые не поменяют своего места при переходе к "лучшей" рассадке.
Рассмотрим самого правого узника, который пересядят вправо при переходе к "лучшей" рассадке. Пусть он сидит на месте N. Тогда его идеальное место точно справа от N, иначе бы он расстроился.
Узник N+1 не может оставаться на месте и не может пересесть вправо (по предположению). Значит, он пересаживается влево, и его идеальное место слева от N+1, иначе бы он тоже расстроился.
Поэтому можно поменять N-го и (N+1)-го.

(Нумерация пропускает узников, сидящих на месте).

Единственный момент, когда это не работает - когда N и N+1 меняются друг с другом при переходе к правильной рассадке, и им это безразлично. Тогда их тоже можно выкинуть:)

[avva.livejournal.com]

Ага, вот с этой последней поправкой, кажется, все проходит.

Замечательно, спасибо! Очень просто и наглядно. Мое собственное решение в том же духе, но несколько сложнее.

Я все же заскриню на несколько часов ваше решение, если вы не против, пока оно единственное верное ;)