A FREGIMO AMISSA

А у Вас получилось? На самом деле, третья задача - общий случай на 2^(n-1) человек и вероятность должна получиться 2^(n-1)/2^n - но это уже значительно менее тривиально, впрочем доказав оптимальность стратегии на 3 человек, легко решается общий случай - самое трудное, доказать оптимальность стратегии :)))))
P.S. Кстати, если пойдёте у меня по тэгу "загадка", найдёте ещё несколько :)

Posted by

прошу прощения - неверно поставила скобку - вероятность (2^n - 1)/2^n

Posted by

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

Posted by

Давайте я лучше сам подумаю, хорошо?

Posted by

Хотел было написать ответ для общего случая произвольного нечетного количества человек, но потом осознал, что либо я нашел более слабый алгоритм (и есть более сильный -- правильный), либо у Вас дан неверный ответ для семи человек... (Мой ответ для N=2k+1 такой: C(N,k)/2^(N-1); т.е. 35/64 для семи.)

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

Posted by

Ваш ответ неверен - правильная вероятность 7/8, или, как удобнее думать, 112/128 - в этом и есть подсказка:) Всё конечно равновериятно и независимо:)Общий случай для (2^n - 1) человек :)

Posted by

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

Posted by

Как нет? Оптимальная стратегия всегда существует для любых подслучаев (только найти ее и доказать оптимальность бывает непросто).

Posted by

Вы не поняли - я имела в виду, единой оптимальной стратегии, дающей какую-то сформулированную вероятность:)

Posted by

Для любого фиксированного N существует оптимальная стратегия, так? Каждый участник знает N. Тогда пусть применяет соответствующую стратегию в зависимости от N. Таким образом, получаем универсальную стратегию для любого N.

Я доказал оптимальность найденной стратегии для N=3, но общий случая пока не заботал; и, кроме того, нужны уточнения правил игры:
1. Могут ли участники _до_ начала игры договариваться между собой (и, в частности, знать сколько их)?
2. Может ли участник пользоваться генератором случайных чисел?

Posted by

1) Несомненно да;
2) Не вижу причины для использования....
Если Вы получите стратегию для любого N, мне (и не только мне...)будет очень интересно на это посмотреть, так как на сегодняшний день доказано только то, о чём говорила я.....

Posted by

1. Ок. Но можно и запретить, тогда будет совсем другая задача. Быть может, для нее мой ответ, написанный выше для нечетного N, является верным для оптимальной стратегии...
2. Интуитивно кажется, что да, ГСЧ не нужны. В смысле, их использование не даст никакого бонуса.

Posted by

Для разных N, кроме тех, о которых говорила я, стратегии совершенно разные.... Универсальной нет....

Posted by

Ну как же нет, когда я только что ее построил. (Из "элементарных" стратегий для каждого отдельного N. То, что эти элементарные стратегии совсем не похожи друг на друга нас не должно смущать.)

Я должен читать фразы "нет стратегий для произвольных (отличных от 2^n-1) N", "нет универсальной стратегии для любого N" как "на сегодняшний день неизвестна стратегия..."? Если так, то я не могу возразить.

Posted by

насколько я знаю, но тут не ловите меня на слове, доказано, что её и быть не может....

Posted by

Ну вот, а я предлагаю элементарное доказательство ее существования.

Стратегия -- есть функция, отображающее "видимое состояние" (игрок видит сколько-то красных шапок, сколько-то синих и видит на ком какая) во множество {"красный", "синий", "не знаю"}. Эта функция отображает конечное множество в конечное, поэтому вообще всех стратегий конечное число. Можно также считать, что каждый игрок применяет свою стратегию, которая может отличаться от стратегий других игроков. Тогда есть глобальная стратегия -- это набор N индивидуальных стратегий отдельных игроков. Глобальных стратегий тоже конечное множество. Далее можно измерить эффективность каждой глобальной стратегии -- подсчитать долю раздач, на которых данная глоб стратегия приводит к выигрышу. Эта доля и есть вероятность выигрыша. Оптимальная стратегия -- это, по определению, стратегия с наибольшей эффективностью. Она существует, поскольку выбирается из конечного множества.

Posted by

