Маловероятное событие

Добрый день!

Можно потратить много денег, чтобы показать мне Филиппа Киркорова на лошади, поющего песню Сергея Шнурова «Ленинград» (вероятность того, что я окажусь в кафе именно тогда, когда местный телевизор исполнит это безумие, крайне мала, но ОНИ воспользовались своим шансом). А можно с весьма скромным бюджетом и совсем без лошади создать весёлый и просветительский клип «Грибок стопы» (угадайте, о чём), самый популярный комментарий к которому «I really do like this music, even don't knowing the text».

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

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

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

Все 100 мудрецов будут в этом испытании выстроены в колонну (каждый видит тех и только тех, кто стоит перед ним), и на головы им будут надеты шляпы одного из k>0 цветов (цвета шляп выбираются независимо и случайным образом). Каждый из мудрецов в колонне, начиная с последнего, должен будет либо назвать цвет своей шляпы, либо сказать «пас».

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

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

Для случая k=1 всё достаточно просто: если известно, что шляпы бывают только одного цвета, то именно его надо называть. С вероятностью 100% ответ будет правильным, поэтому мудрецы пройдут тест. Остаётся найти решение для случая k>1. Будьте осторожны, читая источник задачки, так как там в комментариях уже всё подсказано.

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

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

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

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