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

[avva]

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

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

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

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

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

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

Comments

[neatfires.livejournal.com]

Мое решение, вроде, в других ответах не встречается, поэтому вот, в копилку:
1. запишем любимые камеры узников в массив (любимая камера i-го узника записана i-м элементом)
2. сравним начальный и конечный массивы (A и B). пусть m, n - индекс первого отличия в массивах с начала и с конца, соответственно
3. пусть x - элемент на месте n в массиве B, k - его индекс в массиве A. ясно, что m<=k<=n

Докажем через индукцию по n-m, что есть пара элементов с индексами c и d, выполняющими m<=c<=d<=n, перестановка которых улучшает положение одного узника и не ухудшает положение другого. Для n-m=1 очевидно. Для других: обменяем местами a[k] и a[n]. Не может такого быть, что a[k] ухудшил свое положение или оба сохранили предыдущее положение (последнее бы означало, что a[n]=b[n]). Три остающихся варианта:
1. a[k] улучшил, a[n] не ухудшил
2. a[k] не ухудшил, a[n] улучшил
3. a[k] улучшил, a[n] ухудшил

Первы два варианта дают искомую пару, остается 3-й. По индукции, в A' (т.е. в массиве А после перестановки) есть интересующие нас c и d, выполняющие m<=c<=d<=n-1. Если c!=k и d!=k, то a[c] и a[d] - это искомая пара. Если c<k=d, тогда a[k] и a[n] - это искомая пара. Наконец, если c=k<d, то искомая пара - это a[k], a[d].