ChessPro online

Забавные задачки и головоломки

вернуться в форум

30.09.2007 | 20:54:28

Главная  -  Поговорим?  -  Наука

212

MikhailK

1 разряд

29.10.2008 | 09:58:40
Email

все его сообщения:
за день, за месяц,
за все время
Looking:
Sad_Donkey:
А можно так. Всегда есть автомобиль на котором можно доехать до следующего. Можно считать, что бензин следующего уже находится на этом автомобиле; а следующий этот - изъять "на минуточку".
Годится?
Это не гарантирует, что будет выбрана пара автомобилей, бензина которых хватит доехать до третьего.
Если выбирать сразу пару, бензина которых хватит доехать до третьего, то не гарантирует, что бензина 3-х хватит доехать до четвертого.

Looking, Вы немного неправильно рассуждаете. Никто не собирается ехать на выбранном автомобиле. Важно, что с помощью описанного трюка можно "изъять" один автомобиль. Повторяя этот трюк много раз, можно оставить только один автомобиль. Вот на этом оставшемся и можно будет сделать полный оборот.
номер сообщения: 49-2-1256

213

Looking

29.10.2008 | 10:27:23

все его сообщения:
за день, за месяц,
за все время
MikhailK:
Looking, Вы немного неправильно рассуждаете. Никто не собирается ехать на выбранном автомобиле. Важно, что с помощью описанного трюка можно "изъять" один автомобиль. Повторяя этот трюк много раз, можно оставить только один автомобиль. Вот на этом оставшемся и можно будет сделать полный оборот.

Но задачу надо решить для цепочки автомобилей и полной длины трассы, а не для последнего остатка. Смысл изъятий я понимаю как получить последовательность, которая будет потом "отмотана" обратно.
Аналогия: решение системы линейных уравнений методом Гаусса. Сначала цепочка по уменьшению количества неизвестных на каждом шаге, а потом обратный ход.
номер сообщения: 49-2-1257

214

MikhailK

1 разряд

29.10.2008 | 10:43:11
Email

все его сообщения:
за день, за месяц,
за все время
Looking:
Но задачу надо решить для цепочки автомобилей и полной длины трассы, а не для последнего остатка.

Так ведь этот оставшийся один автомобиль сможет пройти всю трассу и в случае цепочки автомобилей и полной длины трассы.
номер сообщения: 49-2-1258

215

Looking

29.10.2008 | 11:02:56

все его сообщения:
за день, за месяц,
за все время
MikhailK:
Looking:
Но задачу надо решить для цепочки автомобилей и полной длины трассы, а не для последнего остатка.

Так ведь этот оставшийся один автомобиль сможет пройти всю трассу и в случае цепочки автомобилей и полной длины трассы.
Для произвольного автомобиля может не соблюдаться.
Пример цепочки (А-автомобиль, Т-трасса, число длина отрезка трассы и сколько может проехать автомобиль):
А6-Т3-А2-Т6-А7-Т5-А7-Т8 последний участок трассы Т8 примыкает с другой стороны к автомобилю А6.
Если автомобиль А6 начинает двигаться в направлении куска Т8, то он не доедет до автомобиля А7. Если движется по направлению к А2, то он до него доедет. Вместе со слитым бензином дальше сможет проехать 5, а отрезок длиной 6. Т.е. условие выбора произвольного автомобиля с бензином достаточным, что бы доехать до следующего не является полным. Нужны еще дополнительные условия, по выбору первого автомобиля.
Я понимаю вашу логику, но посли изъятия одного автомобиля и соединения участков смежных к нему задача не становится эквивалентной.
Т.е. изъяв автомобиль А2 получаем между А6 и А7 (по прямому направлению) участок длиной 9 но автомобиль А6 может ехать 8 только в прямом направлении в обратном он может ехать только 6.
номер сообщения: 49-2-1259

216

MikhailK

1 разряд

