Pull to refresh

Comments 8

Асимметричная монетка выпадает орлом с вероятностью p и решкой с вероятностью q. Как двум людям вытянуть честный жребий с её помощью?

Вариант избыточный, но зато без расчета - можно бросить монетку 6 раз, 3 раза из которых орел трактуется в пользу первого участника, а 3 раза - в пользу второго. Кто получил больше орлов - тот и побеждает. Если равное количество - бросаем еще 2 раза....

Подозреваю, что можно и за меньшее количество бросков?

Соревновательная модель получается, если я не ошибаюсь. Чем больше асимметрия, тем больше ходов.

Я думал об устранении асимметричности путём удаления k вхождений результатов с большей вероятностью. Пусть p=2/3, а q=1/3. Кидаем монетку три раза и удаляем одного орла, если он есть. Считаем процентное соотношение. У кого больше, тот и победил.

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

Ну и да, если p=0.99 то ходов даже с оптимальным алгоритмом потребуется много, ведь если все время выпадает орел он никакой полезной информации не приносит.

Еще проще - каждый кидает по 1 разу. Если выпало одинаково - перекидываем, если разное - у кого орел тот и победил.

Да, это хороший базовый алгоритм, от которого стоит отталкиваться

Imho в этой статье была бы уместной отсылка к арифметическому кодированию – задачи очень пересекаются и алгоритм по сути общий (единственное – в арифметическом кодировании он повторяется раз за разом).

Спасибо, это хорошее замечание!

Для асимметричной монеты есть еще такой паззл: надо бросить честный жребий на 5 чел., но мы имеем право на старте выбрать и зафиксировать p (и q = 1 - p) по своему разумению. Придумать это самое "p" и алгоритм, чтобы гарантировать результат не более чем за N бросков (чем меньше N, тем лучше, знаю решение за N=5)

Sign up to leave a comment.

Articles