Правила для бесправия

А иногда попадаются на глаза совсем странные новости (цитата): «Посольство Франции в Москве отказалось выдать визы членам сборных России по борьбе, планировавшим принять участие в турнире имени Анри Деглана, который пройдет 27 и 28 ноября в Ницце. По словам первого вице-президента Федерации спортивной борьбы России (ФСБР) Георгия Брюсова, французская сторона не назвала причины своего решения.»

Разгадка этого ребуса будет позже, а пока давайте вникнем в требования для получения визы. Например, необходимо предоставить две фотографии размером 35 на 45 миллиметров, сделанные таким образом, чтобы размер головы от макушки до подбородка составлял около 3 см, а изображение лица занимало около 70-80% фотографии. Бывают ли такие фотографии лиц?

Рассчитать легко: площадь фотографии - 3.5х4.5=15.75 сантиметров квадратных. А лицо должно занять от 70 до 80 процентов этой площади. Считаем: 15.75х0.7=11.025. Другими словами, чтобы удовлетворить требованию «лицо занимает 70% фотографии», необходимо иметь площадь лица более 11 квадратных сантиметров. Но в этих же требованиях сказано, что высота лица всего 3 сантиметра.

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

Если бы лицо было идеальным прямоугольником, то его площадь составила бы 3х3.5=10.5 квадратных сантиметров. Это почти то, что требуется, но всё ещё чуть-чуть не хватает для достижения цели хотя бы в 70%. Выходит, мало иметь широкое и прямоугольное лицо! Что же делать? Есть один выход - надо отрастит щёки и уши - они бы свисали и торчали по краям, позволяя удовлетворять странным требованиям :)

Вообще говоря, такие ограничения на фотографии позволяют не выдавать визу любому человеку. И не из-за каких-то «политических соображений», а по простейшей причине - «не смог правильно подать документы». Соменевающиеся в том, что требования к фотографиям именно такие, легко могут снять все вопросы, зайдя на официальные сайты консульств (или спросив у поисковых систем «Изображение лица должно составлять около 70-80 % фотографии»). Это очень распространённое требование, которое совершенно не совместимо с остальными ограничениями.

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

Ну а что же было с нашей сборной по борьбе? Если верить тем же журналистам, всё не совсем так плохо: «Советник посольства по делам прессы Том Бюффен заявил, что некоторые члены российской делегации не подали все нужные документы», а «основная часть команды получает въездные визы во Францию в четверг, 26 ноября». Складывается впечатление, что журналисты переврали слова вице-президента Федерации спортивной борьбы или он не очень точно выразился.

А какие примеры подобных массовых нарушений своих правил вы знаете?

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

Правила ради правил

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

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

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

Заинтригованы? Оказывается, проблема в том, что данный человек уже однажды пользовался услугами этого банка. У него осталась карточка Виза-Электрон, на которой уже много лет почти нет денег. Это преступление? Нет, за это банк ничего не сделает. А вот тот факт, что карточку он получил до того, как сменил гражданство - реальная проблема.

Ему не могут открыть вклад на новый паспорт, потому что он уже клиент банка - должен пользоваться тем документом, по которому начал. Чтобы открыть вклад, он должен закрыть договор по старой карточке. Для этого необходимо произвести её перевыпуск на новый паспорт - это несколько дней возни. И только после этого можно будет делать что-то новое. И открыть вклад на новый паспорт они не могут, потому что не должно быть две разных записи в базе данных для одной персоны. Я не банковский работник, поэтому не уверен, что правильно понял пересказ их объяснений. Возможно, всё было чуть-чуть иначе.

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

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

Поэтому вопрос: с какими похожими глупостями вы сталкивались в своей жизни?

Хорошей вам недели!

Перепроизводство и подарки

Во многих умных экономических книжках написано, что банкротства - это совершенно нормальные и правильные явления, потому что они убирают с рынка тех, кто больше не нужен. Остаётся только понять, откуда берутся эти компании, чьи услуги/товары перестают покупать...

Рассмотрим, например, наручные часы. У меня есть четыре экземпляра электронных часов: одни я купил лет 15 назад, а ещё трое часов были подарены родственниками и друзьями. Все они прекрасно работают, но чтобы это состояние сохранилось, из них давно извлечены батарейки. Ещё есть пара механических часов - память о дедушках. Но все эти часы я не ношу, так как уже давно привык к мобильному телефону. И у многих моих знакомых тоже есть хотя бы 3-4 экземпляра различных часов. И с возрастом их количество только растёт.

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

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

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

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

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

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