29.10.2008 | 11:38:27
Email

все его сообщения:
за день, за месяц,
за все время
Looking:
MikhailK:
Looking:
Но задачу надо решить для цепочки автомобилей и полной длины трассы, а не для последнего остатка.

Так ведь этот оставшийся один автомобиль сможет пройти всю трассу и в случае цепочки автомобилей и полной длины трассы.
Для произвольного автомобиля может не соблюдаться.
Пример цепочки (А-автомобиль, Т-трасса, число длина отрезка трассы и сколько может проехать автомобиль):
А6-Т3-А2-Т6-А7-Т5-А7-Т8 последний участок трассы Т8 примыкает с другой стороны к автомобилю А6.
Если автомобиль А6 начинает двигаться в направлении куска Т8, то он не доедет до автомобиля А7. Если движется по направлению к А2, то он до него доедет. Вместе со слитым бензином дальше сможет проехать 5, а отрезок длиной 6. Т.е. условие выбора произвольного автомобиля с бензином достаточным, что бы доехать до следующего не является полным. Нужны еще дополнительные условия, по выбору первого автомобиля.
Я понимаю вашу логику, но посли изъятия одного автомобиля и соединения участков смежных к нему задача не становится эквивалентной.
Т.е. изъяв автомобиль А2 получаем между А6 и А7 (по прямому направлению) участок длиной 9 но автомобиль А6 может ехать 8 только в прямом направлении в обратном он может ехать только 6.

Ладно, объясняю подробно. Дано
А6-Т3-А2-Т6-А7-Т5-А7-Т8 (движемся слева направо)

1) Изымаем автомобиль А2. В результате получаем

А8-Т9-А7-Т5-А7-Т8

2) Изымаем автомобиль А7 (который после T5). В результате получаем

А8-Т9-А14-Т13

3) Изымаем автомобиль А8. В результате получаем

А22-Т22

Остался один автомобиль. Если провернуть операции обратно, то находим, что автомобилем А22 в исходной постановке был А7 (который перед T5)

Ответ. Автомобиль А7 (который перед T5) может сделать полный круг.
А6-Т3-А2-Т6-А7-Т5-А7-Т8
Теперь понятно? Порядок изъятия автомобилей совершенно не важен. Главное, изымать на каждом шаге тот автомобиль до которого можно доехать (такой всегда есть).
номер сообщения: 49-2-1260

217

Looking

29.10.2008 | 12:44:02

все его сообщения:
за день, за месяц,
за все время
Ясно, но дополнительное условие все-же есть.
При изъятии следующего автомобиля направление движения принятое на первом шаге должно сохраняться.
Например участок Т8 будет Т7.5, а Т5 будет Т5.5
Т.е. цепочка будет А6-Т3-А2-Т6-А7-Т5.5-А7-Т7.5
Если на втором шаге рассматривать А7 между участками Т5.5 и Т7.5, то он может доехать до другого А7 (в обратную сторону). Тогда изъяв этот (второй) А7 между Т5.5 и полученного на предыдущем шаге Т9 получаем, что оставшийся А7/14 не сможет доехать в сторону Т7.5 туда он может ехать 7 ни в сторону Т14.5 (9+5.5)
И еще, наверное, проверку надо прозводить последовательно двигаясь от первого шага по кругу.
номер сообщения: 49-2-1261

218

MikhailK

1 разряд

29.10.2008 | 12:46:43
Email

все его сообщения:
за день, за месяц,
за все время
Looking: Ясно, но дополнительное условие все-же есть.
При изъятии следующего автомобиля направление движения принятое на первом шаге должно сохраняться.

Естественно. Мне даже в голову не приходило менять направление движения.
Looking:
И еще, наверное, проверку надо прозводить последовательно двигаясь от первого шага по кругу.

А вот это совсем не обязательно.
номер сообщения: 49-2-1262

219

azur

левый 2506

