Тема: Логические загадки-4

[Арвинд›]

Maeglor, просто надо думать не о том, почему задачу нельзя решить, а том, как её решить.
Решение есть, это я говорю как краевед  

               

               

[Maeglor›]

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


               

               

[Kэt›]

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

 

               

               

[Арвинд›]

Правила форума, пункт 3.
Цитата:
Если на вопрос не дан правильный ответ в течении не менее 7 дней, а также в течении не менее чем 3 дней нет никакой активности со стороны отвечающих (наводящие вопросы, уточнения, версии и пр.) то автор вопроса ОБЯЗАН сам дать правильный ответ.
 
Увы, следующим постом выложу решение. Кто хочет думать над "колпаками" дальше - не читать!


               

               

[Erlom-Tiu›]

Думаю, в таком случае не грех и подсказать.

(на случай 3 человек)

Какова вероятность, что на всех трёх будут колпаки одного цвета?

И как каждый может оценить, стоит ли ему угадывать свой колпак?


               

               

[Арвинд›]

Раз уж я обещал выложить решение, так выкладываю. Пока все решали, я думал, что написать - результат получился очень объемистым.

Кому последняя подсказка Erlom-Tiu дает повод зацепиться и еще думать - тому можно просто не читать.

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

Кто хочет быстро и просто понять, как решать - читайте второй пост. Кого интересуют все подробности - с первого по третий. Этот был нулевой  

               

               

[Арвинд›]

Сначала введем обозначения и определения.
Количество игроков: N.
Цвета шляпы пронумеруем: 0, 1.
Все возможные комбинации шляп образуют единичный куб в N-мерном пространстве (т.е. множество наборов из N координат, каждая из которых может быть принимать значение 0 или 1).
Количество комбинаций: M = 2^N

Стратегия одного игрока - функция от N-1 переменной (т.е. от цветов тех шляп, что он видит). Значения этой функции: 0, 1, пас.
Стратегия S команды = набор стратегий игроков. Для каждого из M исходов стратегия даст выигрыш (обозначим его 1) или проигрыш (0). Каждая стратегия S может быть задана в виде таблицы из M строк, N столбцов для игроков и одного - для общего результата (дальше пример от балды):

	1	2	...	N	S
00...00	+	-			0
00...01			+		1
<...>					0
01...11		+	+		1
10...00	-	-			0
<...>					0
11...10	+			-	0
11...11			-	+	0

Мы пишем для i-ого игрока "+", если он угадал, "-" - если не угадал, пусто - если пасовал. Наша задача теперь описать, как должны быть расставлены плюсы и минусы в таблице для того, чтобы в итоговом столбце получилось максимальное число единиц.
Мы знаем, что команда выигрывает в данной строке, только если в ней встречается как минимум один плюс и не встречается минусов. Назовем два расклада соседними по i-ой координате, если у них совпадают все координаты, кроме i-ой (а в ней, естественно, противоположные значения). Из условия задачи ясно, что:
если игрок i угадал цвет своей шляпы в раскладе R, то в раскладе, соседнем с R по координате i, этот игрок обязательно ошибется! (*)

Для простоты предположим, что у нас есть несколько строк, на которых (в сумме) отвечают все имеющиеся игроки. Давайте на этом множестве строк рассмотрим такую модельку: первый игрок ставит где-то плюсик, и в соседней (по его координате) строке ставит минус. Второй ставит один плюс и один минус так, чтобы не сделать хуже. Как именно? Очень просто - чтобы не увеличивать общее количество проигрышей, ему надо поставить свой минус в ту же строку, что и первый! (как там в шахматах обозначают сильный ход?   ). Разумеется, он обязан поставить плюс в соседнюю с "минусовой" строчку, - но уже по своей координате (а это не строка, в которой стоял плюс у первого!). Третий присобачивает минус в строчку к имеющимся, а плюс - в соседнюю, по своей, опять же, координате! Таким образом, если бы игроки имели возможность смотреть на всю картинку "сверху" и решать, как распоряжаться голосами, то условие (*) привело бы их к такой наилучшей расстановке плюсов и минусов:

-	-	-	-
+
	+
		+
			+

В этой умозрительно наилучшей модели на строку из N минусов приходится N строк, в каждой из которых по одному плюсу. И тогда общая вероятность выигрыша составит N/N + 1 !
Спрашивается: в каких случаях игроки могут выйти на такую "плановую мощность"? На вопрос, возможно ли это вообще, положительно отвечает пример N = 3.

               

               

[Арвинд›]

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

• Видишь две белые шляпы - говори "черная".
  
• Видишь две черные - говори "белая".
  
• Видишь разные цвета - молчи.

Казалось бы - если игрок видит две белые шляпы, это никак не сказывается на вероятности черной шляпы на нем. Он угадывает только в половине случаев. Но...
По нашей стратегии игрок проиграет, если все шляпы одного цвета. А это только два случая из восьми. Давайте нарисуем таблицу всех исходов (обозначая нулем белый цвет шляпы, единицей - черный, плюсом - верный ответ игрока, минусом - неверный):

000	-	-	-
001			+
010		+
100	+
111	-	-	-
110			+
101		+
011	+

