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

Добрый день!

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

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

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

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



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

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

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

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

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

Добрый день!

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

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

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

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

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

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

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

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

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

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

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

Добрый день!

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

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

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

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

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

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

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

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

Статистика по излечившимся и детские задачки

Добрый день!

Давненько мы задачек не решали! Сегодня будет целых две: про симметричные даты и про мудрецов. Но сперва короткий вопрос о подаче информации.

1) Не имея медицинского образования, легко задавать глупые вопросы. Например, почему редко публикуется информация о поправившихся после диагноза коронавирус? В англоязычном интернете почему-то про это вообще почти нигде не пишут. Или я не там смотрю? Почему-то везде только следующая статистика о 2019-nCoV: infected, death и fatality. Причём последнее, на мой неквалифицированный взгляд, посчитать из первых двух чисел невозможно, но это зачем-то всюду делают.

На русском изредка публикуют переводы с китайского (см. примеры табло или отчёт о 632 вылеченных). Например, на табло сейчас видно, что количество выздоровевших за сутки почти в три раза превышает количество умерших.

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

2) Позавчера Константин Кноп поделился следующей короткой задачкой, которая, по-моему, хорошо подходит для обсуждения с детьми по дороге домой и аналогичного доброго времяпрепровождения:

«Задача про 02.02.2020

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

Бонус-вопрос - когда была последняя такая дата до наступления нынешнего столетия?»

Есть идеи?

3) Кстати, про красивые даты — тот же Константин перепечатал забавные факты про число 2020 из Facebook Euclidea (пару лет назад мы с вами обсуждали построения циркулем и линейкой, а потом ещё и Пифагорию).

Ниже пример из той записи — пояснение про совпадение 2020-х цифр в десятичной записи трёх интересных констант:

«The 2020th decimal digits of constants π, e and φ are the same. By the way, this property is not so rare. The minimum such number is 12, the predecessor of 2020 is 1905, the next will be 2060.
3,141592653589 ... 12694683 ...
2,718281828459 ... 82922443 ...
1,618033988749 ... 43062623 ...»

4) Но вернёмся к детским задачкам. Одно дело — просто хорошая задачка, которая полезна ребёнку для разгрызания и обдумывания. А другое — приятная задачка, которую дети придумали сами. Представляете, какую пользу они получили, когда исследовали наборы чисел, пока не нашли интересное сочетание! В комментариях к одной записи Константина мне понравилась следующая формулировка, в частности, из-за вклада школьников:

«Задачу сочинили на Ринруте-2019 три Новосибирских пятиклассника, Горелова Аня, Шевченко Роза и Степанов Ярослав из команды Зинцовой Анастасии Сергеевны. Пришлось немного ее литературно обработать.

Мудрецы
Король Артур задумал натуральное число N и разбил его на три различных натуральных возрастающих слагаемых: N=n1+n2+n3, n1<n2<n3. Затем он вызвал к себе трех мудрецов и вручил каждому из них по конверту с одним из загаданных чисел: младшему n1, среднему n2, а старшему n3. Само число N он тоже озвучил и заявил: “Тот из вас, кто сумеет понять, какие числа у товарищей, будет объявлен ГЛАВНЫМ научным мудрецом.” Средний и старший лихорадочно вскрыли конверты, но не смогли сразу ответить Артуру, а младший после этого заявил: ”Мне не требуется вскрывать конверт, я знаю ваши числа!”
Сможете назвать число N, пользуясь приведенной информацией?»

Понятно, что «сразу» — ключевое слово в условии. Надо понимать, что средний и старший не могли успеть учесть замешательство друг друга (тут уместно вспомнить задачку про остров Беззеркалья, где у всех время подумать было). Сможете придумать решение?

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