29.10.2008 | 16:08:51
Email

все его сообщения:
за день, за месяц,
за все время
iourique: Давайте и я задачку подкину. Она некоторое время ходила в интернете, так что кто-то ее может знать. Условие сложноватое, но ответ совершенно удивительный.

Есть четыре заключенных, приговоренных к смертной казни. Им дают последний шанс на спасение:

Карточки с их именами кладут в 4 шкатулки, которые ставят в ряд на столе в отдельной комнате. Смертники по очереди входят в эту комнату. Входящий может открыть одну из шкатулок, прочесть имя на карточке, потом - при желании - открыть еще одну шкатулку и прочесть спрятанное в ней имя. После чего карточки с именами возвращаются туда, где они лежали, узника возвращают в его камеру. Всех четырех освободят, если каждый найдет карточку со своим именем; иначе - всех казнят. Заключенные могут договориться о стратегии до начала испытания, но не могут общаться во время него. Двигать шкатулки, гнуть карточки, и т.п. запрещено. Каковы шансы узников на спасение при использовании наилучшей стратегии?

Две стратегии для затравки:
1) открывать наугад - вероятность найти свое имя: 1/2 для каждого, вероятность спастись - 1/16;
2) первые двое открывают две левых шкатулки, последние двое - две правых. Вероятность спастись - 1/6.

Задача легко обобщается на n узников, каждый из которых может открыть k шкатулок.

У меня получилось так, что если перенумеровать заключенных и шкатулки, шансы спастись достигают 10/24, т.е. близки к 50% ..
(Каждый сначала открывает "свою" и если видит там чужое имя, то открывает соответствующую "чужую")

Наверно это неоптимально ..??
номер сообщения: 49-2-1263

220

iourique

29.10.2008 | 16:21:43

все его сообщения:
за день, за месяц,
за все время
azur:
iourique: Давайте и я задачку подкину. Она некоторое время ходила в интернете, так что кто-то ее может знать. Условие сложноватое, но ответ совершенно удивительный.

Есть четыре заключенных, приговоренных к смертной казни. Им дают последний шанс на спасение:

Карточки с их именами кладут в 4 шкатулки, которые ставят в ряд на столе в отдельной комнате. Смертники по очереди входят в эту комнату. Входящий может открыть одну из шкатулок, прочесть имя на карточке, потом - при желании - открыть еще одну шкатулку и прочесть спрятанное в ней имя. После чего карточки с именами возвращаются туда, где они лежали, узника возвращают в его камеру. Всех четырех освободят, если каждый найдет карточку со своим именем; иначе - всех казнят. Заключенные могут договориться о стратегии до начала испытания, но не могут общаться во время него. Двигать шкатулки, гнуть карточки, и т.п. запрещено. Каковы шансы узников на спасение при использовании наилучшей стратегии?

Две стратегии для затравки:
1) открывать наугад - вероятность найти свое имя: 1/2 для каждого, вероятность спастись - 1/16;
2) первые двое открывают две левых шкатулки, последние двое - две правых. Вероятность спастись - 1/6.

Задача легко обобщается на n узников, каждый из которых может открыть k шкатулок.

У меня получилось так, что если перенумеровать заключенных и шкатулки, шансы спастись достигают 10/24, т.е. близки к 50% ..
(Каждый сначала открывает "свою" и если видит там чужое имя, то открывает соответствующую "чужую")

Наверно это неоптимально ..??


Оптимально .
номер сообщения: 49-2-1264

221

azur

левый 2506

29.10.2008 | 16:41:56
Email

все его сообщения:
за день, за месяц,
за все время
iourique:
azur:
Наверно это неоптимально ..??


Оптимально .

Меня смутила "легкость" обобщения - сходу ни за что бы не посчитал шансы спастись в случае с бОльшим количеством заключенных и шкатулок ..
номер сообщения: 49-2-1265

222

iourique

29.10.2008 | 16:57:52