Поэтому опрос:

1. Есть ли у вас родственники, периодически дарящие одежду, которая вам не подходит? Или из-за фасона, или размер не тот, или качество не устраивает, но их подарок вы надеваете только один раз - примерили при дарителях «чтобы порадовались».

2. С какими дурными проявлениями подарков, сделанных «потому что нельзя прийти с пустыми руками» вы сталкивались? Удавалось ли убедить своих друзей/родственников больше так не делать?

3. Сколько у вас наручных часов?

Транзитивность

Добрый день.

В недавней заметке о разборчивой невесте мы рассматривали группу кандидатов, между которыми есть транзитивное отношение. Записывали мы это так: если А лучше Б, а Б лучше В, то А заведомо лучше В для произвольных A, Б и В. При выполнении этого условия для любой тройки кандидатов можно говорить, что отношение «лучше» является транзитивным.

Например, отношение «тяжелее» тоже является транзитивным: если А тяжелее Б, который тяжелее В, то А тяжелее В. С числами тоже всё легко: если a>b и b>c, то a>c. Легко показать, что свойства параллельности прямых или делимости чисел являются транзитивными.

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

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

Но сначала давайте поймём, как вообще можно считать вероятность того, что одна кость выиграет другую. Предлагаю доверить это дело компьютеру (кстати, это неплохая задачка для освоения его возможностей): запускаем любой табличный процессор и записываем в него строчку и столбец из 6 чисел - значения на гранях первого и второго кубиков, соответственно. В образовавшееся поле 6 на 6 клеток поставим статусы «победил»/«проиграл» (я ставил 1 и 0, чтобы было проще считать). Для этого я записал формулу в верхнюю левую ячейку таблицы, которая для каждой из 36 ячеек сравнивает самое левое число (с грани одного кубика) с самым верхним (с грани второго кубика) - моя формула видна в верхнем правом углу изображений. А потом просто «растянул» эту ячейку на оставшиеся 35 клеток, чтобы получить результаты для всех возможных состояний.

Что мы получили? Сейчас поймём! Один кубик может выпасть шестью разными способами. Второй - тоже шестью способами. Поскольку кубики друг на друга не влияют, то есть 36 разных равновероятных вариантов состояний пары кубиков после броска. Вот мы и рассмотрели все эти 36 вариантов. Остаётся просуммировать единички в таблице, чтобы увидеть, что кубик, значения граней которого расположены вертикально, побеждает в 21 случае из 36. Это значит, что с вероятностью примерно 58% кость (2 3 4 15 16 17) окажется сильнее кости (1 8 10 11 13 14).

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

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

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

Хорошей вам недели!

Клад и кости

Добрый день.

Сегодня я хочу напомнить одну старинную задачу о честном дележе клада, а потом предложу игру, чем-то похожую по постановке, но очень отличающуюcя по сути.

Если два пирата нашли клад, но не считают правильным расправляться друг с другом, чтобы единолично им завладеть, то есть один хороший выход - честно его поделить. Осталось придумать, как бы так распределить добычу, чтобы оба были довольны. Уже не один век известен следующий алгоритм:
1. Один участник делит весь клад на две части, после чего отходит в сторонку.
2. Второй, внимательно изучив две кучи всевозможных ценностей, выбирает себе одну из них.
3. Соответственно, первому остаётся то, что второй не забрал.

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

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

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

Теперь, имея этот опыт, мы будем определять правила предельно ясно ;)

Итак, есть 3 шестигранных игральных кости с чистыми гранями и один маркер. Двое игроков действуют следующим образом:
1. Первый рисует на гранях костей числа от 1 до 18 (без повторов, поэтому использует все 18 чисел на всех 18-ти гранях).
2. Второй выбирает себе одну из трёх игральных костей.
3. Первый выбирает одну из двух оставшихся.
4. После этого игроки бросают свои кости - выигрывает тот, на чьём кубике выпадет большее число.

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

Приглашаю обсудить эту задачку в комментариях. Хороших вам выходных!

Проблема остановки выбора (разборчивая невеста)

