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

[avva]

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

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

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

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

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

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

Comments

[(Anonymous)]

Если записать неравенства, имеющие смысл неухудшения ситуации после пересадки для каждого отдельного заключенного, то получим следующую серию: |a(k(i)) - b(i)| <= |a(i) - b(i)|, при этом хотя бы для одного заключенного это неравенство строгое. Тогда суммируя все неравенства, получим как раз |a(k(1)) - b(1)| + ... + |a(k(100)) - b(100)| < |a(1) - b(1)| + ... + |a(100) - b(100)| = S.

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

[avva.livejournal.com]

Хорошо, тогда так: ваше условие |a(i) - b(j)| >= |a(j) - b(j)| означает лишь, что недовольство заключенного j не уменьшится, оно ничего не говорит о недовольстве заключенного i. Из вашего противоречия тогда следует, что для каких-то i,j это условие неверно, т.е. заключенному j действительно станет лучше. Но i при этом может стать хуже, и это тогда не будет пригодной парой для обмена.

Поскольку мы хотим доказать "i стало не хуже, j стало не хуже, и хотя бы в одном из двух случае неравенство строгое", точное условие, противное этому, будет "либо i стало хуже, либо j стало хуже, либо обоим одинаково". Это можно записать в виде трех формул в вашей нотации, но из-за "либо" суммировать их не очень получается.

[(Anonymous)]

Да, согласен. Спасибо.