все его сообщения:
за день, за месяц,
за все время
azur:
iourique:
azur:
Наверно это неоптимально ..??


Оптимально .

Меня смутила "легкость" обобщения - сходу ни за что бы не посчитал шансы спастись в случае с бОльшим количеством заключенных и шкатулок ..


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

Кстати, можно посчитать вероятность спасения при числе узников, стремящемся к бесконечности, если им разрешают открывать ровно половину коробок.
номер сообщения: 49-2-1266

223

Quantrinas

Любитель
НН / R

30.10.2008 | 19:04:59

все его сообщения:
за день, за месяц,
за все время
Сегодня решал задачу.

В некотором царстве-государстве есть казна на чёрный день, в ней 500 миллиардов баксиков. В день из казны тратится 5 миллиардов тугриков на поддержание курса тугрика. На сколько дней хватит казны, если считать, что один баксик равен 27 тугрикам?

А если в неделю тратиться 30 миллиардов баксиков на поддержку перекредитования купчин толстопузых?



__________________________
Audiatur et altera pars
номер сообщения: 49-2-1267

224

azur

левый 2506

30.10.2008 | 22:30:32
Email

все его сообщения:
за день, за месяц,
за все время
Quantrinas: Сегодня решал задачу.

В некотором царстве-государстве есть казна на чёрный день, в ней 500 миллиардов баксиков. В день из казны тратится 5 миллиардов тугриков на поддержание курса тугрика. На сколько дней хватит казны, если считать, что один баксик равен 27 тугрикам?

А если в неделю тратиться 30 миллиардов баксиков на поддержку перекредитования купчин толстопузых?


Тут кофейную гущу надо попробовать

iourique:
azur: Меня смутила "легкость" обобщения - сходу ни за что бы не посчитал шансы спастись в случае с бОльшим количеством заключенных и шкатулок ..


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

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

Про это можно где-нибудь почитать?
номер сообщения: 49-2-1268

225

iourique

31.10.2008 | 00:30:23

все его сообщения:
за день, за месяц,
за все время
azur:
iourique:
azur: Меня смутила "легкость" обобщения - сходу ни за что бы не посчитал шансы спастись в случае с бОльшим количеством заключенных и шкатулок ..


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

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

Про это можно где-нибудь почитать?


Честно говоря не знаю. Производящую функцию сам нашел, это не очень сложно, будет время - напишу. Вот здесь есть похожая задачка (да и сам сайт неплохой).
номер сообщения: 49-2-1269

226

iourique

31.10.2008 | 06:29:02

все его сообщения:
за день, за месяц,
за все время
В продолжение: правильная стратегия в общем случае точно такая же - сначала открывается своя шкатулка, потом того, чье имя лежит в первой, потом того, чье имя во второй и т.д. Оптимальность доказывать не буду - муторно. Соль же в том, что если первый находит свое имя, то свое имя также находят все, чьи имена первый прочел. Для общего же спасения нужно, чтобы в перестановке из n элементов не было циклов длины больше k. Пусть a(n,k) - вероятность такого события. Очевидно, a(n,k) = 1, если n не больше k. Первый элемент оказывается в цикле длины s с вероятностью 1/n. Отсюда a(n,k) = 1/n (a(n-1,k)+a(n-2,k)+...+a(n-k,k)). Пусть А(k) = sum_n a(n,k)x^n - производящая функция. Из рекурентного соотношения следует после некоторых алгебраических мучений, что А(k)' = (1 + x + x^2+...+x^{k-1})A(k), т.е. A(k) = exp{x + x^2/2 + x^3/3 +...+x^k/k} = exp(x^{k+1}/(k+1) + x^{k+2}/{k+2}+....)/(1 - x). Отсюда довольно легко вывести, что а(2k,k) = 1 - 1/(k+1) - 1/(k+2) -...-1/(2k) (это, впрочем, можно и легче получить), и, следовательно, предел a(2k,k) при k, стремящемся к бесконечности, равен 1 - ln 2.
номер сообщения: 49-2-1270