но это разные стратегии, понимаете, они не универсальны для любого N! а для того, о котором говорю я, да универсальна.... То есть для любого N, если есть 2^N-1 игроков, я могу сказать Вам УНИВЕРСАЛЬНУЮ стратегию... У меня ощущение, что мы друг друга не понимаем.....

Posted by

Что значит "универсальная"? Я ее только что построил. И она существует.

Я охотно верю, что все Ваши стратегии для N=2^n-1 очень похожи друг на друга при разных n. А для других N -- нисколько не похожи ни на Ваши, ни друг на друга. Но это не мешает использовать всё это месиво разных (кое-где похожих) стратегий для всех N, чтобы построить одну общую универсальную стратегию.

Т.е. есть мешок оптимальных для каждого отдельного N стратегий S_N(x). (Здесь x -- это "видимое состояние".) Строим универсальную стратегию S(x):

$S(x)=\left\{\begin{array}{c}S_1(x), \mbox{for 1 player}\\\dots\\S_N(x), \mbox{for N players}\\\dots\end{array}\right.$

Posted by

Да. И еще один, последний шаг: функция, отображающая число игроков N в такую глобальную стратегию. А вот разных натуральных N весьма и весьма изрядно много… :-)

Posted by

Спасибо, хорошие задачки. Вы их сами придумали?

Эту единственную я как раз пока и не решил. Мне просто ручка с бумагой не попалась, когда я над ней думал, а там, похоже, надо записывать, в голове не удерживается. Вы мне подсказки не подсказывайте! :-)

Задача о бале: я предполагал, что, во-первых, залы идентифицируемы (например, один из них заранее известен всем будущим гостям как «левый»), во-вторых, гости заранее знают, кто придет; в-третьих, что все гости до одного собираются в этом «коридоре» до того, как начинают заходить в залы; и, в четвертых, в коридоре каждый видит всех остальных, т. е. это не узкий коридор. Так можно?

И еще — там опечатка одна есть: s/стратегие/стратегии/.

Posted by

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

Posted by

все гости до одного собираются в этом «коридоре» до того, как начинают заходить в залы, в коридоре каждый видит всех остальных, т. е. это не узкий коридор - именно так:)
Придумала не сама - они достаточно известны срдеи тех, кто занимается теорией игр - особенно 2 и 3:) Просто в своё время у меня был семинар у замечательного Ноймана, вот он нам давал это на пятиминутных переменках:)

Posted by

ilanabendery.livejournal.com

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

Posted by

скорей всего она, просто в случае с 3, не ясно видна стратегия - решается, скорее, по наитию, может поэтому Вам кажется, что она не обобщается :)))))

Posted by

Мне удалось доказать оптимальность Ваших стратегий для случая N=2^n-1. Более общо, имеет место следующая оценка (для произвольных N): доля проигрышных раскладов не меньше, чем 1/(N+1). Причем равенство может достигаться лишь при N=2^n-1 (ибо только в этом случае 2^N делится на (N+1) нацело). Правда я пока не довел до конца доказательство, что при таких N оценка всегда достижима.

В ближайшее время постараюсь выложить доказательство оценки. Внимание с Вашей стороны может ускорить эту процедуру. ;)

Posted by

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

Posted by

доказать, что не существует стратегии, дающей бОльшую вероятность

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

Posted by

не заметила слово оптимальна - отвлеклась на жирный шрифт - да, конечно:)

Posted by

http://janatem.livejournal.com/49076.html

Posted by

Ой, только что заметила, что Вы со мной не дружите :(

Posted by

Да я дружу на самом деле, честно. Просто я уже не успеваю ленту читать, и добавлять в нее никого не могу — только лакуны больше будут. Но я зато читаю «налетами» — один журнал, все пропущенное. А Вас это очень огорчает?

Posted by

я только что это заметила, ещё не сформировала ощущений на тему :))))))) Я тут двухмесячный инфант - пока не понимаю что всё это значит :))))))

Posted by

autoench.livejournal.com

А можно френдов на группы разделять и читать по группам: почаще самых интересных, пореже остальных.

Posted by

Задачки оказались совсем простыми, но некоторое количество удовольствия удалось получить. ;)

Posted by

Как нет? Оптимальная стратегия всегда существует для любых подслучаев (только найти ее и доказать оптимальность бывает непросто).

Posted by