Знаете ли вы, что 33% студенток Гарвардского университета вышли замуж за своих преподавателей в 1901 году? Можно представить себе, что написала бы жёлтая пресса про учителей вроде бы приличного ВУЗа, которые не умеют себя контролировать... Впрочем, если разобраться, то окажется, что в том году в Гарварде было всего три студентки, одна из которых вышла замуж за своего профессора. Утверждение может быть абсолютно корректным, но выглядеть дико, если его «удачно» подать. Поэтому знание математики необходимо обществу, если оно не хочет слепо следовать за первым попавшимся жуликом.

Разберём коротко прошлую задачку о странном любовном треугльнике: Женатый Джек любит Анну, которая влюблена в холостого Джорджа. Вроде бы мы не знаем статус Анны, но давайте рассмотрим оба варианта:
- Если Анна состоит в браке, то она и есть тот человек, который любит холостого.
- Если Анна свободна, то женатый Джек является тем человеком, который любит незамужнюю.
Это означает, что ответ «недостаточно данных» является преждевременным. Похоже, интуиция многим мешает разобрать обе возможные ветки этой задачи. Я тоже чуть было так не ответил, но вовремя сообразил, что «не зря же мне эту задачу предложили». И тогда подумал ещё раз, что и привело к полному пониманию ситуации.

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

Раз у нас нынче идёт неделя вероятностей, женитьб и чисел вида 1/e (речь о парадоксе с раздачей подарков), то имеет смысл вспомнить ещё одну задачку, которая возникла совсем недавно - буквально 50 лет назад. Мы её знаем как задачу о разборчивой невесте или проблему остановки выбора, а зарубежом она обычно называется «secretary problem» или «marriage problem» (конечно, есть ещё масса названий).

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

Цель нанимателя/принцессы: выбрать самого лучшего из возможных.
Вопрос: как следует действовать и с какой вероятностью цель будет достигнута?

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

Оказывается, правильная стратегия состоит в следующем:
1. Делим всех N претендентов на две группы: «эксперементальная» (1/e от всех) и «рабочая» (1-1/e от всех).
2. Первой группе (первым N/e претендентам) следует отказать, запоминая, кто из них самый лучший.
3. Представители второй группы уже имеют шансы: следует соглашаться на предложение первого же, кто лучше всех своих предшественников.

Интересно, что при этой стратегии принцесса получит наилучшего принца с вероятностью 1/e (согласитесь, не так уж и мало, учитывая сложность ситуации). Эта задача имеет интересные расширения. Например, если принцесса не слишком привередлива, то она может прожить счастливую жизнь не с самым лучшим принцем, а с тем, кто входит в список «k лучших принцев». Если k=2 (если принцесса согласна на любого из двух самых лучших), то при правильной стратегии она найдёт своего принца с вероятностью 57 процентов.

Рекомендую прочитать интереснейшую книгу на эту тему - Разборчивая невеста (всего 200 килобайт). Это 25-ый выпуск библиотеки «Математическое просвещение» - на двух десятках страниц изложены очень интересные подходы к решению задач (кстати, многие школьники вполне смогут понять этот материал, поэтому стоит попробовать им предложить!). Любители английского языка и противники pdf-файлов найдут статью в википедии (не так подробно, но есть ссылки на близкие по содержанию материалы)

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

Замуж за иностранца

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

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

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

Джек женат, но любит Анну, которая влюблена в холостого Джорджа. Верно ли, что человек, состоящий в браке, любит человека, в браке не состоящего?

Варианты ответа: «Да, это так», «Нет, это не так», «Мало данных для точного ответа», «Я уже видел эту задачку, поэтому знаю ответ». Пожалуйста, оставьте своё мнение в комментариях к заметке, не читая чужих версий.

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

Если вам не очень интересно читать длинные и подробные математические рассуждения, то предлагаю прочесть только подведение итогов - от абзаца, начинающегося словами «Уф-ф...» :)

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

Итак, есть N подарков и N людей, каждый из которых получит ровно один подарок. Это значит, что есть ровно N! способов раздать подарки этим людям (первый получает один из N подарков, второй - один из (N-1) оставшихся подарков, третьему достанется один из (N-2) подарков и так далее). Перемножаем все эти независимые случаи, получаем N*(N-1)*(N-2)*(N-3)*...*2. Запомним этот результат, он нам много раз пригодится.

Теперь давайте разберём случай, в котором первый человек уже получил свой подарок. Это значит, что у нас осталось (N-1) людей и (N-1) подарков (причём каждый подарок принёс один из этих оставшихся). Сколькими способами они могут распределить эти подарки между собой? Как мы установили в предыдущем абзаце, есть (N-1)! способов. Давайте это запомним: если один человек получил свой же подарок, то остальные (N-1) человек могут распределить между собой подарки (N-1)! способами.

Теперь рассмотрим ситуацию, когда второй человек получил свой подарок. Оставшиеся опять могут распределить подарки X1=(N-1)! способами. Аналогично для третьего, четвёртого,... , N-ного участника. Получается, что если сложить все эти случаи, то выйдет N*X1=N*(N-1)!, что как раз равно Y1=N!. Пока всё просто, но сейчас надо осознать одну важную вещь: некоторые возможные ситуации были посчитаны несколько раз. В самом деле, случай, когда первый и второй участники одновременно получили свои подарки, учтён дважды (в первой и во второй сумме). Поэтому для получения правильного ответа необходимо из нашего результата Y1=N! один раз вычесть дважды учтённые расклады (для парных совпадений). Более того, в этот Y1=N! случаев трижды включены расклады, в которых первый, второй и третий участники одновременно получили свои подарки на руки. Такие случаи тройных совпадений надо вычесть дважды (чтобы осталось ровно одно). Дальше аналогично: четвёрки посчитаны по четыре раза, их надо вычесть трижды, пятёрки посчитаны пять раз - их надо вычесть четыре раза. И так далее. Звучит сложно, но мы вот-вот доберёмся до результата.

Давайте разберём случай, в котором двое участников получили свои подарки на руки. Оставшиеся (N-2) участника, как мы выяснили недавно, могут распределить оставшиеся (N-2) подарка ровно X2=(N-2)! способами. Выходит, надо просуммировать все эти X2 конфигурации для всех возможных пар из N участников. А таких пар может быть ровно N*(N-1)/2! (потому что порядок не имеет значения). Выходит, что таких конфигураций ровно N*(N-1)/2 * X2, что как раз равно Y2=N!/2.

Опять важно отметить, что мы несколько раз посчитали одинаковые конфигурации: например, случай, когда первый, второй и третий участники одновременно получили свои подарки, учтён 3 раза. Поэтому для получения правильного ответа из нашего результата Y2=N!/2 необходимо два раза вычесть трижды учтённые расклады. Аналогично - для четвёрок, пятёрок и так далее.

Для ясности рассмотрим следующий шаг: считаем, сколько возможно случаев, в которых трое получили свои подарки. Поскольку трёх человек из N можно выбрать N*(N-1)*(N-2)/3! способами, то получаем результат N*(N-1)*(N-2)/6, что равно Y3=N!/6. Но опять же в нём посчитаны лишние четвёрки, пятёрки... Их тоже надо будет вычесть.

Соберём получившийся «хаос»: заметим, что выражение T(N)=Y1-(Y2-(Y3-(Y4-(Y5-...)))) нам очень удобно. Оно как раз обладает замечательным свойством: многократно учтённые случаи благополучно вычитаются нужное количество раз, поэтому все возможные расклады остаются в количестве ровно одной штуки (надо посмотреть на эту строчку несколько десятков секунд, чтобы почувствовать это). Другими словами, T(N) - это как раз и есть идеальный ответ. T(N) - это количество ситуаций без повторов, в которых хотя бы один участник получил свой подарок обратно. Если из общего количества возможных раскладов N! вычесть T(N), то мы получим количество случаев, в которых никто не получил свой подарок обратно.

Подставим Yi в формулу и раскроем скобки: выходит T(N)=N!-(N!/2!-(N!/3!-(N!/4!-...)))=N!-N!/2!+N!/3!-N!/4!+N!/5!-...-(-1)^N.

Теперь найдём Z(N) - количество ситуаций, в которых каждый получил чужой подарок: Z(N)=N!-T(N)=N!/2!-N!/3!+N!/4!-N!/5!+...+(-1)^N.

Ну а теперь найдём P(N) - вероятность того, что никто не получит свой подарок обратно. Для этого надо разделить количество интересных нам элементарных исходов на количество всех возможных элементарных исходов N!.

P(N)=Z(N)/N! = 1/2! - 1/3! + 1/4! - 1/5! + ... + (-1)^N/N!.

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

Ну а тот факт, что P(N) стремится к 1/e при N стремящемся к бесконечности, легко понять, так как разложение в ряд Тейлора функции экспонента как раз совпадает с P(N) при параметре -1 (exp(-1)=Sum{k=0..inf}(-1)^k/k!). Интересно вот что: P(N) стремится к 1/e очень быстро. Уже для семи участников P(N) приблизительно равно 0.3679 (то есть, совпадает с 1/e с точностью до четырёх знаков после запятой). Мне кажется, это вообще очень важно осознать: если вероятность каждого конкретного события всего лишь 1/N, но этих событий N штук, то вероятность того, что хотя бы одно произойдёт, получается около 2/3. То есть, хотя бы одно событие скорее произойдёт, чем ничего не произойдёт.

Если вам эта тема показалось такой интересной, что хочется прочитать ещё что-то, то рекомендую поискать статьи с распределением Пуассона в главной роли (сейчас мы рассматривали распределение с параметром λ=1). Оно известно человечеству с 1837 года - тогда Симеон Денис Пуассон издал книгу со своими размышлениями о различных последовательностях испытаний Бернулли. В то время эти исследования не нашли себе применения, но после 1894 года распределение Пуассона пригодилось при изучении одного странного феномена: германская армия анализировала статистику трагических случаев, когда солдат был убит ударом копыта. Согласно наблюдениям, 196 солдат погибли таким образом за 280 наблюдений (20 лет умножить на 14 кавалерийских корпусов). Это значит, что можно ожидать, что события будут подчинены распределению Пуассона с параметром λ=0.7. Другими словами, должно было быть 139 случаев без смерти участника, 97 наблюдений с одной смертью, 34 наблюдения с двумя смертями и так далее. Реальность оказалось такой: 140 случаев без жертв, в 91 случае был один убытый копытом, в 32 случаях - двое. Реальные наблюдения очень хорошо совпали с теоретическими размышлениями, что очень поддержало теоретиков, хотя солдат, конечно, жалко.

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

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

Хорошей вам недели!

Вероятности и подарки

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

Какие рассуждения при этом используются?

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

Недавно мы уже говорили о том, что словами «бесконечность» и «предел» нужно пользоваться очень осторожно, чтобы не обмануть самого себя. А про любые «очевидные» логические переходы надо уметь в течение 30 секунд детально и корректно объяснить, почему они очевидны. Но сегодня я предлагаю начать с обратной стороны: поставить эксперимент.

Проще всего для этого воспользоваться языком программирования javascript, потому что он есть под рукой почти у всех читателей (да и традицию не будем нарушать). Создайте файл presents.html со следующим содержимым и откройте его браузером:

<script type="text/javascript">
N = 100;     // quantity of presents (and participants)
nbIt = 1000; // quantity of iterations
okIt = 0;    // OK situaions
for (iter = 0; iter < nbIt; iter++) {
  var a = new Array(N); // create array
  for(i=0; i<N; i++)
    a[i] = i; // fill it by numbers 0, 1, 2,... , N-1

  // shuffle array
  i = N;
  while(i) {
   j = Math.floor( (i--) * Math.random() );
   t = a[i];
   a[i] = a[j];
   a[j] = t;
  }

  // calculate number of self-presents
  selfp = 0;
  for(i=0; i<N; i++)
    if (a[i] == i)
      selfp++;

  if (selfp == 0) // if there are no self-presents
    okIt++;       // increase OK-counter
}

document.write('Probability of OK-situation: ' + (100*okIt/nbIt) + '%');
</script>

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

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

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

Зачем это надо? Для калибровки своей интуиции! Редкий человек обладает достаточной дисциплиной ума, чтобы проверять каждый шаг всех выкладок. Иногда приходится полагаться на ощущение «это верное утверждение, потому что оно не может быть ошибочным»... Но чтобы чего-нибудь достичь, позволяя себе такие вольности, необходима тренированная интуиция, а не умение переспорить. Эти глубокие интуитивные шаги необходимы, чтобы не погрязать в рутине маленьких простых этапиков в размышлениях, а сразу выделять важные и серьёзные идеи (которые потом, конечно, надо будет детально обосновать, если они покажутся интересными).

