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

[avva]

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

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

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

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

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

Comments

Knop

[v888.livejournal.com]

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

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

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

[nechaman]

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

[avva.livejournal.com]

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

[avva.livejournal.com]

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

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

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

[fyysik.livejournal.com]

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

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

[mikhaelo.livejournal.com]

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

[avva.livejournal.com]

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

[avva.livejournal.com]

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

[fyysik.livejournal.com]

то есть им самим строиться нельзя? :(

[avva.livejournal.com]

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

[avva.livejournal.com]

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

[(Anonymous)]

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

[shultz-flory.livejournal.com]

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

[fyysik.livejournal.com]

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

[avva.livejournal.com]

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

[avva.livejournal.com]

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

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

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

[avva.livejournal.com]

Да, вы совершенно правы.

[avva.livejournal.com]

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

[alex-wmd.livejournal.com]

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

[old-radist.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]

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