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

[avva]

Отличная задачка от Константина Кнопа knop. Кстати, всем, кто интересуется математическими задачками, всячески рекомендую его журнал.

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

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

[скрываю комменты на сутки, кроме уточняющих вопросов, которые буду раскрывать. Через сутки все раскрою]

[Update: раскрыл все комментарии. Очень много правильных ответов. Я в очередной раз впечатлен тем, сколько умных людей читают этот журнал :)]

Comments

Knop

[v888.livejournal.com]

как же его, бедного, произносят по-английски?!

[http://users.livejournal.com/_1313/]

числа на лбах все уникальные или повторы тоже могут быть?

[avva.livejournal.com]

Для простоты можно считать, что числа не повторяются.

[nechaman]

Они могут предварительно о чем-то договориться?

[avva.livejournal.com]

Да, но только до того, как им напишут числа.

[fyysik.livejournal.com]

а передвижение с расталкиванием друг друга считается общением?

можно даже без физического расталкивания.

[avva.livejournal.com]

Да, считается.

[mikhaelo.livejournal.com]

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

[avva.livejournal.com]

Да, их выстроят лицом в одну сторону. Остроумный трюк с "построиться, потом части развернутся" запрещен.

[(Anonymous)]

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

[fyysik.livejournal.com]

числа действительные, поэтому придется полагаться на округление, причем видимо не суммы, а каждого отдельного числа, а потом суммировать.

[shultz-flory.livejournal.com]

Каждая варежка - не получится для крайних в шеренге.

[avva.livejournal.com]

Имеется в виду, что всякий раз, когда две варежки встречаются, они одного цвета.

[avva.livejournal.com]

Кстати, я хочу отдельно сказать, что по-хорошему завидую всем, кто сам додумался до трюка "после построения часть из них развернется так, чтобы все совпало". Это не правильное решение, и условия задачи это запрещают - но отличный пример ломки стереотипа, thinking outside the box. Я сам эту задачку решил, но в процессе решения эта идея мне и в голову не пришла.

[http://users.livejournal.com/d_m_/]

Это потому, что Вы решали математическую задачку, а не т.н. головоломку :)

[alex-wmd.livejournal.com]

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

[old-radist.livejournal.com]

Мудрецам написали номера, выдали варежки, построили в шеренгу. Теперь что ж, теперь и тачки выдадут. И паек.
Можно было бы хоть в пятницу не о политике?..

:(((

>> Да, их выстроят лицом в одну сторону.

пыщ-пыщ.

Кто бы сомневался...

[avva.livejournal.com]

В одну сторону лицом к стене, ага.

"-- Это уж точно -- ответил я. -- Но мальчика-то за что?
Подонки!"

[http://users.livejournal.com/d_m_/]

Решение.

0. Для простоты - все числа на лбах разные.
1. Перед началом игры всех мудрецов нумеруют от 1 до N, этот номер им сообщается, кроме того, каждому выдаётся шапочка с его номером.
2. Договариваются, что игроки с нечётными номерами надевают одну комбинацию варежек (скажем ЧБ), а с чётными - другую (БЧ).
3. Во время игры каждый мудрец считает коллизии. Коллизия - это пара мудрецов, порядок чисел на лбах у которых противоположен порядку номеров на шапочках. Скажем, пара (3.1415; 1) и (2.7183; 2) - это коллизия.
4. Если число коллизий, который наблюдает данный мудрец, чётно (в т.ч. 0), то этот мудрец надевает варежки так, как условились (см.п.2), если нечётно - наоборот.

Доказательство воистину замечательно, но не влезает на поля :)

[tishika.livejournal.com]

Числа идут не подряд, естественно?

[avva.livejournal.com]

Не подряд, и вообще необязательно целые.

[knop.livejournal.com]

Меня сегодня около десятка новых людей зафрендили.
Такая вот неожиданная глория мунди ;-)

[buddha239.livejournal.com]

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

Схема работает, если числа упорядочены так же, как мудрецы, и не портится, если поменять два числа местами.

[spamrobot3.livejournal.com]

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

[knop.livejournal.com]

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

[avva.livejournal.com]

каждая шляпа двуцветная, и нужно сориентировать? или как?

[mikev.livejournal.com]

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

[(Anonymous)]

Мудрецы могут видеть процесс одевания варежек и из этого делать выводы?

[avva.livejournal.com]

Нет, они должны все одновременно решить и надеть.

[graf-vk.livejournal.com]

Договориться заранее о фиксированном порядке.

Потом каждый сравнивает то, как упорядочены все кроме него с тем, как было договорено. Если это четная перестановка -- действует как договорились, если нечетная -- наоборот.

[(Anonymous)]

Для начала будем считать что каждый мудрец выбирает 0 или 1 и их задача состоит в том, чтобы 0 и 1 чередовались в окончательном ряду.

Занумеруем наших мудрецов от 1 до N. Теперь каждый мудрец, видя всех остальных, сортирует их и получает некую перестановку(из N-1 числа, каждое из которых от 1 до N), после чего выбирает (перестановка четная) XOR (его изначальный номер четный).

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

[(Anonymous)]

Вычисляется средний/средние два, договариваются о порядке варежек они, т.е мудрецы первого порядка. А дальше система самоорганизуется.

[unbe.livejournal.com]

Мудрецы заранее назначают каждому порядковый номер.
Каждый с нечетным номером наденет белую рукавичку слева, а с четным - справа. Потом, когда дали числа на лбах, каждый мудрец смотрит: если выстроить всех, кроме меня, по порядковым номерам, сколько будет инверсий в ряду чисел на лбах. Если число инверсий нечетное, то меняет рукавицы местам.

[ro-che.info (from livejournal.com)]

Пусть до начала шоу мудрецы занумеровались числами от 1 до n, после чего на них написали числа a_1, ..., a_n.

Пусть каждый мудрец посчитает количество инверсий, которые он видит -- то есть количество пар (i,j) таких, что i<j и a_i>a_j (i,j не равны номеру мудреца). Обозначим количество инверсий, которые наблюдает мудрец k, через b_k.

Возьмем двух мудрецов с соседними номерами i и i+1. Числа инверсий b_i и b_{i+1} будут одинаковой четности тогда и только тогда, когда в шеренге между мудрецами i и i+1 будет четное число других мудрецов.

Пусть c_i = b_i + i. Тогда числа c_i и c_{i+1} будут разной четности тогда и только тогда, когда в шеренге между мудрецами i и i+1 будет четное число других мудрецов.

Это утверждение по индукции обобщается: числа c_i и c_j будут разной четности тогда и только тогда, когда в шеренге между мудрецами i и j будет четное число других мудрецов.

Таким образом, в шеренге у соседних мудрецов i и j будут разной четности c_i и c_j (поскольку между ними 0 других мудрецов). Каждый мудрец может вычислить свое "c" и мудрецы с четным "c" наденут черную варежку на левую руку, а с нечетным на правую.

[jedal]

Можно сказать, что мудрецы не надевают варежки, а говорят остатки mod 2 (и их цель в том, чтобы эти остатки чередовались).

Присвоим каждому мудрецу номер. Пусть мудрец номер n, если он видит k беспорядков (беспорядок -- пара мудрецов, номера которых идут не в том порядке, что числа у них на лбу) скажет "n + k mod 2".

(Пример: 4 мудрецов расставили в порядке 3,1,4,2; соответствующие k: 1,2,2,1; n+k: 4,3,6,3 -- четность действительно чередуется.)

Докажем, что это решает задачу. Так как группа перестановок порождена транспозициями соседних элементов, достаточно 1) рассмотреть случай, когда мудрецам написали числа в порядке возрастания их номеров (очевидно) 2) проверить, что если два мудреца с соседними номерами меняются числами, то условие задачи не нарушается (тоже ясно -- если до обмена k_1=k_2 mod 2, то и после обмена тоже).

[bukky-boogwin.livejournal.com]

задача - найти алгоритм, который С ГАРАНТИЕЙ позволяет всем надеть варежки правильно, или алгоритм, который только делает вероятность этого максимальной?

[avva.livejournal.com]

с гарантией.

[-zerkalo-.livejournal.com]

Меняться меж собой варежками до построения они, конечно же, не могут. Так?

[avva.livejournal.com]

Да, не могут.