Полагаю, скоро в комментариях появится объяснение, почему даже для небольших групп людей вероятность получения сюрприза каждым не очень высока. А самое интересное, почему эта вероятность не устремляется к 100% при росте количества участников :)

Манипуляции полезны?

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

Сейчас уже можно кидаться камнями с надписью «и ты тоже о свином гриппе», но я попробую успеть до этого сказать, что пример с ним будет короткий (один последний абзац), а сама заметка о другом.

Теоретический вопрос состоит в следующем: допустим ли небольшой обман, если от этого зависят тысячи жизней? Кто-то ответит, что недопустим. Увы, сейчас это почти никого не интересует, потому что стало очень обычным. Недавно мы вспоминали очень распространённое различие в представлениях о названии романа Льва Толстого «Война и мир». Как вы понимаете, такой миф существует не для спасения в критической ситуации. Полагаю, он так хорошо живёт из-за того, что «массирует чувство собственной важности» - приятно ощущать себя понимающим глубину великой литературы.

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

Вспомним, например, что человечество пока не умеет надёжно лечить ВИЧ-инфицированных, а их количество продолжает расти. Самые эффективные и частые способы передачи ВИЧ - использование общего шприца для инъекций и анальный секс (заразиться при традиционном значительно труднее, если верить официальной статистике). А раз так, то массовое неприятие наркоманов и гомосексуалистов может быть вполне позитивным явлением для здоровья человечества.

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

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

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

Или давайте поймём возможный смысл истерики с тем же свиным гриппом. Чего боятся некоторые биологи? Вроде бы ничего выдающегося в новом штамме нет - смертность от него и способность распространяться вполне рядовые. А какую пользу тогда может приносить массовая паника (речь сейчас не об экономической выгоде отдельных участников рынка)? Есть теория, что последние годы один из основных рисков - одновременное заражение человеческой клетки «птичьим гриппом» и любым штаммом «обычного» гриппа (в том числе, и «свиного»). При этом с некоторой вероятностью может произойти рекомбинация РНК этих вирусов, из-за чего возникнет новый вирус, обладающий способностью передаваться от человека к человеку (как обычный), но с высокой смертоносностью (как «птичий»). Просчитывать опасность и вероятность такого события я не возьмусь, так как я вообще не специалист в этой области (эх, было бы здорово, если бы такую фразу говорили все неквалифицированные теоретики). Но я призываю увидеть следующую возможность пользы от «свиной паники»: люди постараются меньше подставляться (реже ходить в общественные места, чаще мыть руки, проветривать помещения), что уменьшит активность «обычного» гриппа в этом году. А это уже снижает вероятность рекомбинации РНК двух разных вирусов в ближайшее время, что похоже на реальную пользу.

Хорошей вам недели! И крепкого здоровья!

Нам не дано предугадать

Что отнято судьбой, а что подарено, -
В конце концов не все ли мне равно?
(c) Михаил Щербаков
(впрочем, по совсем другому поводу)

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

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

Его актёрская судьба началась очень странно - со вступительных экзаменов в педагогический ВУЗ. Как Дмитрий сказал, его выгнали с экзамена по химии, потому что поймали со шпаргалкой. Возможно, кто-то тогда переживал: «Как же так? Лишили ребёнка возможности стать учителем! Пожалели бы чуть-чуть!»

Но его выгнали с экзамена, не взяли в ВУЗ, поэтому Дмитрий не стал учителем. А стал слесарем. Частые гости «Ленкома», возможно, удивятся, как можно такого Фигаро ставить за слесарный станок :)

Но оказалось, что работа на заводе дала будущему актёру две важных вещи:
1. Он понял, что категорически не хочет стоять всю жизнь за станком.
2. Имея 7 часов рабочего времени, в течение которых голова не занята совсем, Дмитрий мог о многом думать.

И второй пункт мощным рывком притянул его к книгам и театру. Как он сказал, «начал ходить в театр сам, а не с родителями». Ну а после этого всё было как у всех :) А представьте, что ему попались бы не такие строгие экзаменаторы!

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

Мы не знаем будущего, поэтому пора перестать кипятить собственный мозг в подобных случаях. Колебаться и напрягаться надо только в тех ситуациях, когда о раскладе имеется хоть какая-то информация. Не надо себя накручивать, потому что мы не можем всего предусмотреть. Делайте так, как кажется правильным!

Хорошей вам недели!