19 февр. 2020 г.

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

Добрый день!

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

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

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

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



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

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

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

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

14 февр. 2020 г.

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

Добрый день!

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

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

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

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

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

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

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

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

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

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

10 февр. 2020 г.

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

Добрый день!

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

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

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

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

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

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

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

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

4 февр. 2020 г.

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

Добрый день!

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

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, пользуясь приведенной информацией?
»

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

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

24 янв. 2020 г.

О гладких и ступенчатых функциях

Добрый день!

Как известно, 2020 год объявлен годом гладких функций в России (к сожалению, нет). Конечно, мы не будем требовать непрерывности производных всех порядков, но хотя бы первый порядок же часто можно обеспечить.

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

О чём речь? Самый простой пример: в ближайшем ко мне продовольственном магазине при чеке выше 1000 рублей автоматически применяется скидка 15%. Хорошо? Да, наверное. Но если вдруг в корзине прямо сейчас товаров на 950 рублей, то выгоднее добавить какую-нибудь шоколадку за 50 р. (и тогда товаров будет на 1000 рублей, но со скидкой 15% получится 850 рублей (ситуация настолько банальная, что из этого хорошую задачку, наверное, придумать не удастся)). Мотивацию магазина я понимаю: он стимулирует покупать сразу много (не всегда нужного), разгружает кассы (очереди должны быть меньше, если люди реже ищут в кошельке карту/мелочь) и т.д., но комфорт человека страдает, по-моему.

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

Мне неприятно от того, что вокруг так много ступенчатых функций: в страховании, на таможне, в банках и т.д. Взять тот же автомобильный налог (ниже данные по легковым автомобилям в Московской области в 2019 году):
- До 100 лошадиных сил ставка 10 р. за каждую лошадь.
- От 100 до 150 лошадиных сил ставка 34 р. за каждую лошадь.
- От 150 до 200 лошадиных сил ставка 49 р. за каждую лошадь.
И т.д. К чему это приводит? Давайте сравним налог для автомобилей с мощностью двигателя 99-101, 149-151, 199-201 лошадиных сил. Получаем следующие суммы:
- 10*99 = 990 и 34*101 = 3434 рубля (разница в три раза из-за двух лошадиных сил),
- 34*149 = 5066 и 49*151 = 7399 рублей (отличие в полтора раза из-за тех же двух лошадиных сил),
- 49*199 = 9751 и 65*201 = 13065 рублей (то же самое).
А вокруг 250 л.с. прыжок ещё сильнее: с 75 до 150 рублей.

Коряво же! Рассказывать о том, что это не главная проблема, что это мелочи, что есть куча всего серьёзного, я и сам могу. Но ведь всё равно коряво! А ведь можно было сделать нормально: первые 100 лошадиных сил по 10 рублей, а следующие уже по 34, затем по 49 р., потом по 75 и так далее. Я понимаю, что это чуть сложнее считать будет. Но плюс в том, что совершенно уйдёт необходимость переживать о том, что написано в ПТС (99 или 101, например).

По-моему, так можно сделать почти всегда при вычислении суммы/налога/штрафа и т.д. Сейчас всюду компьютеры считают, поэтому выдумывать ничтожные упрощения считающему не надо, ведь это приводит к усложнениям у многих других. Допустим, банк берёт 1% за переводы в другие банки суммы до 100 т.р., но 2% за переводы свыше 100 т.р. Получается, что перевод 99 и 101 т.р. отличается по цене примерно в два раза. Ну нелогично же! Тут же тоже напрашивается правило «1% до 100 т.р., а оставшаяся сумма по 2%» (я не одобряю такие тарифы, привёл их для примера).

Вот если ситуация не предполагает гладкости (например, если законом запретили квадрокоптеры тяжелее 250 г., то логично, что тут же производители сделали устройства весом 249 г.), то не о чем и говорить. Или, например, с льготами/доплатами при разном количестве детей тоже понятно — тут явная ступенчатая функция без вариантов. Но в остальных-то ситуациях можно добавить гладкости, чтобы не спотыкаться зря на ступеньках.

Надеюсь, вы хорошо повидались с близкими в новогодние праздники! Здоровья вам, родным и друзьям!

И хорошего завершения недели!

27 дек. 2019 г.

Вижу рифмы и Сакирмахрепяка

Добрый день!

В начале года вы подсказали мне название жанра «Вижу рифмы», а заодно вспомнили про древнее искусство составления вывесок «Сакирмахрепяка», чтобы уже сейчас мы вместе могли посмотреть на прекрасный пример синтеза:



Вот как они это делают?!

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

Другой пример применения пристального взгляда, который мне тоже нравится полноценным использованием особенностей вёрстки:

ама с апой купили для сына Две раскраски и пачку красителей Но был недоволен подарком детина - Он швырнул свой набор в одителей

