14 февр. 2020 г.

Организуем перебор

Добрый день!

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

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

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

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

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

Осталось перечислить функции, которые переводят бит в бит:
1) О -> О, Р -> О (т.е. «всегда орёл»);
2) О -> Р, Р -> Р (т.е. «всегда решка»);
3) О -> О, Р -> Р (т.е. «не менять»);
4) О -> Р, Р -> О (т.е. «менять на противоположный»).
(возможно, в комментариях мы обсудим, какие ещё бывают функции, а также, почему мы их сейчас даже не упоминаем)

Соответственно, задача математиков — договориться, кто из них какую функцию применяет. А решающий эту задачку может прямо сейчас перебрать все 4x4=16 вариантов этих договорённостей. Что именно перебирать? Для всех 16 вариантов договорённостей математиков надо перебрать все 4 возможных результата бросков двух монет (ОО, ОР, РО, РР) — так мы узнаем, при каких правилах и сколько раз они выиграли. Например, в прошлой заметке мы показали, как выигрывать в 75% случаев.

Итого, имеем 16х4=64 варианта — не так много. Более того, в процессе перебора должна включиться интуиция, которая быстро его направит к решению. Зачем проделывать этот перебор? Чтобы решить куда более интересную задачку о половине бесконечной последовательности бросков, известной каждому из двух пойманных математиков.

Вы уже начали её исследовать?

Хороших выходных!

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

  1. Кстати, если уж говорить о переборе вариантов и подсчёте вероятностей, то можно вспомнить ещё эту старинную заметку - http://my-tribune.blogspot.com/2011/12/blog-post_18.html - тут и код программки приведён, и пояснения есть.

    ОтветитьУдалить
  2. В задаче про "чётного" и "нечётного" математика, где надо назвать номер в бесконечной последовательности Вы не сказали, считается ли тоже общей победой, если правильно назвал хотя бы один, или каждый играет за себя. Кроме того, не сказано, сообщают ли ли математикам результаты сравнений и можно ли называть один и тот же номер больше одного раза.

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

    ОтветитьУдалить
    Ответы
    1. Анонимный15.02.2020, 04:57

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

      Удалить
    2. user_ami, спасибо, что указали на возможную невнятность формулировки. Идея вот в чём: у одного игрока есть последовательность орлов и решек A, а у другого - B. Каждый из них анализирует свою последовательность, а потом сообщает индекс в последовательности второго (пусть это будут a и b). Далее организаторы мероприятия сравнивают A[b] и B[a] (т.е. b-ый элемент в последовательности A и a-ый элемент в последовательности B. Если оба эти элемента совпали, то оба математика победили, а в противном случае оба проиграли.

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

      Надеюсь, сейчас стало понятнее. Благодарю, что указали на сложности в понимании условия!

      Уважаемый аноним, спасибо, что процитировали условие!

      Теперь о том, каким боком этот текст к этой задаче: можно провести аналогичную работу (перебрать варианты). Надо только сперва понять, что именно перебирать. Через несколько дней мы это разберём подробнее.

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

    Ответ напишете?

    ОтветитьУдалить
    Ответы
    1. В предыдущей заметке был о несколько раз. См., например, https://my-tribune.blogspot.com/2020/02/two-cats.html?showComment=1581327009257#c7755332244749580832 (там даже есть пояснения, как к этому подойти). Но я убеждён, что прочитать ответ не так полезно, как найти решение.

      Удалить

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

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



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

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