227

MikhailK

1 разряд

31.10.2008 | 14:46:42
Email

все его сообщения:
за день, за месяц,
за все время
Мне удалось удачно формализовать условие и решение задачи об автомобилях на трассе. Решение оказалось очень простым и следует из того, что периодическая функция всегда больше (или равна) своего минимального значения.

Выберем произвольный автомобиль и начнём двигаться с ним по трассе, переливая бензин из встречающихся автомобилей. В какой-то момент количество бензина может стать отрицательным, но не будем обращать на это внимание и продолжим движение. В некоторой точке на трассе количество бензина в автомобиле достигает своего минимума. Легко сообразить ,что тот автомобиль, который находится в этой точке минимума и даёт решение задачи.
номер сообщения: 49-2-1273

228

iourique

31.10.2008 | 16:24:45

все его сообщения:
за день, за месяц,
за все время
Вот еще задачка на коллективную информацию: есть три мудреца и неограниченное количество белых и черных колпаков. На мудрецов надевают колпаки, так что они видят колпаки других, но не свой колпак. После этого каждый из них записывает на бумажку одно из трех слов: "белый", "черный", или "пас". Мудрецы выигрывают, если хоты бы один из них угадал цвет своего колпака и ни один не ошибся и проигрывают во всех остальных случаях (3 паса - тоже проигрыш). О стратегии можно договориться заранее, после этого любой обмен информацией запрещен. Какова правильная стратегия? Вероятность выигрыша? Что если мудрецов семь?
номер сообщения: 49-2-1274

229

MikhailK

1 разряд

01.11.2008 | 12:21:36
Email

все его сообщения:
за день, за месяц,
за все время
iourique: Вот еще задачка на коллективную информацию: есть три мудреца и неограниченное количество белых и черных колпаков. На мудрецов надевают колпаки, так что они видят колпаки других, но не свой колпак. После этого каждый из них записывает на бумажку одно из трех слов: "белый", "черный", или "пас". Мудрецы выигрывают, если хоты бы один из них угадал цвет своего колпака и ни один не ошибся и проигрывают во всех остальных случаях (3 паса - тоже проигрыш). О стратегии можно договориться заранее, после этого любой обмен информацией запрещен. Какова правильная стратегия? Вероятность выигрыша?
У меня получилось, что вероятность выигрыша равна 0.5. Мудрецы договариваются, что два из них пасуют, а третий называет цвет наобум. Мне не удалось в решении использовать тот факт, что мудрецы видят колпаки других мудрецов.

iourique: Что если мудрецов семь?

Тут работает та же стратегия, что и при трёх мудрецах. Подумаю, можно ли её улучшить.
номер сообщения: 49-2-1275

230

Sad_Donkey

КМС

01.11.2008 | 13:43:23

все его сообщения:
за день, за месяц,
за все время
MikhailK: Мне удалось удачно формализовать условие и решение задачи об автомобилях на трассе. Решение оказалось очень простым и следует из того, что периодическая функция всегда больше (или равна) своего минимального значения.

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


Мне казалось, что любая функция "всегда больше (или равна) своего минимального значения"(?). И потому, из этого вряд ли что-нибудь может следовать...
То, что "легко сообразить", я вообще никак сообразить не могу...
Как количество бензина в автомобиле может быть отрицательным - даже представить себе не могу... А уж продолжать движение на нем, при этом, так и вообще - упаси, Боже!..
Похоже, у меня катастрофа с абстрактным мышлением... "Мартышка к старости слаба мозгами стала"...
номер сообщения: 49-2-1276

231

Sad_Donkey

КМС

01.11.2008 | 13:49:38

