Comments 19
Думаю, следует указать, что необходимо, чтобы вероятность всех 3-х случаев была одинакова.
А то можно получить следующее:
Мат ожидание — 1 раз.
Орел — 1-й вариант, 50% вероятность
Решка — 2-й вариант, 50% вероятность
3-й вариант — 0% вероятность.
Формально, под условие задачи подходит…
А то можно получить следующее:
Мат ожидание — 1 раз.
Орел — 1-й вариант, 50% вероятность
Решка — 2-й вариант, 50% вероятность
3-й вариант — 0% вероятность.
Формально, под условие задачи подходит…
Мат. ожидание — 2,66 (посчитал программно, можно и дроби было составить, почитать на сходимость полученного ряда и т.д., но так — проще и быстрее, а точность не сильно пострадала).
В худшем случае — бесконечное число раз.
Подкидываем 2 раза монетку.
Орел — 1
Решка — 0.
Из этого получаем 4 равновероятного случая.
Если у нас
00 — 1й случай
01 — 2й случай
10 — 3й случай.
Если получили 11 — повторяем все заново.
А теперь почему максимум — бесконечное число раз.
Мы подкидываем монетку. У нее 2 варианта способа падения (орел/решка). Итого, столько бы мы не подкидывали монетку, у нас будет 2^<число подкидываний монетки> вариантов, которые надо разделить между 3 случаями равномерно. Но ни одна степень 2 не делится на 3, поэтому это невозможно, следовательно максимальное число подбрасываний — бесконечность.
Почему 2 раза подкидывать — это потому, что 1 явно недостаточно :)
В худшем случае — бесконечное число раз.
Подкидываем 2 раза монетку.
Орел — 1
Решка — 0.
Из этого получаем 4 равновероятного случая.
Если у нас
00 — 1й случай
01 — 2й случай
10 — 3й случай.
Если получили 11 — повторяем все заново.
А теперь почему максимум — бесконечное число раз.
Мы подкидываем монетку. У нее 2 варианта способа падения (орел/решка). Итого, столько бы мы не подкидывали монетку, у нас будет 2^<число подкидываний монетки> вариантов, которые надо разделить между 3 случаями равномерно. Но ни одна степень 2 не делится на 3, поэтому это невозможно, следовательно максимальное число подбрасываний — бесконечность.
Почему 2 раза подкидывать — это потому, что 1 явно недостаточно :)
Да, это самое очевидное решение. Но есть ли другие?
Решений — немеряно, но они будут и с большим мат. ожиданием.
Достаточно 2^<число подкидываний монетки> поделить целочисленно на 3, раскидать полученной количество кодов каждой из 3 монет, а не вошедшие в раскиданные коды объявить как для повтора. Конечно, не все случаи под данную модель попадут (если считать абсолютно, то 0% от числа возможных решений ;) ), но и в данной модели число решений — бесконечно.
Достаточно 2^<число подкидываний монетки> поделить целочисленно на 3, раскидать полученной количество кодов каждой из 3 монет, а не вошедшие в раскиданные коды объявить как для повтора. Конечно, не все случаи под данную модель попадут (если считать абсолютно, то 0% от числа возможных решений ;) ), но и в данной модели число решений — бесконечно.
А вот почему нельзя получить меньшее мат. ожидание, тоже можно доказать.
Например, 2 подкидывания за 1 итерацию алгоритма — минимум.
Если мы вышли на следующую итерацию, значит нас не волнует результат предыдущей (вероятность выбора 1-й из монет на данной итерации не должна измениться от предыдущих итераций), значит мы в том же положении, что и в предыдущей итерации и опять получаем, что 2 подкидывания минимум нам необходимо. А это как раз и есть приведенное решение.
Например, 2 подкидывания за 1 итерацию алгоритма — минимум.
Если мы вышли на следующую итерацию, значит нас не волнует результат предыдущей (вероятность выбора 1-й из монет на данной итерации не должна измениться от предыдущих итераций), значит мы в том же положении, что и в предыдущей итерации и опять получаем, что 2 подкидывания минимум нам необходимо. А это как раз и есть приведенное решение.
В данном доказательстве, конечно, есть скользкие моменты, например, можно сказать, что у нас вероятность невыхода в данной итерации — 1/4, а при 4-х подкидываниях можно добиться вероятности 1/16. Но против данного аргумента есть факт, что у нас мат. ожидание <3, значит, любой алгоритм, подкидывающий более 2 монет за итерации даст результат хуже.
есть решение с матожиданием 7/3, и бесконечным кол-вом бросков в худшем случае
Легко, кстати, доказать, что любое решение обязано иметь бесконечное ноличество подбрасываний в любом случае. Предположим обратное, т.е. что сделав n подбрасываний можно гарантировано выбрать один вариант из 3-х равновероятно. Любой исход наших подбрасываний выразится двоичным числом с n разрядами, например ОРРРООРОРР… РР, и каждой такой комбинации должен соответствовать единственный вариант. При этом все возможные результаты бросков (их 2^n, а вероятность получения каждого 1/2^n) распадутся на три группы, соответствующие каждая своему варианту. Понятно, что т.к. 2^n на три не делится при любом n, то группы нельзя выбрать содержащими одинаковое кол-во результатов, а значит а равновероятными.
вот так навскидку:
при трёх бросаниях получается 8 равновероятных вариантов,
из них в 25% случаев все три выпадают одинаково
в остальных 75% результаты двух бросаний совпадают друг с другом, и одно — отличается. номер этого бросания можно взять за выбираемый вариант.
варианты распределяются равномерно:
ооо переброс
оор 3
оро 2
орр 1
роо 1
рор 2
рро 3
ррр переброс
в худшем случае всегда бесконечное число бросаний,
потомучто есть ненулевая вероятность что монета будет падать всегда одной стороной и никакого распределения не даст.
при трёх бросаниях получается 8 равновероятных вариантов,
из них в 25% случаев все три выпадают одинаково
в остальных 75% результаты двух бросаний совпадают друг с другом, и одно — отличается. номер этого бросания можно взять за выбираемый вариант.
варианты распределяются равномерно:
ооо переброс
оор 3
оро 2
орр 1
роо 1
рор 2
рро 3
ррр переброс
в худшем случае всегда бесконечное число бросаний,
потомучто есть ненулевая вероятность что монета будет падать всегда одной стороной и никакого распределения не даст.
Хватит ровно двух подбрасываний. Для лучшего и худшего случаев.
Вводим матрицу состояний (states):
[[1, 2, 3, -1], [-1, 3, 2, 1], [2, 1, -1, 3]].
Нулевое значение из этой матрицы объявляем активным. Кидаем монету два раза и считаем сумму (attemptSum): для ОО – 0, для ОР – 1, для РО – 2, для РР – 3. Теперь если активное состояние с индексом attemptSum равно -1, то переводим активное состояние на одну позицию вправо, а если это не возможно, то опять берем нулевое значение. Возращаем активное состояние с индексом attemptSum.
Теперь замечание по матрице states. Ее крайне важно подобрать так, чтобы в следующем активном состоянии, на месте -1 появлялись различные цифры и одинаковое число раз, то есть состояний может быть больше, кратно 3, а вот такая матрица [[1, 2, 3, -1], [-1, 3, 2, 1], [1, 2, -1, 3]] не допустима.
Пример на JS:
jsfiddle.net/7e8Xt/
Вводим матрицу состояний (states):
[[1, 2, 3, -1], [-1, 3, 2, 1], [2, 1, -1, 3]].
Нулевое значение из этой матрицы объявляем активным. Кидаем монету два раза и считаем сумму (attemptSum): для ОО – 0, для ОР – 1, для РО – 2, для РР – 3. Теперь если активное состояние с индексом attemptSum равно -1, то переводим активное состояние на одну позицию вправо, а если это не возможно, то опять берем нулевое значение. Возращаем активное состояние с индексом attemptSum.
Теперь замечание по матрице states. Ее крайне важно подобрать так, чтобы в следующем активном состоянии, на месте -1 появлялись различные цифры и одинаковое число раз, то есть состояний может быть больше, кратно 3, а вот такая матрица [[1, 2, 3, -1], [-1, 3, 2, 1], [1, 2, -1, 3]] не допустима.
Пример на JS:
jsfiddle.net/7e8Xt/
Sign up to leave a comment.
Трехсторонняя монетка