Король Артур и Рыцари Круглого Стола — про справедливость

[Equinoxe]

— Сэр, — сказала королева Гвиневера, — я хочу выбрать и взять с собою кое-кого из рыцарей
— Поступайте по своему желанию, — ответил король Артур
— Но не соблаговолите ли вы самолично выбрать одного из них?
Артур, не долго думая, достал один безант* и несколько раз подбросил его, после чего ответил:
— Пожалуй, возьмите сэра Ланселота
— Разрешите полюбопытствовать: как монета помогла Вам в этом выборе?
— Все 12 рыцарей Круглого Стола равноправны между собой, а значит и шансы быть выбранным у них должны быть равны.

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

*Безант — золотая монета византийской чеканки, имевшая хождение в Европе с IX в. Достоинство ее в разное время менялось.

[age]

(Оффтоп)

не вижу способа минимизировать так, чтобы королева не заметила. Хотя это зависит от её собственного интеллекта. Если она умна, то выше чем на 10% увеличить вероятность не удастся

[Евгений Машеров]

Бросаем 4 раза, рассматривая "орёл" как 1, а "решку" как 0, получем двоичное число $0\le n\le15$
Если $n \le 11$, посылаем рыцаря с номером n+1.
Иначе (n-12) рассматриваем, как два разряда нового числа m, ещё два разряда получаем, бросив ещё дважды.
Полученное число трактуем аналогично, пока не получим $m \le 11$
С вероятностью 3/4 хватит 4-х бросаний, иначе нужно $\frac 1 4 \frac 3 4 2 + \frac 1 4 \frac 1 4 \frac 3 4 2 +...=\frac 1 2$
Итого матожидание 3.5
Теоретический минимум равен $\log_2 12=3,5849625007211561814537389439478$

-- Вс июл 24, 2011 22:27:22 --

Выйти на теоретический минимум несколько сложнее. Для этого надо записать $\frac 1 {12}, \frac 2 {12}, ... \frac {11} {12}$ в двоичном виде. Бросая монету, выписываем двоичное число, проверяя, не попадает ли одна или несколько выписанных на предыдущем шаге границ в интервал между полученным числом и числом, полученным дополнением его бесконечно большим числом единиц. Если не попадает - умножаем полученное число на 12, прибавляем единицу, и целая часть есть номер рыцаря. Если попадает - ещё раз бросаем и опять проверяем.

[mihailm]

Евгений Машеров в сообщении #470957 писал(а):

Бросаем 4 раза, рассматривая "орёл" как 1, а "решку" как 0, получем двоичное число $0\le n\le15$
Если $n \le 11$, посылаем рыцаря с номером n+1.
Иначе (n-12) рассматриваем, как два разряда нового числа m, ещё два разряда получаем, бросив ещё дважды.
Полученное число трактуем аналогично, пока не получим $m \le 11$
С вероятностью 3/4 хватит 4-х бросаний, иначе нужно $\frac 1 4 \frac 3 4 2 + \frac 1 4 \frac 1 4 \frac 3 4 2 +...=\frac 1 2$
Итого матожидание 3.5
...

Счет неверный 14/3 получится

[Cash]

$14/3$ получается, если сводить задачу к выбору 1-го из 3-х.
2 бросками выводим 3-х рыцарей в "финальную пульку". После чего разыгрываем между ними, бросая монетку по 2 раза, пока не выпадет присвоенная им комбинация.
Вопрос - можно ли улучшить? $\log_2 12=3,58$ точно недостижимо. Как ни крути, а кинуть монетку 4 раза придется, вероятность выбора какого-либо рыцаря после 3-х бросков минимум $1/8$, что явно выше "справедливой". И как доказывать минимальность?

[Евгений Машеров]

Сорри, чего-то ночью стормозил. Спасибо за поправку.

[Equinoxe]

Cash, да, всё верно. Вот только насчет строгого док-ва минимальности всё довольно-таки сложно

[sup]

Строгое доказательство не очень трудное, особенно для тех, кто знаком с деревьями Хаффмана. Пусть у нас всего 3 рыцаря (для простоты). Построим двоичное дерево "стандартным образом": выпал 0 идем налево, выпала 1 идем направо. Получится бесконечное дерево, в листах которого написано либо 1 либо 2 либо 3 ("имена" рыцарей). Вероятность листа высоты $k$, очевидно, $2^{-k}$. Сумма всех вероятностей для данного рыцаря должна быть равна $1/3$. Замечаем, что
$\frac {1}{3}=\frac {1}{4} + \frac {1}{4^2} +\frac {1}{4^3} + \dots $
Это означает, что для каждого рыцаря имеется ровно 1 лист высоты 2, ровно 1 лист высоты 4 и тд. А это и есть решение Cash.
Можно, однако, возразить, что, например вместо $1/4$ можно использовать $1/8 +1/8$. Но это кодирование не оптимально. Изменяя, если потребуется, кодировку, можно добиться того, чтобы листы с вероятностями $1/8$ были "братьями". А это значит, что вместо этих двух листов, надо назначить листом их родительский узел. Ну например, пусть кодировка такая:
0,0,0 - первый рыцарь
0,0,1 - первый рыцарь
Такую кодировку легко "сократить", назначив
0,0 - первый рыцарь.
Для 12 рыцарей все аналогично.