все его сообщения:
за день, за месяц,
за все время
Простая, но забавная маленькая задачка.
На шахматной доске стоит фигура "лев", которая может ходить так: на соседнее поле вверх или вправо или вниз-налево (то есть, по диагонали).
Можно ли этой фигурой обойти шахматную доску, побывав на каждом поле ровно один раз и встав последним ходом на исходную клетку?
номер сообщения: 49-2-1277

232

MikhailK

1 разряд

01.11.2008 | 14:13:38
Email

все его сообщения:
за день, за месяц,
за все время
Sad_Donkey:
MikhailK: Мне удалось удачно формализовать условие и решение задачи об автомобилях на трассе. Решение оказалось очень простым и следует из того, что периодическая функция всегда больше (или равна) своего минимального значения.

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


Мне казалось, что любая функция "всегда больше (или равна) своего минимального значения"(?). И потому, из этого вряд ли что-нибудь может следовать...
То, что "легко сообразить", я вообще никак сообразить не могу...
Как количество бензина в автомобиле может быть отрицательным - даже представить себе не могу... А уж продолжать движение на нем, при этом, так и вообще - упаси, Боже!..
Похоже, у меня катастрофа с абстрактным мышлением... "Мартышка к старости слаба мозгами стала"...


Вторая попытка.

1) Берём произвольный автомобиль и совершим на нём полный оборот по трассе, переливая бензин из обгоняемых машин.

2) На финише количество бензина будет равно нулю.

3) В некоторой точке на трассе количество бензина в автомобиле достигает своего минимума. Обозначим это количество бензина через p (p<=0).

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

5) Расставим (и заправим) заново автомобили по трассе и сядем в тот автомобиль, который оказался в точке минимума. Легко сообразить (?!), что в этом автомобиле всегда будет на -p литров бензина больше, чем в первоначально выбранном автомобиле, а значит количество бензина в нём будет всегда положительным.
номер сообщения: 49-2-1278

233

MikhailK

1 разряд

01.11.2008 | 14:35:59
Email

все его сообщения:
за день, за месяц,
за все время
Sad_Donkey: Простая, но забавная маленькая задачка.
На шахматной доске стоит фигура "лев", которая может ходить так: на соседнее поле вверх или вправо или вниз-налево (то есть, по диагонали).
Можно ли этой фигурой обойти шахматную доску, побывав на каждом поле ровно один раз и встав последним ходом на исходную клетку?


для доски 8 на 8 я решил.
номер сообщения: 49-2-1279

234

iourique

01.11.2008 | 18:13:32

все его сообщения:
за день, за месяц,
за все время
MikhailK:
Sad_Donkey: Простая, но забавная маленькая задачка.
На шахматной доске стоит фигура "лев", которая может ходить так: на соседнее поле вверх или вправо или вниз-налево (то есть, по диагонали).
Можно ли этой фигурой обойти шахматную доску, побывав на каждом поле ровно один раз и встав последним ходом на исходную клетку?


для доски 8 на 8 я решил.


В общем случае, кажется, тоже нет. Обобщающееся решение: так как маршрут кольцевой, он должен содержать следующую последовательность ходов: a8-b8-...-g1-h1-h2-...-a7-a8. Но как пройти от h2 к a7, не пересекая пути из b8 в g1?
номер сообщения: 49-2-1280

235

azur

левый 2506

01.11.2008 | 19:47:43
Email

все его сообщения:
за день, за месяц,
за все время
iourique: В продолжение: правильная стратегия в общем случае точно такая же - сначала открывается своя шкатулка, потом того, чье имя лежит в первой, потом того, чье имя во второй и т.д. Оптимальность доказывать не буду - муторно. Соль же в том, что если первый находит свое имя, то свое имя также находят все, чьи имена первый прочел. Для общего же спасения нужно, чтобы в перестановке из n элементов не было циклов длины больше k.

Спасибо, очень интересно ..

