19 февр. 2020 г.

Бесконечная последовательность бросков

Добрый день!

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

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

Разных таких функций может быть очень много, поэтому давайте временно упростим игру — пусть наши математики смотрят только на результат первого броска, а всю остальную последовательность игнорируют. Соответственно, имея на входе только один бит (будем обозначать буквами O и R от слов obverse и reverse), он будет называть число, задаваемое одним битом (мы считаем, что последовательность начинается с 1, поэтому на выходе у функций математиков будет 1 или 2).

Пусть, например, первый математик, увидев результат первого броска «O», всегда называет индекс 1, а увидев «R» — отвечает 2. А второй математик пусть действует наоборот. Ниже приведены две таблицы для всех возможных 16 входных состояний, названные индексы обоих математиков (выделено жирным), а также результаты броска другого математика по названному индексу.



А в нижней таблице приводятся результаты сравнения этих бросков по названным индексам. Как видите, вероятность победы при таких функциях получилась меньше 50% (6/16=37.5%). Уже в этот момент нам должно стать странно, ведь совсем недавно было совершенно очевидно, что при любых договорённостях математики выигрывают с вероятностью 50% (мол, они ничего не знают про последовательности друг друга, поэтому могут называть любые индексы — как раз будут случайно совпадать в половине случаев). А тут вдруг они небольшим усилием смогли выигрывать реже, чем при назывании случайных индексов. Как так?

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

Если вы хотите ещё почитать о том, как считать вероятности, то предлагаю вспомнить разбор другой задачки о бросках монетки (вопрос был в том, проще выиграть три раза из четырёх или пять раз из восьми). Там мы сперва перебирали на Javascript, а потом аккуратно всё проверили. Самое ценное в той заметке в комментариях, как обычно.

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

4 комментария:

  1. Порекомендую ещё один материал играх с монетками - http://kvant.mccme.ru/1987/05/luchshee_pari_dlya_prostakov.htm (статья "Пари для простаков" из 5 номера за 1987 год Научно-популярного физико-математического журнала "Квант"). Вспомнилась она из-за похожих табличек 4х4.

    ОтветитьУдалить
  2. Анонимный19.02.2020, 17:44

    Разве честно давать задачи на компьютерный перебор? Это как играть в Что? Где? Когда? с интернетом. В задаче думать надо.

    ОтветитьУдалить
    Ответы
    1. Анонимный19.02.2020, 17:46

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

      Удалить
    2. В предыдущей задаче перебор был очень маленький. Достаточно было сделать одну-полторы итерации, чтобы всё почувствовать. Здесь то же самое - кто попытался сделать хоть что-то, тот нашёл способ выигрывать чаще, чем в 50% случаев. Если перебрать 5-7 конфигураций, то можно нащупать более эффективное решение.

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

      Кстати, ЧГК с доступом в интернет - не такое уж бесполезное дело. Искать в интернете тоже надо уметь.

      Удалить

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

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



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

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