Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

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

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

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

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

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

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

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

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 35 comments