?

Log in

задачка (математическое) - Поклонник деепричастий [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 из 3
<<[1] [2] [3] >>
[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) (Развернуть)
[User Picture]From: mikev
2010-07-02 12:58 pm
им нужно предварительно перенумероваться, а затем одеваться в зависимости от четности перестановки, которую они видят перед собой
(Ответить) (Thread)
From: (Anonymous)
2010-07-02 01:03 pm
Мудрецы могут видеть процесс одевания варежек и из этого делать выводы?
(Ответить) (Thread)
[User Picture]From: avva
2010-07-02 01:12 pm
Нет, они должны все одновременно решить и надеть.
(Ответить) (Parent) (Thread)
[User Picture]From: graf_vk
2010-07-02 01:17 pm
Договориться заранее о фиксированном порядке.

Потом каждый сравнивает то, как упорядочены все кроме него с тем, как было договорено. Если это четная перестановка -- действует как договорились, если нечетная -- наоборот.
(Ответить) (Thread)
From: (Anonymous)
2010-07-02 01:49 pm
Для начала будем считать что каждый мудрец выбирает 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 будет разным.
(Ответить) (Thread)
From: (Anonymous)
2010-07-02 01:55 pm
Вычисляется средний/средние два, договариваются о порядке варежек они, т.е мудрецы первого порядка. А дальше система самоорганизуется.
(Ответить) (Thread)
[User Picture]From: unbe
2010-07-02 02:37 pm
Мудрецы заранее назначают каждому порядковый номер.
Каждый с нечетным номером наденет белую рукавичку слева, а с четным - справа. Потом, когда дали числа на лбах, каждый мудрец смотрит: если выстроить всех, кроме меня, по порядковым номерам, сколько будет инверсий в ряду чисел на лбах. Если число инверсий нечетное, то меняет рукавицы местам.
(Ответить) (Thread)
From: ro-che.info
2010-07-02 02:38 pm
Пусть до начала шоу мудрецы занумеровались числами от 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" наденут черную варежку на левую руку, а с нечетным на правую.
(Ответить) (Thread)
[User Picture]From: jedal
2010-07-02 02:52 pm
Можно сказать, что мудрецы не надевают варежки, а говорят остатки 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, то и после обмена тоже).
(Ответить) (Thread)
[User Picture]From: bukky_boogwin
2010-07-02 03:17 pm
задача - найти алгоритм, который С ГАРАНТИЕЙ позволяет всем надеть варежки правильно, или алгоритм, который только делает вероятность этого максимальной?
(Ответить) (Thread)
[User Picture]From: avva
2010-07-02 04:05 pm
с гарантией.
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: avva
2010-07-02 04:11 pm
Да, не могут.
(Ответить) (Parent) (Thread)
Страница 1 из 3
<<[1] [2] [3] >>