Ни о какой безапелляционности в моих высказываниях не может быть и речи!

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

From:

Видимо, так:
Не будем рассматривать всех узников, которые не поменяют своего места при переходе к "лучшей" рассадке.
Рассмотрим самого правого узника, который пересядят вправо при переходе к "лучшей" рассадке. Пусть он сидит на месте N. Тогда его идеальное место точно справа от N, иначе бы он расстроился.
Узник N+1 не может оставаться на месте и не может пересесть вправо (по предположению). Значит, он пересаживается влево, и его идеальное место слева от N+1, иначе бы он тоже расстроился.
Поэтому можно поменять N-го и (N+1)-го.

(Нумерация пропускает узников, сидящих на месте).

Единственный момент, когда это не работает - когда N и N+1 меняются друг с другом при переходе к правильной рассадке, и им это безразлично. Тогда их тоже можно выкинуть:)

Edited Date: 2012-03-08 05:02 pm (UTC)

From:

Ага, вот с этой последней поправкой, кажется, все проходит.

Замечательно, спасибо! Очень просто и наглядно. Мое собственное решение в том же духе, но несколько сложнее.

Я все же заскриню на несколько часов ваше решение, если вы не против, пока оно единственное верное ;)

From:

lagu.livejournal.com

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

From:

Однако может быть (?) так, что попарные перестановки вначале неизбежно уменьшают значение функции, но потом по мере приближения к лучшему варианту увеличивают его еще больше начального.

From:

nasty-naz.livejournal.com

после таких постов мне кажется, нет, уверен, что полтора курта матанализа, курс матстата и даже семестры линейной алгебры прошли мимо меня.
спасибо)

From:

amarao-san.livejournal.com

Вам не кажется, что эта задача слишком оторвана от жизни? Уж лучше в терминах "А, Б, 100 значений" формулировать. Потому что в пересказе на реальный мир задача звучит как идиотизм.

From:

ztatyan.livejournal.com

Вот есть есть цепочка переезжающих заключенных: а_1 переезжает к а_2, а_2 - к а_3, ..., а_(n-1) - к а_n, а тот - к а_1. Тогда обязательно есть заключенный, скажем а_k, на котором меняется напрвление переездов, то есть если а_(k-1) передвинулся направо, то а_k уехал налево. В самом деле, иначе бы все ехали в одну сторону, и цепочка бы не замкнулась. Сравним длину переезда для а_(k-1) и а_k. Если эти длины равны, то перед нами искомая пара. Пусть теперь они не равны, например, |a_k-a_(k+1)|>|a_(k-1)-a_k|. Тогда a_(k-1) и a_k - искомая пара. В самом деле, то что a_(k-1) выигрывает - ясно. Что касается a_k, то он переезжает в сторону своей любимой камеры на расстояние меньше, чем в цепочке, то есть тоже выигрывает.

From:

А что если эти длины равны, но оба при этом равнодушны к переезду? Тогда это не искомая пара.

From:

ztatyan.livejournal.com

Все множество заключенных разбито на такие непересекающиеся цепочки, и как минимум в одной цепочке есть выигрыш. Забыл сказать, что надо с этой цепочкой иметь дело. Если длины равны, то это цепочка из двух заключнных.

From:

Да, придирок больше нет, правильное решение :)

Мое похоже на него: я доказываю, что можно сократить любую цепочку длиной больше 2, "закоротив" ее в середине. Пусть в выигрышной цепочке некий выигрышный ход A->B будет слева направо. Тогда любой другой элемент в цепочке, находящийся справа от A, должен также быть справа от B (иначе A может прыгнуть сразу в него и укоротить цепочку). Рассмотрим другие звенья в цепочке до и после А: ...->Y->Z->A->B->C->... Видим, что после B все следующие переходы должны оставаться справа от B - иначе им нужно прыгнуть аж влево от A, но тогда такой переход можно заменить на переход к A и сократить. С другой стороны, Z->A должен прийти слева, потому что иначе Z расположен справа от B и может придти в B и сократить. Выходит, что соединить части цепочки слева и справа от A невозможно.

From:

ztatyan.livejournal.com

Да, у нас вами получилось похоже, ключевой элемент - направление переезда. Спасибо!

From:

Вообще-то мне кажется, что найдутся два из соседних камер (это куда сильнее утверждение). Доказательство --- напишем в строчке числа 1..Н и во второй строчке под ней ещё такую. Для каждого сидельца камеры А соединим верхнее число А с нижним числом Х(А), где Х -- функция хотения. Лемма 1: рассадка оптимальна тогда и только тогда, когда на рисунке нет пересечений (пересечения на концах линий для Х(А)=Х(Б) при различных А, Б не считаем за пересечение). Доказательство леммы --- упражнение (если окажется, что лемма липовая, то пардон ;) Лемма 2: на рисунке нет пересечений тогда и только тогда, когда для любого В<Н линии выходящие из верхних чисел В и В+1 не пересекаются. Доказательство очевидно. Ну и соответственно теорема следует очевидным образом из обеих лемм.

