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

[avva]

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

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

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

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

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

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

Comments

[avva.livejournal.com]

Да, придирок больше нет, правильное решение :)

Мое похоже на него: я доказываю, что можно сократить любую цепочку длиной больше 2, "закоротив" ее в середине. Пусть в выигрышной цепочке некий выигрышный ход A->B будет слева направо. Тогда любой другой элемент в цепочке, находящийся справа от A, должен также быть справа от B (иначе A может прыгнуть сразу в него и укоротить цепочку). Рассмотрим другие звенья в цепочке до и после А: ...->Y->Z->A->B->C->... Видим, что после B все следующие переходы должны оставаться справа от B - иначе им нужно прыгнуть аж влево от A, но тогда такой переход можно заменить на переход к A и сократить. С другой стороны, Z->A должен прийти слева, потому что иначе Z расположен справа от B и может придти в B и сократить. Выходит, что соединить части цепочки слева и справа от A невозможно.

[ztatyan.livejournal.com]

Да, у нас вами получилось похоже, ключевой элемент - направление переезда. Спасибо!