Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

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

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

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

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

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

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

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

  • advent of code

    Народ (программисты, стремящиеся и близлежащие), а вы помните еще про Advent of Code, милое такое ежегодное состязание с не очень сложными…

  • два интересных курса

    Два онлайн-курса (для программистов), которые кажутся интересными и подмывает смотреть, хотя не факт, что все-таки соберусь. 1. MIT 18.S191,…

  • немного компьютерной ностальгии

    1. Webamp - браузерная версия Winamp, полностью рабочая, поддерживает все на свете включая скины оригинала, и даже есть в десктопной версии. На том…

  • 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

  • advent of code

    Народ (программисты, стремящиеся и близлежащие), а вы помните еще про Advent of Code, милое такое ежегодное состязание с не очень сложными…

  • два интересных курса

    Два онлайн-курса (для программистов), которые кажутся интересными и подмывает смотреть, хотя не факт, что все-таки соберусь. 1. MIT 18.S191,…

  • немного компьютерной ностальгии

    1. Webamp - браузерная версия Winamp, полностью рабочая, поддерживает все на свете включая скины оригинала, и даже есть в десктопной версии. На том…