24 июн. 2012 г.

Маловероятное событие

Добрый день!

Можно потратить много денег, чтобы показать мне Филиппа Киркорова на лошади, поющего песню Сергея Шнурова «Ленинград» (вероятность того, что я окажусь в кафе именно тогда, когда местный телевизор исполнит это безумие, крайне мала, но ОНИ воспользовались своим шансом). А можно с весьма скромным бюджетом и совсем без лошади создать весёлый и просветительский клип «Грибок стопы» (угадайте, о чём), самый популярный комментарий к которому «I really do like this music, even don't knowing the text».

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

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

Стоп! Мы же не сравнили средний возраст нашей футбольной сборной, а также зарплату её тренера, с аналогичными характеристиками конкурентов! Гм... Ну не сравнили, ничего страшного. Может их всех вообще нет и не было никогда. Вернёмся лучше к задачке.

Все 100 мудрецов будут в этом испытании выстроены в колонну (каждый видит тех и только тех, кто стоит перед ним), и на головы им будут надеты шляпы одного из k>0 цветов (цвета шляп выбираются независимо и случайным образом). Каждый из мудрецов в колонне, начиная с последнего, должен будет либо назвать цвет своей шляпы, либо сказать «пас».

Мудрецы считаются прошедшими тест, если хотя бы один из них назовёт цвет верно и не будет никого, кто назвал цвет неверно.


Вопрос: как должны договориться мудрецы между собой до испытания, чтобы максимизировать вероятность успеха? И какова эта вероятность? Естественно, нельзя ориентироваться ни на какие дополнительные данные (высота голоса ранее ответивших, интервал времени перед ответом и т.д.), решаем честно :)

Для случая k=1 всё достаточно просто: если известно, что шляпы бывают только одного цвета, то именно его надо называть. С вероятностью 100% ответ будет правильным, поэтому мудрецы пройдут тест. Остаётся найти решение для случая k>1. Будьте осторожны, читая источник задачки, так как там в комментариях уже всё подсказано.

Чем мне нравится эта задача? А тем, что кажется, что она не имеет разумного решения. Судите сами: первый отвечающий (который видит перед собой 99 шляп) ничего не знает о цвете своей шляпы. Поэтому он, не имея права назвать какой-то цвет (если назовёт, то с вероятностью 1-1/k все проиграют), вынужден сказать «пас». Но у второго совершенно такая же ситуация: он видит перед собой 98 шляп, он заранее знал, что первый скажет «пас», поэтому он тоже вынужден говорить «пас». И так далее. Возникает иллюзия, что выиграть невозможно. И тем интереснее догадаться, как же действовать мудрецам.

И ещё одна мысль на сегодня: раньше, объясняя метод математической индукции, я часто показывал задачку о триминошках (и её изящное решение). Обычно такого типа задачка гораздо лучше проясняет ситуацию для ученика. Во всяком случае, это всё куда нагляднее, чем стандартные задачки на делимость (главное, не слишком сбить с толку задачкой о лошадях). Если вам близка эта тема, то рекомендую заметку про Ханойскую башню (там в комментариях полезное дополнение к основному тексту).

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

Хорошего дня!