Итак, фишка в том, что игрок не угадывает в половине случаев, - и с ним вместе ошибаются все! Случаи же угадывания игроками своих цветов разнесены по разным исходам.
Как было (неформально) показано ранее, такая стратегия действительно является оптимальной. Вероятность выигрыша при ней равна 3/4.

               

               

[Арвинд›]

Теперь опять вернемся к N игрокам. Множество всех исходов является, повторюсь, единичным кубом. В нем расстоянием между точками назовем сумму модулей покоординатных разностей. В частности, расстояние между точками будет равно единице, если они являются соседними по какой-то одной координате. Единичной сферой в смысле приведенного расстояния будет являться множество всех точек, соседних с данной (центром сферы). Единичным шаром будет являться множество, состоящее из сферы и ее центра.
Предположим, что единичный куб состоит из p непересекающихся единичных шаров. В этом случае игроки могут воспользоваться таким делением и согласиться дружно проигрывать в центрах шаров, но зато выигрывать во всех точках сфер! Для этого игроки должны исходить из предположения, что они не попали центр (система шаров должна быть зафискирована заранее, конечно).
Подробнее, данная стратегия должна быть такой:
я посмотрел на шляпы всех остальных и дополнил весь набор нулем (предположил, что моя шляпа нулевого цвета). Получим общий "расклад" R₀. Дополним известный набор единицей - получим точку R₁. Если я - игрок с номером i, то точки R₀ и R₀ будут соседними по i-ой координате. Стратегия должна состоять из одного-единственного правила: если среди точек R₀ и R₁ одна является центром шара, то я выбираю другую. В противном случае я молчу.
Давайте посмотрим, как будет работать стратегия.
На первом этапе игроки зафиксировали систему шаров.
На втором этапе случайным образом была выбрана точка N-мерного куба.
На третьем этапе все игроки применяют описанную стратегию.
В хорошем случае выпавшая точка принадлежит какой-то сфере. Значит, среди всех центров шаров есть только один, расстояние до которого от выпавшей точки равно единице. Это, в свою очередь, значит, что есть только одна координата i, по которой выпавшая точка оказывается соседней с центром. Все игроки, кроме i-ого, не могут решить, как им голосовать, и пасуют. Игрок с номером i отвечает правильно.
Пусть выпал плохой случай. Тогда все игроки, подставляя правильное значение своей шляпы, обнаружат себя в центре шара, и предпочтут другое, неправильное значение.

Итак, мы видим, что описанная стратегия как раз дает нам ту "идеальную" картинку, что нарисовалась при рассмотрении условия (*). Есть строка, в которую все игроки лепят минусы, но зато каждый игрок по отдельности ставит плюс в строку, соседнюю с минусовой по его собственной координате. Таким образом, мы действительно нашли наилучшую стратегию с вероятностью выигрыша N/N+1.

Все, что было написано до сих пор, не требовало никакой математики! Но остается два вопроса, на которые без математики уже не ответишь. Первый: при каких N возможно такое деление единичного куба на систему непересекающихся единичных шаров? Второй: каков алгоритм выбора центров этих шаров - т.е. каким наиболее простым способом игрокам решать, что им ответить?
Ответ можно найти в теории кодов Хэмминга.
Для того, куб можно было разложить на шары, необходимо и достаточно, чтобы нашлось такое k, для которого:
N = 2^k - 1.
При этом алгоритмически простое решение (внешне непохожее на изложенное, но на самом деле к нему сводящееся) выглядит так:
каждый игрок имеет номера от 1 до N, что соответствует наборам из k координат от (00..1) до (11..1).
Суммой наборов назовем покоординатную сумму по модулю два, например: 1011 + 1101 = 0110. Сумма любого набора с собой будет нулевым набором.
Когда игрок увидит шляпы других игроков, он должен будет выделить игроков, на ком он видит черные (скажем) шляпы, и составить сумму их наборов. Если он получает нулевую сумму, то он говорит "на мне черная". Если он получает сумму, которая соответствует его собственному набору, он говорит "на мне белая". Во всех остальных случаях он молчит.
Алгоритм основан на том, что центрами шаров будут являться такие точки, для которых указанная сумма будет нулем.

Ну и последние замечания:
1. Интересно отметить, что чем больше игроков, тем выше вероятность выигрыша.
2. Если игрокам не повезло с количеством (оно не входит в ряд 3, 7 ,15, 31, ...), то оптимальная стратегия достигается элементарным "отцеплением" лишних - те всегда пасуют, и цвета их шляп все остальные игнорируют.
3. Для трех игроков у нас было два шара с центрами 0 00 и 1 11. Кому интересны центры шаров "по Хэммингу" для семи игроков (N = 7, k = 3, p = 16) - привожу (можете проверить на них описанное свойство с нулевыми суммами):

0000 000
0001 111
0010 110
0011 001
0100 101
0101 010
0110 011
0111 100
1000 011
1001 100
1010 101
1011 010
1100 110
1101 001
1110 000
1111 111

Это 16 раскладов из 128, в которых все игроки ошибутся. Вероятность выигрыша (128-16)/128 = 7/8, как и ожидалось.

               

               

[Maeglor›]

Признаю себя побежденным в чесной борьбе.

               

               

[azyam›]

борьба была не совсем честной, он ответ знал, а ты нет