Дано: обыкновенная монетка и выбор из трех возможных вариантов (например, как в сказке налево, прямо и направо).
Требуется придумать алгоритм выбора одного из вариантов с помощью монетки, так чтобы вероятность выбора каждого конкретного варианта была 1/3, т.е. с помощью случайных событий с вероятностью 1/2 имитировать случайное событие с вероятностью 1/3.

Единственный вариант, который мы смогли придумать следующий: бросаем монетку 2 раза, орел пусть обозначает 0, решка – 1. Таким образом, получили число от 0 до 3 в двоичной системе. Пронумеровали все варианты налево – 1, прямо – 2, направо – 3. Если выпадает 0, то данный исход считается неблагоприятным и кидаем монетку заново. По закону больших чисел, рано или поздно, подходящий вариант выпадет. Единственное но нельзя заранее сказать, сколько итераций потребуется.

Может, кто еще какие варианты придумает.

поскольку 1/3 не может быть представлена конечной (непериодической) дробью в двоичной системе счисления, задача нерешаема.

Об этом мы уже думали, но алгоритм есть, я его написал. Он может потребовать много итераций, но рано или поздно он сработает.

Я понимаю, что разбить множество из 2^n элементов на 3 равные группы нельзя, но вот доказать что мы можем получить только множество в котором, вероятность каждого элемента или равна всем остальным или соотносится с ним, как степень двойки я не могу.

Цитата(LSD @ 22.8.2005, 23:15)

Он может потребовать много итераций, но рано или поздно он сработает.

То ли Вы забыли теорию вероятностей, то ли что... Для любого сколь угодно большого N существует отличная от нуля вероятность, что количество "итераций" будет больше этого N.

Цитата(LSD @ 22.8.2005, 23:15)

Я понимаю, что разбить множество из 2^n элементов на 3 равные группы нельзя

Однако можно задаться точностью, которая допустима (или которой можно пренебречь, что то же самое). Скажем если это 0,0001%, то достаточно 20 бросков и

Код

выбранный_вариант = полученное_20-битовое_число MOD 3

Цитата(Akina @ 22.8.2005, 23:31)

Для любого сколь угодно большого N существует отличная от нуля вероятность, что количество "итераций" будет больше этого N.

У нас N не заданно, количество итераций может быть любым.

Цитата(LSD @ 22.8.2005, 23:52)

У нас N не заданно, количество итераций может быть любым

Вот и я о том же... а тебе, как я понимаю, нужно гарантированно уложиться таки в конечное время.

Цитата(LSD @ 22.8.2005, 20:42)

бросаем монетку 2 раза, орел пусть обозначает 0, решка – 1. Таким образом, получили число от 0 до 3 в двоичной системе.

таким образом мы имеем 4 варианта:

00
01
10
11

а не 3.

Неверное решение в принципе.

Цитата(podval @ 23.8.2005, 10:22)

таким образом мы имеем 4 варианта: .... а не 3.

Цитата(LSD @ 22.8.2005, 20:42)

Таким образом, получили число от 0 до 3 в двоичной системе. Пронумеровали все варианты налево – 1, прямо – 2, направо – 3. Если выпадает 0, то данный исход считается неблагоприятным и кидаем монетку заново.

Рассмотри систему из трех состояний. 0 1 2


Начинаем движение из 0.


На каждом шаге кидаем монету и в соответствии с полученным результатом, идем в одно из смежных состояний.(из 0 в 1 или 2, из 1 в 0 или 2, из 2 в 0 или 1).


Через 100 шагов останавливаемся. То состояние в котором мы остановились и есть нужная сл величина.

Для i-го шага вероятность нахождения в состоянии 0 будет равна (вероятность нахождения в состоянии 1 на шаге i-1)*0.5 + (вероятность нахождения в состоянии 2 на шаге i-1)*0.5. В итоге получаем:

Код

Состояние 0  Состояние 1  Состояние 2 Шаг                                             1            0          0,5          0,5    2          0,5         0,25         0,25    3         0,25        0,375        0,375    4        0,375       0,3125       0,3125    5       0,3125      0,34375      0,34375    6      0,34375     0,328125     0,328125    7     0,328125    0,3359375    0,3359375    8    0,3359375   0,33203125   0,33203125    9   0,33203125  0,333984375  0,333984375   10  0,333984375  0,333007813  0,333007813   11  0,333007813  0,333496094  0,333496094   12  0,333496094  0,333251953  0,333251953   13  0,333251953  0,333374023  0,333374023   14  0,333374023  0,333312988  0,333312988   15  0,333312988  0,333343506  0,333343506

Мы стремимся к вероятности 1/3, но это тоже приближенное решение.

Цитата(LSD @ 23.8.2005, 12:32)

Мы стремимся к вероятности 1/3, но это тоже приближенное решение.

Ну не будет точного, не будет... я же объяснил даже почему...

Цитата(LSD @ 23.8.2005, 11:32)

Для i-го шага вероятность нахождения в состоянии 0 будет равна (вероятность нахождения в состоянии 1 на шаге i-1)*0.5 + (вероятность нахождения в состоянии 2 на шаге i-1)*0.5. В итоге получаем: Код      Состояние 0  Состояние 1  Состояние 2 Шаг                                             1            0          0,5          0,5    2          0,5         0,25         0,25    3         0,25        0,375        0,375    4        0,375       0,3125       0,3125    5       0,3125      0,34375      0,34375    6      0,34375     0,328125     0,328125    7     0,328125    0,3359375    0,3359375    8    0,3359375   0,33203125   0,33203125    9   0,33203125  0,333984375  0,333984375   10  0,333984375  0,333007813  0,333007813   11  0,333007813  0,333496094  0,333496094   12  0,333496094  0,333251953  0,333251953   13  0,333251953  0,333374023  0,333374023   14  0,333374023  0,333312988  0,333312988   15  0,333312988  0,333343506  0,333343506  Мы стремимся к вероятности 1/3, но это тоже приближенное решение.

Да, но если точность решения больше точности представления числа в компьютере. То решение можно считать точным - это раз.


Два, скорость сходимости пропорциональна 2 в степени минус количество шагов - что есть супер быстро.



Добавлено @ 11:39

Цитата(Akina @ 22.8.2005, 21:53)

поскольку 1/3 не может быть представлена конечной (непериодической) дробью в двоичной системе счисления, задача нерешаема.

К сожелению это не доказательство и не объяснение.

Цитата(esperant0 @ 23.8.2005, 12:37)

К сожалению это не доказательство и не объяснение.

Да? ну и ладно... я считаю иначе, но спорить не буду - на результат это не влияет.

Цитата(Akina @ 23.8.2005, 11:43)

Цитата(esperant0 @ 23.8.2005, 12:37) К сожалению это не доказательство и не объяснение. Да? ну и ладно... я считаю иначе, но спорить не буду - на результат это не влияет.

Математика на то и математика - что правильность доказательства не трудно установить.
Путем логических рассуждений. Которые вы отказались к сожалению привести.

Цитата

К сожелению это не доказательство и не объяснение

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