Самый большой стол

Добрый день.

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

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

Вопрос: стол какой максимальной площади можно занести в кабинет Дяди Васи?

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

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

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

Да, и ещё: завтра (в пятницу, 29 июня 2012 в 20.00 Москвы) состоится очередной (и последний в этом сезоне) турнир по игре «Банальности» (подробнее). Не пропустите интересную игру! Вы можете попробовать сыграть с роботами на сайте, чтобы почувствовать, в чём смысл.

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

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

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

Добрый день!

Можно потратить много денег, чтобы показать мне Филиппа Киркорова на лошади, поющего песню Сергея Шнурова «Ленинград» (вероятность того, что я окажусь в кафе именно тогда, когда местный телевизор исполнит это безумие, крайне мала, но ОНИ воспользовались своим шансом). А можно с весьма скромным бюджетом и совсем без лошади создать весёлый и просветительский клип «Грибок стопы» (угадайте, о чём), самый популярный комментарий к которому «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 шляп, он заранее знал, что первый скажет «пас», поэтому он тоже вынужден говорить «пас». И так далее. Возникает иллюзия, что выиграть невозможно. И тем интереснее догадаться, как же действовать мудрецам.

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

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

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