55 комментариев:

  1. Анонимный24.06.2012, 14:19

    Здравствуйте. Есть вопрос по условию: мудрецы заранее знают k, и заранее могут договориться о стратегии?

    ОтветитьУдалить
    Ответы
    1. Да, условие (включая k) они заранее знают полностью. Они не знают только одну мелочь - на кого шляпу какого цвета наденут.

      Удалить
  2. Анонимный24.06.2012, 15:35

    Читал о задаче в «Астровитянке». Там k=2.
    «— Нашла, нашла! Смотри — присваиваем красному колпаку значение единицы, а синему — двойки. Последний мудрец смотрит на колпаки впереди стоящих товарищей по несчастью и складывает все эти цифры. Получает число — чётное или нечётное. Если чётное — он отвечает на вопрос палача «синий», если нечётное — «красный». Ему может повезти, и этот цвет совпадёт с его колпаком, тогда он останется жив. Когда палач переходит к следующему мудрецу, тот уже знает ответ первого, подсчитывает сумму цифр по передним колпакам и если получает число той же чётности, то это означает, что его колпак — синий. Если чётность чисел не совпадает, то его колпак — красный. Так поступает каждый мудрец — зная ответ сзади стоящего и видя колпаки впереди стоящих, он вычисляет цвет своего колпака»

    ОтветитьУдалить
    Ответы
    1. Анонимный24.06.2012, 15:55

      В вашей стратегии шанс выжить – 1/k. С таким же успехом все могут говорить "пас", и лишь один наугад назовет какой-то из цветов перед ним.

      Удалить
    2. Анонимный24.06.2012, 16:09

      Нет, в "Астровитянке" другая задача. Там она гораздо проще.

      Удалить
    3. Можно попробовать докрутить задачу из "Астровитянки" до указанной в данном блоге:
      Note: Проверка на четность - по сути остаток суммы от деления на k (только легче оперировать числами 0 и 1, вместо 1 и 2)
      Итого:
      * ставим цвету в соответствие число от 0 до k-1.
      * суммируем и получаем остаток от деления на k - число от 0 до k-1
      * переводим полученный остаток в цвет.
      * поскольку мы заведомо имеем спасительное "пас" - можно один из потенциальных остатков закодировать именно словом "пас".

      Вероятность выиграть:
      1/k (вероятность выпадения остатка, который закодирован словом "пас")
      + (k-1)*1/k*1/k (вероятность совпадения цвета остатка и цвета шапки первого мудреца)
      = (2*k-1)/k^2

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

      Удалить
    4. Анонимный24.06.2012, 19:51

      Но как же так? Ведь в этой задаче игрокам нельзя ошибаться (если хоть один назовёт неправильный цвет, то все проиграют), а в задаче из Астровитянки "каждый за себя".

      Удалить
  3. Если k и сами цвета известны и каждого цвета не менее 1 шапки, то можно действовать так:
    Первый из отвечающих, кто видит не все цвета называет отсутствующий цвет, остальные пасуют.
    Цвет он назовёт верный, так как до него все пасовали, значит видели все цвета, а раз он видит не все, значит недостающий у него на голове.
    После верного ответа вполне логично молчать (пасовать) чтобы всё не испортить.

    ОтветитьУдалить
    Ответы
    1. Анонимный24.06.2012, 16:31

      Кстати, эту модификацию можно расширить до исходной задачи. Надо всего лишь рассчитать, с какой вероятностью в наборе из 100 шапок будет представлен каждый из k цветов. Всего вариантов Q=k^100. А вариантов с меньшим количеством цветов W=(k-1)^100 + (k-2)^100 + (k-3)^100 + ...

      Значит, W/Q - это вероятность того, что будут представлены все цвета, что равно вероятности победы.

      Удалить
    2. Анонимный24.06.2012, 16:49

      Упс, 1-W/Q - это искомая вероятность. В остальном вроде правильно посчитал :-)

      Удалить
    3. Но ведь сказано, что цвет шляпы для какждого игрока выбираются НЕЗАВМИСИМО, и при этои совсем не обязательно появятся ВСЕ возможные цвета.

      А насчёт варианта, указанного анонимом никак не доказывается, что полученная им вероятность больше 1/К. Может, она даже меньше! Например, если возможных цветов больше 100, то всех уж точно не будет.

      Удалить
    4. Уважаемый аноним, насколько я понимаю, Вы не очень аккуратно посчитали W.
      (k-1)^100 - это количество способов, которыми можно надеть на 100 мудрецов набор из (k-1) шляпы заданных цветов. Но ведь таких наборов k штук (мы можем выбрать отсутствующий цвет k способами). Поэтому первое слагаемое должно быть k * (k-1)^100.

      Аналогично, второе слагаемое k*(k-1)/2 * (k-2)^100
      И так далее.

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

      Кстати, Вы правы, если k превышает 100 (или даже просто достаточно близко к 100), то вероятность победы мудрецов заметно снижается. Но и тут есть за что бороться. Выигрывать с вероятностью 1/k - это слабый результат. Надо улучшать :)

      Удалить
    5. 1) Даже если эта вероятность "достаточна" (это для Вас сколько?), аноним этого не доказал. Кроме того, не сказано, что делать, если последний мудрец видит, что всех К цветов заведомо нет.

      2) Однако, приведённая анонимом стратегия в этом случае заведомо не годится.

      Удалить
    6. З.Ы. Забыла упомянуть ещё вот что: из того, что цвета выбираются случайным образом, ещё не следует, что они равновероятны. Ведь в условии же не сказано, как именно султан получает случайные числа. Может, он на каждого мудреца несколько раз бросает монетку и, если орёл выпадает при первом броске, записывает первый цвет (после чего переходит к выбору для следующей шляпы), если при втором -- записывет второй цвет, и так далее. Думаю, что если последний мудрец назовёт цвет, то лучше ему выбирать тот, которого он видит больше.

      Удалить
    7. > Однако, приведённая анонимом стратегия в этом случае заведомо не годится.
      Насколько я понимаю, его план таков: если не все цвета использованы, то проиграть с вероятностью 1/k (назвав случайный), а если все разные, то проиграть выиграть с вероятностью 100%.
      Для, например, k=8 это позволяет проигрывать с вероятностью ~10^-5. На мой взгляд, это уже неплохой результат (гораздо лучше, чем с вероятностью 7/8). Но его можно улучшить (что сделал asd, получив вероятность проигрыша ~10^-6 для k=8).

      Другими словами, слова "стратегия заведомо не годится" не очень точны. Стратегия срабатывает в большинстве случаев, но с какой-то вероятностью будет ситуация, в которой мудрецы проиграют, если будут пользоваться этой стратегией.

      > з того, что цвета выбираются случайным образом, ещё не следует, что они равновероятны
      Хорошее замечание! Обычно в подобных задачах фразу о том, что что-то выбирается случайно, следует понимать, как "все возможные исходы равновероятны" (по причине симметричности ситуации). Но для аккуратности мне следовало, конечно, написать это в условии задачи. Если у кого-то ещё возникнет подобный вопрос, то я поправлю заметку.

      > Думаю, что если последний мудрец назовёт цвет, то лучше ему выбирать тот, которого он видит больше.
      Да, это хорошее статистическое соображение. Но тут тоже понятно, что если коварный султан знает об этой хитрости мудрецов (или догадался, что они могут воспользоваться такой хитростью, чтобы повысить свои шансы), то он может надеть на последнего мудреца шапку, цвет которой встречается реже, чем цвета всех остальных видимых им шапок (т.е. султан может скорректировать свой "случайный алгоритм" так, чтобы повысить вероятность такого расклада). И тут уже оказывается, что мудрецам выгоднее не хитрить, а честно выбирать один из равновероятных цветов (это как в обобщении задачи Монти-Холла).

      Удалить
    8. 1) Но ведь в условии же не сказано, что К -- это именно восемь. И даже не сказано, что К<100. А при К>=100 всех цветов заведомо никто видеть не будет, и стратегия анонима не годится. Хотя, интуитивно, конечно, представляется, что К<100, иначе придётся брать настолько близкие цвета, что мудрецы перестанут их различать.

      2) А, может, не надо править? Мне кажется, я придумала две стратегии, при которых если цвета не равновероятны, то мудрецам это только выгодно, и которые дают вероятность выигрыша больше 1/К даже при К>100. (Правда, чему конкретно равна эта вероятность, я посчитать не могу)

      а) Последний мудрец говорит "пас", если видит хотя бы одну пару шляп одного цвета рядом. Если для следующего мудреца верно то же самое, он тоже говорит "пас", иначе называет цвет шляпы перед ним, и так далее.

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

      3)ПО УСЛОВИЮ, цвета шляп выбираются НЕЗАВИСИМО и случайным образом, а если султан специально наденет на последнего мудреца шапку, цвет которой встречается реже, чем цвета всех остальных видимых им шапок, это будет уже не так. Поэтому я, как и все остальные комментаторы, такой вариант не рассматривала. Разумеется, если султан нечестен и будет знать стратегию мудрецов, он всегда может выбрать невыгодную для них комбинацию.

      Удалить
    9. Да, я Вас неправильно понял, видимо. Конечно, если k>100, то заведомо не все цвета на головах, поэтому предложенная анонимом стратегия не сможет работать. Но я знаю стратегию, которая позволяет для, например, k=200 выигрывать с вероятностью ~40% (что гораздо лучше 1/k = 0.5%). Насколько я понимаю, Ваши интересные стратегии являются усложнениями моей (при этом ещё и снижается вероятность победы).

      Да, Вы правы, так как цвета шляп выбираются независимо, то описанный мною финт невозможен :)

      Удалить
    10. Я не знаю, какую стратегию Вы имели в виду под "Вашей", и сказать о ней ничего не могу.

      Но при моей стратегии а) вероятность, что последний мудрец увидит невыгодную комбинацию равна [(К-1)/К]^98. Я не могу посчитать эту цифру, но что она меньше (К-1)/К, это уж точно. Кроме того, стратегия анонима заведомо хуже при всех К>2 (а при К=2 равноценна): у него шансов явно меньше, чем при ставке на повтор первого цвета (поскольку одну заданную пару получить вероятнее, чем К-1), а у меня столько же.

      А вот как сравнить с другими стратегию б) я придумать не могу. Мне понятно, что при К=2 она менее выгодна, чем другие, но дальше непонятно.

      Удалить
    11. Кстати, никто не запрещает комбинировать стратегии (договориться, что при k < 4 действуем таким-то образом, при k < 19 секим-то, а при остальных k - третьим способом). Считаем, что игроки, стоящие в колонне, знают k.

      Удалить
  4. Анонимный24.06.2012, 19:21

    Для к=2 мудрецы пасуют пока перед каким-то не останутся только колпаки цвета(одного цвета пусть он будет 1) 1. Он объявляет 2. Если бы на нем был 1 предыдущий назвал бы 2. Если был пас значит предыдущий видел 2 разных цвета, а он видит только один значит второй цвект на нем.
    Последующие пасуют чтобы ничего не испортить.

    Для трех цветов тоже самое но пасуют только те кто видит все три цвета. Кто видит два называет третий.

    ОтветитьУдалить
    Ответы
    1. Анонимный24.06.2012, 19:23

      Далее по индукции, называть должен тот кто видит к-1 цветов

      Удалить
    2. Да, выше уже было такое решение. Можно ли его улучшить?

      Удалить
    3. Анонимный25.06.2012, 09:30

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

      Удалить
    4. Интереснее было бы увеличить вероятность того, что мудрецы выиграют.
      Т.е. хотелось бы так улучшить алгоритм, чтобы в условиях, когда не все k цветов встречаются на шляпах мудрецов, вероятность их победы была больше 1/k.

      Удалить
    5. Анонимный25.06.2012, 10:49

      В общем случае если первый мудрец видит N< К цветов он называет один из k-n. Что в худшем случае дает 1/к-1, что уже лучше 1/к. Можно ли еще улучшить?

      Удалить
  5. Если вижу первый цвет, пасую, иначе называю первый цвет. Выигрываем тогда и только тогда, когда у кого-то есть первый цвет, то есть с вероятностью 1-((k-1)/k)^n. Не знаю, можно ли лучше, но здорово, что вообще можно лучше 1/k.

    ОтветитьУдалить
    Ответы
    1. Анонимный25.06.2012, 13:51

      Вот это похоже на правильный ответ

      Удалить
    2. Да, здорово. Но можно ли лучше? ;)

      Удалить
    3. Можно завязатся не на первый цвет, а на повтор цвета последнего мудреца (того, которого все видят). Т.е. все пасуют до тех пор пока видят две шапки одного цвета - на последнем и на i-том. Соответственно i-тый назовёт цвет шляпы последнего мудреца.

      Удалить
  6. Первое что приходит в голову - вести бинарную функцию от параметров A1, A2,..., AK, где Ai - это количество шляп i-ого цвета, которые видит перед собой мудрец. Если результат функции 0, то нужно говорить "пас", иначе - назвать цвет. При этом если очередь дошла до мудреца, у которого функция даёт 1 - он может сделать вывод: если на единицу увеличить параметр, соответствующий цвету его собственной шляпы, то функция даст 0, т.к. предыдущий сказал "пас". Если таких цветов больше одного - он говорит "пас", но надеемся, что рано или поздно найдётся мудрец, для которого вывод насчёт цвета однозначен, засчёт использованя того факта, что для предыдущего он был неоднозначен... надеюсь что-то понятно из такого объяснения.

    В качестве функции можно использовать например F(...) = (A1*A2*A3*...*AK == 0). Иначе говоря: 0 - если перед мудрецом видны шляпы всех K цветов, и 1 - если хотя бы какого-то цвета не хватает. Тот для кого условие даст 1 (а оно точно будет таким для того, перед кем стоит меньше К мудрецов) делает вывод, что у него шляпа недостающего цвета. Если цветов больше, чем мудрецов - первому же говорящему только и остаётся что назвать любой цвет, которого он не видит перед собой.

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

    ОтветитьУдалить
    Ответы
    1. Это совсем не вариант, так как противоречит условию задачи. Мы же договорились, что нельзя ориентироваться ни на какие дополнительные данные (высота голоса ранее ответивших, интервал времени перед ответом и т.д.), решаем честно :)
      Временным интервалом можно закодировать координаты всех атомов в мире, а не только какие-то цвета шляп. Поэтому такое читерство не может быть интересным.

      Удалить
    2. Сорри :) Этот абзац почему-то сразу не увидел

      Удалить
  8. Улучшить результат для k < 100 можно так:
    смотреть на первого, если видишь что его цвет повторяется - пас, иначе - называешь его цвет.

    Тогда хороших случаев будет будет тот в котором цвет первого есть ещё хотя бы у одного.

    Это сработает для того случая когда использованы не все цвета.
    Таких случаев больше чем случаи когда обязательно использованы все.

    ОтветитьУдалить
  9. Есть такой вариант:
    Нумеруем цвета.
    Хорошей называем ситуацию, если есть мудрец у которого номер цвета шапки совпадает с его порядковым номером (по модулю к).
    Алгоритм: пока видим хорошую ситуацию - пасуем, как только очередной мудрец хорошей ситуации не видит - называет цвет, соответствующий его номеру. Проиграем только если хорошей ситуации изначально в построении нет.
    Таким образом шанс на удачу: Q = 1 - ((k-1)/k)^100
    Что даёт хороший результат на малых k: http://www.wolframalpha.com/input/?i=plot+y+%3D+1+-+%28%28x-1%29%2Fx%29%5E100%2C+x+from+1+to+300

    Для интереса сравним с пресловутым 1/k:
    Q - 1/k = 1 - ((k-1)/k)^100 - 1/k = {k^100 - (k-1)^100 - k^99}/k^100 = {(k-1)*k^99 - (k-1)^100} / k^100 = (k-1) * (k^99-(k-1)^99) / k^100, что >0 при k>1.
    Таким образом Q>1/k, т.е. наша стратегия всегда лучше случайного выбора, что уже неплохо.

    ОтветитьУдалить
    Ответы
    1. Без редактора формул некрасиво входит. :-(
      Ну и ссылку забыл выделить.

      Удалить
    2. Анонимный26.06.2012, 09:48

      Уважаемый LisandreL
      В Ваших выкладках содержится ошибка. Проверяем для простого случая когда k=2

      Рассмотрим какие цвета шляп могут быть у мудрецов 99 и 100 (КРА и СИН это цвета шляп). Третья колонка - это то что сказал мудрец номер 100 (который говорит первым). Четвертая колонка - результаты по итогам того что сказал мудрец номер 100. Плюс - результат не ухудшен, минус - сотый мудрец наступил на мину.
      Пусть хорошая ситуация, когда СИН совпадает с нечетом, а КРА четом

      099 100 SAY RES
      СИН СИН ПАС +
      СИН КРА ПАС +
      КРА СИН КРА -
      КРА КРА КРА +

      Поскольку все 4 варинта равновероятны, то вероятность наступить на мину в первом же шаге равна 1/4. Даже если дальше всё пройдет гладко, то вероятность выиграть по вашему алгоритму не выше 3/4, что не совпадает с Вашей формулой для Q при k=2.

      Хотя конечно это намного выше чем 1/2.

      Удалить
    3. Видимо, анонимный не очень вчитался в условие задачи, поэтому неправильно проверил решение LisandreL.

      Кстати, по поводу этого решения возникает вопрос: можно ли доказать (и если да, то как это сделать), что не существует более эффективной стратегии?

      Удалить
    4. вероятность не отличається от версии asd (24.06.12, 19:23) Если вижу первый цвет, пасую, иначе называю первый цвет.
      Это даст туже вероятность, только нужно добавить поправку для первого мудрица. Он всегда называэт первый цвет. Эсли все видят у первого мудреца шляпу первого цвета - все пасуют.

      Можна перефразировать:
      Хорошей называем ситуацию, если первый мудрец имеет шапку первого цвета или есть мудрец у которого цвет шапки совпадает с цветом шапки первого мудреца.
      Алгоритм: пока видим хорошую ситуацию - пасуем, как только очередной мудрец хорошей ситуации не видит - называет цвет шапки первого мудреца. Проиграем только если хорошей ситуации изначально в построении нет.

      Аналогично можна завязаться на повторение цвета.

      Все случаи дают одинаковую вероятность победы.

      Удалить
    5. Анонимный26.06.2012, 14:48

      Нет, я невнимательно вчитался в решение LisandreL. Речь там оказывается шла о том, что если впереди есть ХОТЯБЫ один мудрец с совпадением его номера и номера цвета, а не о мудреце, стоящем непосредственно перед говорящим.

      Теперь всё понятно. Решение гуд.

      Удалить
  10. Наглядное сравнение шансов нашего алгоритма и случайного выбора.

    ОтветитьУдалить
  11. Анонимный26.06.2012, 08:48

    Стратегия на вскидку. Извините если уже была озвучена, долго вчитываться в переписку нет времени.

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

    2. Следовательно следующий "голосующий" мудрец обязан попасть в яблочко на основе информации, переданной ему от первого "голосующего" мудреца.
    Определение: "голосующий" мудрец - это тот, кто скажет любое слово кроме "пас".

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


    Под данную стратегию можно разработать несколько тактик. Причем скорее всего для разных K будет своя наиболее оптимальная тактика, например когда K "очень мало" или для "очень больших K".

    ОтветитьУдалить
    Ответы
    1. По вашей стратегии первый голосующий уже снизил шанс на удачу до 1/k.
      2 мудрецам отвечать вообще нету смысла - если первый ответил правильно, то они уже победили, если неправильно, то уже проиграли, так что ответ второго может повлиять на результат только в одном случае, если первый угадал, а второй ошибся и всё завалил.

      Удалить
    2. Анонимный26.06.2012, 09:57

      ---По вашей стратегии первый голосующий уже снизил шанс на удачу до 1/k.

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

      Удалить
    3. Анонимный26.06.2012, 10:24

      --- 2 мудрецам отвечать вообще нету смысла

      Согласен, надо будет потом переосмыслить.

      Удалить
  12. О, доказал оптимальность решения с 1-((k-1)/k)^n (n=100). По крайней мере среди детерминированных стратегий. Оказывается, все просто. Осторожно, спойлер.

    Рассмотрим стратегию чувака, отвечающего последним. Если все до него сказали "пас", у него нет никакой дополнительной информации, чтобы решить, что назвать (ведь он никого не видит). Значит нужно заранее договориться, какой конкретно цвет ему выбирать в этой ситуации. Назовем этот цвет x[1]. Предпоследний отвечающий чувак видит цвет последнего. Ясно, что если этот цвет равен x[1], то выгодно сказать "пас", потому что тогда первый ответит правильно, и мы выиграем. Иначе оказываемся в той же ситуации, что и раньше: надо называть цвет, а информации нет, значит надо называть фиксированный цвет, пусть x[2]. Аналогичные рассуждения можно по индукции провести для всех остальных, построив произвольную последовательность x[i], i=1..n. Показать, что от выбора иксов ничего не зависит, и получается та самая стратегия (что моя, что LisandreL) и те самые 1-((k-1)/k)^n.

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

    ОтветитьУдалить
  13. если что, я не читал предыдущие комменты, может уже ответили
    если k <= 100 и мудрецы знают, что это за k, то:

    последний из них смотрит, сколько РАЗНЫХ шляп на предыдущих.
    если их k, он пасует
    если их k-1, он говорит, что на нем цвет #k

    если он пасует, последним становится тот, кто был перед ним
    вероятность выиграть - 100% (ну, или я облажался)



    если k > 100, что им делать, пока не знаю

    ОтветитьУдалить
    Ответы
    1. ---вероятность выиграть - 100%
      Если я правильно понял условие, то не факт, что все k цветов будут в выборке. Например, есть 90 цветов. Но некоторые повторяются по 2-3 раза, а некоторых вообще нет. Это снижает вероятность победы.

      Удалить
    2. Конечно, не факт, что все k цветов будут в выборке. Поэтому вероятность победы здесь равна вероятности того, что все k цветов окажутся на головах мудрецов. Осталось сравнить эту вероятность с вероятностями победы при других стратегиях.

      Удалить
  14. Анонимный27.06.2012, 12:40

    По условию задачи "султан решил устроить им еще одно испытание...". Следовательно султан не решал устраивать 100% казнь, т.е. он не будет организовывать специальную подставу. Вернее сказать так:

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

    Исходя из этого наши мудрецы могут спокойно себе считать что они 100% останутся в живых в случае если они докажут себе что их стратегия является наиболее оптимальной.

    Вот такой вот житейский ответ на вопрос "Можно ли его улучшить?"

    ОтветитьУдалить
    Ответы
    1. Ваши рассуждения полностью перечёркивает фраза из условия: «цвета шляп выбираются независимо и случайным образом», т.е. на выборку султан не влияет.

      Удалить
    2. Ну и к тому же про казнь при неудаче в условии ЭТОЙ задачи ничего не сказано.

      Удалить
    3. Для разных оптимальных стратегий выигрышны разные комбинации шляп. Именно, для любой комбинации шляп есть оптимальная (в смысле исходной вероятностной задачи) стратегия, проигрывающая при выпадении такой комбинации.

      Удалить
    4. Анонимный27.06.2012, 17:01

      "цвета шляп выбираются независимо и случайным образом"
      Не думаю что султан станет заниматься подбрасыванием монеты 100 раз. Это фраза скорее дана для определенности, чтобы не было утомительных расспросов. Поскольку султан ответ знает, то ему легко назначить тестовую выборку.

      "Ну и к тому же про казнь...". Замените слово "казнь" на "немилость" или "общественное ФУУУ" или "лишение стипендии". Какието санкции или мотивация должны же быть, иначе ради чего мудрецам приседать вообще.

      Удалить
    5. Анонимный27.06.2012, 17:09

      "Именно, для любой комбинации шляп есть оптимальная стратегия, проигрывающая при выпадении такой комбинации."

      Как говорится, "Переведи" ((с) Москва слезам не верит), мы что, стремимся проиграть наиболее оптимальным образом????????

      Удалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний