Начни вчера

Добрый день!

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

Список странных национальных особенностей можно продолжать долго... Но есть одна очень распространённая традиция, которая присуща почти всем народам — начинать что-то делать с первого января.

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

И этот самообман может работать не неделями, а месяцами. Иногда человек в августе позволяет себе говорить «вот с 1 января я с этим завяжу»... Видели такое?

Редкому человеку везёт осознать правильную последовательность действий до того, как будет пора действовать. Обычно мы узнаём о том, как надо было поступить, когда уже поздно. Получается, что довольно часто мы уже отстаёт от правильного графика, потому что не располагали необходимой информацией или не успели сообразить вовремя. Нормальные люди, поняв, что именно надо делать, как можно скорее бы постарались скомпенсировать отставание, но у нас же есть традиция — начни с завтрашнего утра, начни с понедельника, начни с первого числа... И самая эффективная отговорка для самого себя — начни с первого января!

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

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

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

Живите счастливо! И начните делать это не с 1 января, а хотя бы прямо сейчас (или даже со вчерашнего дня :)

До встречи в 2012 году!

Аукцион с камнями

Добрый день.

За новогодним столом бывает здорово поиграть в какую-нибудь весёлую игру. Например, можно устроить аукцион, в котором побеждает тот, кто сможет закодировать пару чисел из наибольшего диапазона. Здорово звучит?

Цитата из книги «Что делать, если вас не считают занудой»: «Встретив филологов или историков, расскажите им анекдот про марсианина. Обязательно объясните им, почему это смешно. Убедите их поделиться этим анекдотом с друзьями. Проконтролируйте, чтобы они правильно объяснили своим друзьям, почему этот анекдот смешной».

Но возвращаемся к нашему аукциону. Недавно Константин Кноп напомнил чудесную формулировку (осторожно, там в комментариях сказано уже слишком много!):

Секретный код к любому из сейфов ФБР — это натуральное число от 1 до 1700. Двое шпионов узнали по одному коду каждый и решили обменяться информацией. Согласовав заранее свои действия, они встретились на берегу реки возле кучи из 26 камней. Сначала первый шпион кинул в воду несколько камней, потом - второй, потом опять первый и так далее до тех пор, пока камни не кончились. После этого шпионы разошлись. Каким образом могла быть передана информация? (Шпионы не сказали друг другу ни слова.) (Авторы - Дмитрий Челкак и Константин Кохась, СПбМО 2002, отборочный тур, 10 класс)

Мне в ней не нравятся две вещи:
- наших разведчиков назвали шпионами,
- задана граница 1700.

Поэтому давайте чуть-чуть переформулируем задачу:
- два человека знают целые числа из диапазона от 1 до N,
- они поочерёдно пишут на доске положительные целые числа, пока сумма всех записанных чисел не станет равна 26,
- давным давно они учились в одном классе, поэтому заранее договорились, как кодировать данные.

Вопросы:
1. Как они могли бы обменяться парой чисел при N = 1700?
2. Для какого максимального N вы можете придумать способ кодирования?

Эта задачка хороша тем, что когда кажется, что «ну уж дальше N увеличить невозможно», обязательно находится кто-то, кто опять смог поднять верхнюю границу :)

(Кстати, не так давно мы решали другую забавную школьную задачку, имеющую отношение к теории кодирования)

Хорошего начала предпраздничной недели!

Как считать вероятности?

Добрый день!

Неделю назад мы провели небольшой опрос на тему «Проще выиграть три раза из четырёх или пять раз из восьми?»

Опрос показал, что заметная часть подписчиков не только изучала, но и успешно освоила азы теории вероятностей. Если вы к ним относитесь, то можете смело переходить к последним двум абзацам заметки.

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

В комментариях можно прочитать разные мнения:
- кто-то считает, что из того, что подбрасывания монетки друг на друга не влияют (что верно), следует, что выиграть 3 раза из 4, 6 раз из 8, 5 раз из 8 можно с равными вероятностями (что неверно),
- кто-то считает, что раз 3 к 4 относится как 6 к 8, то одинаковы вероятности выигрыша 3 раза из 4 и 6 раз из 8,
- кому-то очевидно, что 3 раза из 4 можно выиграть с вероятностью 1/16, а хоть 5, хоть 6 из восьми можно выиграть с вероятностью 1/256.

Короче, разных мнений много, но разводить демократию для выбора правильного ответа мы здесь не будем. Давайте сначала выясним примерный ответ, проведя эксперимент (на JS, как обычно):

<script type="text/javascript">
n = 100000;  nb3of4 = 0;  nb6of8 = 0;  nb5of8 = 0;
for (i = 0; i < n; i++) {
  nbWin = 0;
  for (j = 0; j < 4; j++)
    if (Math.random() > 0.5)
      nbWin++;
  if (nbWin == 3)
    nb3of4++;
  for (j = 4; j < 8; j++)
    if (Math.random() > 0.5)
      nbWin++;
  if (nbWin == 5)
    nb5of8++;
  if (nbWin == 6)
    nb6of8++;
}
document.write('pA = ' + nb3of4/n + ', pB = ' + nb6of8/n + ', pC = ' + nb5of8/n);
</script>

Скопируйте этот текст в файл test.html, после чего откройте его браузером (на медленных компьютерах может работать несколько секунд).

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

У меня этот эксперимент дал следующие результаты:
  pA = 0.24865,
  pB = 0.10918,
  pC = 0.21898.

Вроде бы уже понятно, что вероятность события А больше В, а В больше Б, но как раз тут важно не остановиться, а понять, что означают эти числа. Давайте попробуем в первой строке программы заменить число 100000 на 10 (т.е. заметно сократим число экспериментов). У меня получались следующие результаты при n=10:
pA = 0.2, pB = 0, pC = 0.1,
pA = 0.2, pB = 0, pC = 0.5,
pA = 0.1, pB = 0.2, pC = 0.3,
pA = 0.4, pB = 0, pC = 0.2,
pA = 0.3, pB = 0.1, pC = 0.4.

Как видите, в первой и четвёртой строчках наша теория «pA > pC > pB» подтвердилась, а в трёх других строчках не подтвердилась. Что это означает? А это означает это, что мы провели эксперимент с низкой степенью достоверности.

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

Так и у нас с этой задачкой: если мы проводим всего 10 экспериментов, то вероятность получить правильный результат не очень высока. Преимущество же наше в том, что мы можем «опросить» всех, что позволит получить совершенно точный ответ.

Итак, кто же эти все? Это элементарные события. Мы можем перечислить все возможные равновероятные ситуации для нашей игры, а потом посчитать количество интересных. Например, если мы будем обозначать победу единицей, а поражение нулём, то список элементарных исходов для четырёх бросков монеты будет выглядеть так:
- 0000,
- 0001,
- 0010,
- 0011,
- 0100,
- 0101,
- 0110,
- 0111,
- 1000,
- 1001,
- 1010,
- 1011,
- 1100,
- 1101,
- 1110,
- 1111.

Поскольку монетка симметричная, а результаты предыдущих бросков не влияют на следующие, то все эти 16 ситуаций имеют равную вероятность. И так как в четырёх случаях из шестнадцати (выделенные строки) победа случается ровно три раза (три единички в строке), то и вероятность таких событий 4/16 = 0.25. Примерно это число мы и увидели в эксперименте при большом n.

Аналогично можно перечислить все расклады для 8 бросков монетки:
- 00000000,
- 00000001,
...
- 11111110
- 11111111.

Далее можно просто посчитать количество строк, в которых ровно 5 и ровно 6 единичек. Знатоки двоичной системы счисления уже давно поняли, что строк будет 2^8 = 256. Понятно, что работа была бы большая, но вполне выполнимая. Но давайте лучше найдём более простой способ посчитать число таких строк.

Начнём с «6 из 8». Нам проще будет посчитать, в каком количестве строк ровно два нуля (это то же самое, что и ровно 6 единиц). Первый нолик можно поставить на одно из восьми мест, а второй нолик — на одно из оставшихся семи мест. Получается, что два нолика можно разместить на восьми местах 8*7 способами. Надо только учесть, что каждый расклад мы посчитали дважды (сначала первый нолик левее второго, а потом на тех же местах второй нолик левее первого). Поэтому наш ответ надо ещё разделить на 2. Получается, что вероятность выиграть 6 раз из 8 равна 4*7/256 = 28/256 = 7/64 = 0,109375.

Теперь понятно, как посчитать число строк с пятью единичками на восьми местах. Будем считать, сколько у нас строк ровно с тремя нулями:
первый нолик можно поставить одним из 8 способов, второй — одним из 7 оставшихся способов, а третий — на одно из шести свободных мест. Получается 8*7*6 вариантов. Но здесь мы опять получили завышенную оценку, так как посчитали каждую возможную конфигурацию 6 раз (три нолика могут занять одни и те же позиции шестью способами: абв, авб, бав, бва, ваб, вба). Это значит, что наш ответ надо поделить на 6. Получается, что вероятность выиграть 5 раз из 8 равна 8*7/256 = 56/256 = 7/32 = 0,21875.

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

Дело в том, что в теории вероятностей ориентируется не так уж и много людей, но «применить здравый смысл» и «порассуждать о нормальном распределении» готовы очень многие (хоть и не готовы сформулировать определение нормального распределения). Я не спорю, иногда некорректные рассуждения приводят к верному ответу. Но надо помнить, что нередко правдоподобные о вроде бы очевидные мысли уводят от истины и мешают к ней вернуться. Поэтому я считаю правильным начинанием введение в ЕГЭ по математике одной простой задачки на теорию вероятностей. Это даёт надежду на постепенное движение к тому, что почти все школьники России будут легко справляться с элементарными вопросами о вероятностях.

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

Вероятность победы

Добрый день!

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

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

Я прошу вас написать в комментариях что-то вроде «вероятности Б и В одинаковы, а про вероятность А не знаю, но вроде бы должна быть меньше Б» (не это, а то, что подсказывает ваш здравый смысл).

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

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

UPD: опубликовано продолжение разговора.

Надёжная поломка

И даже если завтра появится телефон, аккумулятор
которого держит заряд 1000 лет, уже через месяц его придётся
поменять на новый, который держит заряд 2000 лет.

Добрый день!

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

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

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

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

Для одного гвоздя задачка решается элементарно.
Для N=2 многие уже решали в детском саду/начальной школе.
А как решить для N>2?
А можно ли решить так, чтобы длина верёвки не зависела от N экспоненциально?

Хорошего вам решения!