10 февр. 2020 г.

Математики договорятся

Добрый день!

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

Вы слышали про Форт Боярд Математиков? Пару недель назад у них была интересная задачка про бесконечную последовательность бросков честной монетки, которую разделили на чётные и нечётные броски, причём каждую из этих подпоследовательностей сообщили чётному и нечётному математику, сидящим в разных подземельях. Каждый математик должен назвать номер броска в последовательности своего товарища по несчастью, чтобы сравнить соответствующие результаты бросков. Цель математиков — так заранее договориться, чтобы результат броска в последовательности первого под номером, который назвал второй математик, совпал с результатом броска в последовательности второго под номером, который назвал первый. Как выигрывать чаще, чем в половине случаев? Какова вероятность их победы, если они хорошо предварительно подумали?

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

Итак, два математика сидят в разных подземельях. Каждому из них завтра утром принесут честную монетку, каждый из них подбросит её, а потом сообщит своё предположение о результате броска своего товарища по несчастью. Если хотя бы один из них угадает, то они выиграли. Понятно, что им легко выигрывать в 75% случаев, давая случайные ответы. Но они прямо сейчас могут договориться о более умной игре. С какой вероятностью они будут выигрывать, если хорошо подумают?

Прелесть задачи в том, что она кажется неразрешимой. В самом деле, первый математик ничего не знает о результате броска второго, а второй — о результате первого. Поэтому может показаться, что самое умное — всегда говорить, что у коллеги выпал, например, орёл. Тогда в трёх ситуациях из четырёх (ОО, ОР, РО) у них будет гарантированная победа, а лишь в одной (РР) — не менее гарантированное поражение.

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

Дополнение: в следующей заметке мы начали разбор этой задачки.

Хорошей недели!

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

  1. Анонимный10.02.2020, 10:22

    Пусть первый всегда называет орла, а второй решку. Тогда во всех четырех элементарных исходах ОО/ОР/РР/РО им гарантируется больший шанс, чем если оба скажут орел.

    ОтветитьУдалить
    Ответы
    1. Не совсем так. В вариантах (ОО, РО, РР) они выигрывают, но в (ОР) оба их утверждения оказываются ложными. Получаем те же самые 75%. Здесь тоже простое решение предполагается, но всё же чуть-чуть интереснее.

      Удалить
  2. Пусть один математик считает что их результаты совпали, а второй что не совпали.

    ОтветитьУдалить
    Ответы
    1. Да, конечно! Умеете объяснить, как придумали такое решение?

      Удалить
    2. Анонимный10.02.2020, 13:07

      Да, вы правы, а я неправильно понял формулировку "хотя бы один".

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

      Удалить
  3. Анонимный10.02.2020, 12:59

    Если и монетки, и броски - честные (про броски ничего не сказано, но иначе легко можно "переподбрасывать" при неправильном результате), то по теории любая подпоследовательность случайной последовательности или ее инвертирование другой случайной последовательностью - также случайная последовательность. Единственная возможность превзойти 75% - передавать информацию о своем броске после того, как он совершен, но до того, как второй математик даст ответ. Формулировка задачи позволяет менять последовательность бросков и сообщений: первый бросает, называет второму под видом предположения о его будущем броске свой нынешний результат, чтобы второй знал ответ до того, как будет высказывать свое предположение, и только потом второй бросает монетку.

    ОтветитьУдалить
  4. Анонимный10.02.2020, 16:39

    Первый математик всегда говорит тот же результат, что выпал у него, второй математик — всегда противоположный. Тогда один из них точно окажется прав.

    ОтветитьУдалить

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

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



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

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