А какие примеры талантливого совмещения разнородных сущностный недавно попадались вам? И вообще, что вас недавно порадовало? Какие подборки фильтрованного юмора вы знаете? Скажем, у sly2m неплохие подборки, так как там всего половину я бы предпочёл пропустить. Примеры удачного:

- Что ты больше любишь, меня или суп?
- Первое...

Курить по 3 пачки в день – это трудный путь, но разве нам нужны легкие?

На следующий день после ограбления банка грабители получили смс с условиями оформленного кредита.

На выборах 2020 в США будет решаться важнейший вопрос, кто победит: русские хакеры или китайские?

Горбатый:
— Зато мне удобно носки одевать.
Могила:
— Надевать.

Актеры в советских фильмах с каждым годом играют все лучше.

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

Идёт Будда с учениками по дороге. Видит: яма, в ней вол, крестьянин пытается его вытянуть, но сил не хватает. Будда кивнул ученикам, они быстро помогли вытянуть животное. Идут дальше, снова яма, в ней вол, на краю сидит крестьянин и горько плачет. Будда прошёл мимо и как бы не заметил. Ученики его спрашивают:
- Учитель, почему ты не захотел помочь этому крестьянину?
- Помочь плакать?

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

Решение всех проблем сразу одной кнопкой: «Отметить всё как прочитанное».

Приходит мужик к адвокату и просит совета.
- Мой сосед должен мне пятьсот долларов, и не отдаёт. Могу я как-нибудь отсудить эти деньги у него?
- Можете, но для этого нужно письменное доказательство, что он вам должен. У вас есть такое доказательство?
- Боюсь, что нет. Он у меня просто так взял.
- Тогда напишите ему письмо, и потребуйте в этом письме, чтобы он немедленно вернул вам тысячу долларов.
- Но он мне должен только пятьсот долларов!
- Именно так он и ответит. И это будет письменное доказательство.

Счастливые люди думают о том, что у них есть, а несчастные — о том, чего у них нет.


Понятно, что собирать что-то подобное сложно (когда-то и я пробовал), но не менее понятно, что вам иногда что-то удачное попадается. Поделитесь, пожалуйста, в комментариях!

А я напоследок покажу ещё одну цитату:

Однажды добрая фея явилась к галерному рабу и спросила:
- Какое твоё самое заветное желание? Я могу исполнить что угодно!
- Хочу кандалы из чистого золота!- немедленно воскликнул раб.

(источник)

И опробуйте, пожалуйста, разреграммы за новогодним столом, а лучшее присылайте мне :)

Хорошего завершения рабочей недели!

12 дек. 2019 г.

Чем измерять? Какой цифры нет?

Добрый день!

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

Интересно, что иногда достаточно отличающиеся по первоначальным определениям величины могут оказаться взаимосвязанными. В разборе детского вопроса о том, что произойдёт, если взять моль кротов (кстати, рекомендую этот сайт для совместного чтения с детьми), упоминается следующее забавное совпадение: «сфера с радиусом X километров будет такого же объема, что и куб со стороной X миль». Ясно, что это достаточно приблизительно, но не менее ясно, что и само понятие мили весьма гибкое: морская миля = 1852 метра, географическая миля = 1855,3 метра, а ведь есть ещё французские сухопутная и морская мили, древнеримская, датская, норвежская и т.д., а также шотландская миля, длина которой варьировалась в зависимости от региона, но была примерно на 200 метров длиннее британской (1809−1814 метров).

Кстати, про совпадения: сегодня мне рассказали, что в десятичной записи числа числе 229 (два в двадцать девятой степени) ровно девять цифр (это легко понять), причём все они различны (а вот в это придётся поверить). Из такого факта может получиться удачная разминочная задачка. Сможете ли вы определить, какой цифры нет в записи этого числа, не вычисляя его? Задачка приятная, рекомендую (путёвые младшеклассники вполне способны определить 5-6 цифр, которые точно есть в записи этого числа, так что для вечернего совместного обсуждения задачка подходит).

Но вернёмся к разнообразию единиц измерения. Что забавного ещё сразу же вспоминается? Пример: градусы Фаренгейта, если верить легенде, вышли такими необычными ещё и из-за того, что жена Фаренгейта болела (мол, он планировал определить свою шкалу так, чтобы 100 градусов соответствовали температуре здорового человека, но не тут-то было, т.к. калибровал установку он по слегка температурящей жене). Ноль же градусов он решил определить, ориентируясь на физические свойства смеси воды, льда и хлорида аммония, что с нашей нынешней колокольни тоже не вполне интуитивно (разные подходы применялись для исправления отдельных дефектов систем, которые были очевидны исследователям; скажем, Цельсий прекрасно понимал, что температура кипения воды зависит от атмосферного давления — попыткой обойти эту особенность стало, например, определение градуса Реомюра через расширение спирта на 1 тысячную его объёма).


(картинка из Википедии)

А какие ещё забавные факты и удивительные совпадения вы можете вспомнить о различных единицах измерения?

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

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

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



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

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