В свое время одна (не математическая, но весьма даже шахматная) проблема привела к необходимости посчитать количество неизоморфных "латинских" матриц mxn. Помучался сам день-другой и .. полез в инет. И хоть дело прояснилось только для случая 2хn, зато в процессе поисков познакомился с несколькими интересными математиками, работающими в области комбинаторики .. :-)
номер сообщения: 49-2-1281

236

Sad_Donkey

КМС

01.11.2008 | 20:15:26

все его сообщения:
за день, за месяц,
за все время
iourique:
В общем случае, кажется, тоже нет. Обобщающееся решение: так как маршрут кольцевой, он должен содержать следующую последовательность ходов: a8-b8-...-g1-h1-h2-...-a7-a8. Но как пройти от h2 к a7, не пересекая пути из b8 в g1?


А почему вы написали "кажется"? Вы не уверены в точности ваших рассуждений?
номер сообщения: 49-2-1282

237

iourique

01.11.2008 | 22:29:15

все его сообщения:
за день, за месяц,
за все время
MikhailK:
iourique: Вот еще задачка на коллективную информацию: есть три мудреца и неограниченное количество белых и черных колпаков. На мудрецов надевают колпаки, так что они видят колпаки других, но не свой колпак. После этого каждый из них записывает на бумажку одно из трех слов: "белый", "черный", или "пас". Мудрецы выигрывают, если хоты бы один из них угадал цвет своего колпака и ни один не ошибся и проигрывают во всех остальных случаях (3 паса - тоже проигрыш). О стратегии можно договориться заранее, после этого любой обмен информацией запрещен. Какова правильная стратегия? Вероятность выигрыша?
У меня получилось, что вероятность выигрыша равна 0.5. Мудрецы договариваются, что два из них пасуют, а третий называет цвет наобум. Мне не удалось в решении использовать тот факт, что мудрецы видят колпаки других мудрецов.


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

238

iourique

01.11.2008 | 22:31:03

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


Уверен. Но всегда есть вероятность провраться. Так что "кажется" - это то, что по-английски называется hedging .
номер сообщения: 49-2-1284

239

MikhailK

1 разряд

01.11.2008 | 22:40:39
Email

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

Да я понимаю... Но в чём секрет пока понять не могу.
номер сообщения: 49-2-1285

240

jenya

02.11.2008 | 01:04:28

все его сообщения:
за день, за месяц,
за все время
iourique: Вот еще задачка на коллективную информацию: есть три мудреца и неограниченное количество белых и черных колпаков. На мудрецов надевают колпаки, так что они видят колпаки других, но не свой колпак. После этого каждый из них записывает на бумажку одно из трех слов: "белый", "черный", или "пас". Мудрецы выигрывают, если хоты бы один из них угадал цвет своего колпака и ни один не ошибся и проигрывают во всех остальных случаях (3 паса - тоже проигрыш). О стратегии можно договориться заранее, после этого любой обмен информацией запрещен. Какова правильная стратегия? Вероятность выигрыша? Что если мудрецов семь?


Трем мудрецам я бы посоветовал такую стратегию: говорить пас, если на двух собратьях колпаки разных цветов. Если же на них колпаки одного цвета, надо записать на бумажку другой цвет. Стратегия не работает, если на всех мудрецах колпаки одного цвета. То есть, вероятность выигрыша - три четверти.
номер сообщения: 49-2-1286

241

iourique

02.11.2008 | 04:00:56

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


Это, конечно, правильно. За 7 возьметесь?

Если нет, давайте я еще схитрю: я нигде не говорил, что колпаки надеваются случайно и равновероятно. Предположим, что организаторы игр - те еще жуки, и, увидев, что мудрецы пользуются определенной стратегией, начинают ей противодействовать, например, чаще надевая на всех мудрецов колпаки одного цвета. Если мудрецы могут передоговариваться перед каждым раундом, смогут ли они все равно обеспечить себе выигрыш с вероятностью 3/4?
номер сообщения: 49-2-1287