задачка (математическое)
Mar. 8th, 2012 06:29 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaВот рассказали забавную задачку - я думал, что знаю все задачки про сто арестантов, но оказалось, что не все. Задачка не очень сложная, но и не совсем тривиальная. Комментарии не скрываю.
Update: в комментариях есть несколько правильных решений; первым правильное решение запостил![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
kaathewise.
--------------
100 узников сидят в 100 тюремных камерах, которые расположены в ряд. В одной камере всегда сидит ровно один узник.
У каждого узника есть любимая камера, в которой ему бы больше всего хотелось сидеть. При этом у разных узников любимые камеры могут совпадать. Если узнику не довелось сидеть в своей любимой камере, то он предпочитает остальные в соответствии с расстоянием до любимой. Например, если у узника любимая камера номер 25, то на втором месте - камеры 24 и 26, на третьем 23 и 27, и так далее.
На данный момент все узники рассажены по камерам каким-то образом. Известно, что существует такой способ их пересадить, чтобы увеличилось количество добра и никто не ушел обиженный. Иными словами, в результате пересадки ни один из узников не попадает на худшее с своей точки зрения место, и по крайней мере один узник попадает на лучшее.
Нужно доказать, что в такой ситуации обязательно найдутся два узника, которые согласятся поменяться местами. То есть, опять-таки, ни одному из этих двоих не станет хуже, и как минимум одному станет лучше.
Update: в комментариях есть несколько правильных решений; первым правильное решение запостил
kaathewise.--------------
100 узников сидят в 100 тюремных камерах, которые расположены в ряд. В одной камере всегда сидит ровно один узник.
У каждого узника есть любимая камера, в которой ему бы больше всего хотелось сидеть. При этом у разных узников любимые камеры могут совпадать. Если узнику не довелось сидеть в своей любимой камере, то он предпочитает остальные в соответствии с расстоянием до любимой. Например, если у узника любимая камера номер 25, то на втором месте - камеры 24 и 26, на третьем 23 и 27, и так далее.
На данный момент все узники рассажены по камерам каким-то образом. Известно, что существует такой способ их пересадить, чтобы увеличилось количество добра и никто не ушел обиженный. Иными словами, в результате пересадки ни один из узников не попадает на худшее с своей точки зрения место, и по крайней мере один узник попадает на лучшее.
Нужно доказать, что в такой ситуации обязательно найдутся два узника, которые согласятся поменяться местами. То есть, опять-таки, ни одному из этих двоих не станет хуже, и как минимум одному станет лучше.
