?

Log in

No account? Create an account
задачка (математическое) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка (математическое) [июл. 2, 2010|01:58 pm]
Anatoly Vorobey
Отличная задачка от Константина Кнопа knop. Кстати, всем, кто интересуется математическими задачками, всячески рекомендую его журнал.

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

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

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

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

Comments:
Страница 1 из 4
<<[1] [2] [3] [4] >>
[User Picture]From: v888
2010-07-02 11:00 am

Knop

как же его, бедного, произносят по-английски?!
(Ответить) (Thread)
[User Picture]From: _1313
2010-07-02 11:07 am
числа на лбах все уникальные или повторы тоже могут быть?
(Ответить) (Thread)
[User Picture]From: avva
2010-07-02 11:21 am
Для простоты можно считать, что числа не повторяются.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: nechaman
2010-07-02 11:09 am
Они могут предварительно о чем-то договориться?
(Ответить) (Thread)
[User Picture]From: avva
2010-07-02 11:21 am
Да, но только до того, как им напишут числа.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: fyysik
2010-07-02 11:34 am
а передвижение с расталкиванием друг друга считается общением?

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

Edited at 2010-07-02 11:39 (UTC)
(Ответить) (Thread)
[User Picture]From: avva
2010-07-02 11:42 am
Да, считается.
(Ответить) (Parent) (Thread) (Развернуть)
From: mikhaelo
2010-07-02 11:40 am
А и выстроят в шеренгу лицом в одну сторону? Т.е. каждый мудрец своей левой рукой будет держать правую руку соседа и наоборот? Напрашивается стратегия положить на числа и договориться одеть всем на левую руку черную варешку и на правую белую, или я не понял условия.
(Ответить) (Thread)
[User Picture]From: avva
2010-07-02 11:42 am
Да, их выстроят лицом в одну сторону. Остроумный трюк с "построиться, потом части развернутся" запрещен.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2010-07-02 11:46 am
Есть два способа одеть варежки, и способ одевания каждый определяет исходя из четности суммы чисел на лбах остальных. Например договариваются, что если сумма четная - то на левую руку белую, на правую - черную; если сумма нечетная - то наоборот.
(Ответить) (Thread)
[User Picture]From: fyysik
2010-07-02 11:49 am
числа действительные, поэтому придется полагаться на округление, причем видимо не суммы, а каждого отдельного числа, а потом суммировать.
(Ответить) (Parent) (Thread)
[User Picture]From: shultz_flory
2010-07-02 11:47 am
Каждая варежка - не получится для крайних в шеренге.
(Ответить) (Thread)
[User Picture]From: avva
2010-07-02 11:51 am
Имеется в виду, что всякий раз, когда две варежки встречаются, они одного цвета.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2010-07-02 11:55 am
Кстати, я хочу отдельно сказать, что по-хорошему завидую всем, кто сам додумался до трюка "после построения часть из них развернется так, чтобы все совпало". Это не правильное решение, и условия задачи это запрещают - но отличный пример ломки стереотипа, thinking outside the box. Я сам эту задачку решил, но в процессе решения эта идея мне и в голову не пришла.

Edited at 2010-07-02 11:59 (UTC)
(Ответить) (Thread)
[User Picture]From: d_m_
2010-07-02 12:06 pm
Это потому, что Вы решали математическую задачку, а не т.н. головоломку :)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: alex_wmd
2010-07-02 11:58 am
каждый мудрец упорядочивает числа остальных, постепенно перестанавливая соседние числа местами. и в зависимости от чётности количества таких перестановок выбирает какую варежку на какую руку надеть (договариваются заранее).
(Ответить) (Thread)
[User Picture]From: old_radist
2010-07-02 11:58 am
Мудрецам написали номера, выдали варежки, построили в шеренгу. Теперь что ж, теперь и тачки выдадут. И паек.
Можно было бы хоть в пятницу не о политике?..

:(((

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

пыщ-пыщ.

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

Edited at 2010-07-02 12:05 (UTC)
(Ответить) (Thread)
[User Picture]From: avva
2010-07-02 12:09 pm
(Ответить) (Parent) (Thread)
[User Picture]From: d_m_
2010-07-02 12:00 pm
Решение.

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

Доказательство воистину замечательно, но не влезает на поля :)
(Ответить) (Thread)
[User Picture]From: tishika
2010-07-02 12:03 pm
Числа идут не подряд, естественно?
(Ответить) (Thread)
[User Picture]From: avva
2010-07-02 12:05 pm
Не подряд, и вообще необязательно целые.
(Ответить) (Parent) (Thread)
[User Picture]From: knop
2010-07-02 12:12 pm
Меня сегодня около десятка новых людей зафрендили.
Такая вот неожиданная глория мунди ;-)
(Ответить) (Thread)
[User Picture]From: buddha239
2010-07-02 12:16 pm
Всех пронумеровать. Дальше каждый смотрит на число инверсий в тех числах, которые видит, прибавляет свой номер, и надевает перчатки в зависимости от четности результата.

Схема работает, если числа упорядочены так же, как мудрецы, и не портится, если поменять два числа местами.
(Ответить) (Thread)
[User Picture]From: spamrobot3
2010-07-04 11:32 am
А вы можете так же красиво лаконично, как изложили решение и канву доказательства, доказать "и не портится, если поменять числа местами"? Мне пришлось долго возиться с подсчетом инверсий в общем случае.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: knop
2010-07-02 12:24 pm
Дабы уж быть совсем точным, то задача это не моя, а вычитанная в книжке. Там, правда, были шляпы на голове вместо варежек на руках, но суть решения от этого не менялась.

(Ответить) (Thread)
[User Picture]From: avva
2010-07-02 12:32 pm
каждая шляпа двуцветная, и нужно сориентировать? или как?
(Ответить) (Parent) (Thread) (Развернуть)
Страница 1 из 4
<<[1] [2] [3] [4] >>