Edited Date: 2012-03-08 06:16 pm (UTC)

From:

К сожалению, Лемма 1 неверна, Лемма 2, пожалуй, верна, а теорема тоже неверна.
Лемма 1 неверна, например, в такой ситуации: Х(1,2,3) = (1,2,1) - рассадка оптимальна, однако пересечения есть.
Теорема неверна, например, в такой ситуации: Х(1,2,3) = (3,2,1) - можно поменять местами 1-го и 3-го, а соседних поменять нельзя.

From:

Да уж, лемма увязла => всей теореме кирдык. Если добавить условие "никто не сидит в любимой камере", то спасётся?

From:

Мне вообще кажется, что рассадка не оптимальна, если "никто не сидит в любимой камере":) но я могу ошибаться.

Edited Date: 2012-03-08 08:12 pm (UTC)

From:

А если так переформулировать --- "если расскадка не оптимальна, то к оптимальной можно придти последовательностью пересадок соседей, ни на каком ходу оценку не ухудшая"?

From:

Что значит "не ухудшая"? Значит, никто не будет жаловаться? Тогда нельзя. Даже если в начале никто не был на своем месте, где-то в середине он может на него попасть, и получится как в примере Х(1,2,3) = (3,2,1).

From:

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

From: (Anonymous)

Давненько я не брал в руки шашек, поэтому прошу простить за возможные глупости. :)

Пусть i --- номер заключенного, a(i) --- номер его текущей камеры, b(i) --- номер любимой камеры. Недовольство заключенного выражается через |a(i) - b(i)|. Общее недовольство всех заключенных равно S = |a(1) - b(1)| + ... + |a(100) - b(100)|. По условию существует такая перестановка (k(1), ..., k(100)), что каждое k(j) принимает уникальное значение от 1 до 100 и |a(k(1)) - b(1)| + ... + |a(k(100)) - b(100)| < S.

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

From: (Anonymous)

Вы не ответили - это значит, всё хорошо или всё плохо? :) Я подозреваю, что всё плохо, однако не могли бы вы указать, где ошибка? Спасибо.

From:

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

From: (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.

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

From:

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

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

From: (Anonymous)

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

From:

n0-spam.livejournal.com

Хорошая послевыборная задачка!

From:

From:

falcao.livejournal.com

Я рассуждал следующим образом.

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

Всех остальных перенумеруем слева направо. Они как-то обмениваются местами. На место первого кто-то приходит, и он сдвигается влево. Обозначим через k минимальный номер того, кто сдвигается влево.

Ясно, что k больше 1, так как номер 1 движется вправо. Поэтому существует номер k-1, и он сдвигается вправо в силу минимальности выбора k. Далее показываем, что k-1 и k могут обменяться местами с соблюдением условий задачи.

Прежде всего, покажем, что при таком обмене ни у одного из них положение не ухудшится. Достаточно это обосновать для перемещения номера k-1 ввиду симметрии. Ясно, что k-1 перемещался либо на место k, либо правее. Его положение при этом не ухудшилось. Следовательно, не ухудшится и его положение при шаге в том же направлении на ту же самую или на меньшую величину.

Выделенное соображение является "ключевым" для решения, поэтому скажем несколько слов в качестве обоснования. Любимая камера для k не может находиться левее него -- в противном случае он при шаге вправо увеличил бы до неё расстояние. Она не может также совпадать с k, что очевидно. Тем самым, она правее k, и если при коротком шаге вправо положение ухудшается, то это означает, что он сдвигается правее любимой камеры на достаточно большое расстояние. А тогда при более длинном перемещении вправо он отдаляется от любимой камеры ещё больше.

Итак, мы показали, что после обмена местами k-1 и k никому не станет хуже. Если лучше тоже никому не стало, то они оба находятся на равном расстоянии от любимой камеры, одинаковой для каждого из них. Из этого следует, что если в изначальном перемещении k-1 сдвинется правее k, или k сдвинется левее k-1, то произойдёт ухудшение. Этого быть не может по условию, но тогда получается, что k-1 и k поменялись местами в исходном перемещении. А такие случаи мы договорились не рассматривать в самом начале изложения.

Объяснение, возможно, длинноватое, но я старался так писать, чтобы ничего не было упущено.

From:

Да, действительно исчерпывающее объяснение, спасибо :)

From:

muthafutha.livejournal.com

Предположим, что все узники любят последнюю, 100-ую, камеру. Тогда одно перемещение количество добра не увеличит.

From: