Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 54 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.
Автор Сообщение
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 10 авг 2017, 18:04 
Не в сети
Начинающий
Аватара пользователя
Зарегистрирован:
08 авг 2017, 05:45
Сообщений: 15
Откуда: Барнаул
Cпасибо сказано: 5
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Talanov писал(а):
В половине случаев с первого броска победитель не выявляется.

Не в половине, а а 2/3 случаев

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 10 авг 2017, 19:11 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
28 дек 2011, 16:16
Сообщений: 8239
Откуда: Дивногорск
Cпасибо сказано: 374
Спасибо получено:
1422 раз в 1297 сообщениях
Очков репутации: 230

Добавить очки репутацииУменьшить очки репутации
Talanov писал(а):
Предлагаю следующий алгоритм:
1. Участники ранжируются по росту и рассчитываются на первый, второй.
2. Бросается монета, если орёл остаются первые, если решка - вторые.
3. Если остался один участник, он объявляется победителем, в противном случае повторяются пункты 1 и 2.

Shadows писал(а):
Проверьте ваш алгоритм для 3-х участников.

Вероятность для каждого из 3-х участников стать победителем равна:

[math]\frac{1}{3}\cdot\frac{1}{2}+\frac{2}{3}\cdot\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{3}[/math].

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 10 авг 2017, 20:37 
Не в сети
Оракул
Зарегистрирован:
17 окт 2013, 20:46
Сообщений: 933
Cпасибо сказано: 65
Спасибо получено:
365 раз в 287 сообщениях
Очков репутации: 132

Добавить очки репутацииУменьшить очки репутации
Talanov, перестаньте уже! У Вас нет случйного события -"определение позиции", вы их по росту распределили.
Хотите так, пусть будет так, но только с помощью монеты определите кто будет номер 1, кто 2 и кто 3. Равновероятно.

(А если сможете, то продолжение бессмыслено)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 10 авг 2017, 22:19 
В сети
Профи
Зарегистрирован:
25 июл 2014, 13:28
Сообщений: 326
Cпасибо сказано: 34
Спасибо получено:
109 раз в 104 сообщениях
Очков репутации: 22

Добавить очки репутацииУменьшить очки репутации
Позвольте предложить вариант. Всей семьей думали над задачей. Мама предложила интересное решение. Самое приятное в нем то, что участников сортировать не требуется.
Сначала каждый бросает монету. В зависимости от результата он относится к группе "орел" или к группе "решка". Если одна из групп пуста, то монета бросается повторно, пока в каждой группе не будет хотя бы по одному участнику. Затем бросается монета (неважно кем, например, незаинтересованным судьей или честным участником), которая определяет группу тех, кто останется в игре. Игроки из другой группы выбывают. Затем розыгрыш повторяется среди оставшихся, пока не остается один участник — победитель. Все участники имеют равные шансы просто в силу симметрии.
Недостаток в том, что нельзя сказать, через сколько ходов игра завершится и завершится ли вообще. Впрочем, это не должно создать проблем на практике. Для ускорения игры можно договориться, что в случае неравных групп "орел" и "решка" большая из них автоматически выбывает.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 01:57 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
28 дек 2011, 16:16
Сообщений: 8239
Откуда: Дивногорск
Cпасибо сказано: 374
Спасибо получено:
1422 раз в 1297 сообщениях
Очков репутации: 230

Добавить очки репутацииУменьшить очки репутации
Я ведь не зря в самом начале спросил, каким образом участники будут пронумерованы. Если случайным образом, то монету можно уже не бросать. С вероятностью 1/n победителем назначается участник с номером 1.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Talanov "Спасибо" сказали:
Booker48
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 04:31 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
28 дек 2011, 16:16
Сообщений: 8239
Откуда: Дивногорск
Cпасибо сказано: 374
Спасибо получено:
1422 раз в 1297 сообщениях
Очков репутации: 230

Добавить очки репутацииУменьшить очки репутации
Space, всё хорошо, но можно улучшить для ускорения процесса. Из двух групп пусть выбывает большая, а бросок ведущего делается только при равенстве групп.
Прошу прощения, вы об этом упомянули.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 05:09 
Не в сети
Начинающий
Аватара пользователя
Зарегистрирован:
08 авг 2017, 05:45
Сообщений: 15
Откуда: Барнаул
Cпасибо сказано: 5
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Talanov писал(а):
Я ведь не зря в самом начале спросил, каким образом участники будут пронумерованы. Если случайным образом, то монету можно уже не бросать. С вероятностью 1/n победителем назначается участник с номером 1.

В том то и дело, что результат игры не должен зависеть от того, как будут пронумерованы участники. Ибо изначально у нас есть неупорядоченное множество и мы не можем взять и выбрать случайного, так как генератора случайных чисел из n у нас нет. Есть генератор (0 или 1). Если с его помощью нумеровать участников, то задача математически сведется к варианту описанному swan:
swan писал(а):
В целом алгоритм такой:
1. кодируете n чисел m битами [math]2^{m-1}<n\leqslant 2^m[/math]
2. Производите m бросков монеты
3. Если полученная серия соответствует одному из чисел (0-решка, 1 - орел или наоборот), то соответствующий человек объявляется победителем.
Если нет - переходим к п.2


Talanov проведите уже эксперимент с тремя участника. Вы увидите, что второй будет выигрывать чаще. Т.е. результат игры зависит от способа нумерации, а должен зависеть от самой игры. А если нумерация - это часть игры, то это тоже самое, что и у swan, просто сложнее (избыточнее).

Как вариант, чтобы уйти от противоречия, можно уточнить условия задачи:
Есть n участников, пронумерованных от 1 до n (они построены в ряд по росту, первый - самый высокий). Нужно среди них выбрать одного победителя с помощью простой монеты. Выбор победителя должен быть случайным (для каждого участника вероятность выигрыша должна быть одинакова) . Как это можно сделать?

Хотя и тут можно придраться. Вот вам решение в духе Нильса Бора:
Нужно выстроить всех участников в идеально круглый хоровод и бросить монету с высоты 100 м ровно в центр. Участник, ближе к которому упадет монета, победил.
:D1

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю sibedir "Спасибо" сказали:
Shadows
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 07:45 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
28 дек 2011, 16:16
Сообщений: 8239
Откуда: Дивногорск
Cпасибо сказано: 374
Спасибо получено:
1422 раз в 1297 сообщениях
Очков репутации: 230

Добавить очки репутацииУменьшить очки репутации
sibedir, это было бы так, если бы второй участник назначался ведущим авторитарно, но при случайном построении шансы стать вторым одинаковы для всех трёх участников.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 08:26 
Не в сети
Начинающий
Аватара пользователя
Зарегистрирован:
08 авг 2017, 05:45
Сообщений: 15
Откуда: Барнаул
Cпасибо сказано: 5
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Я пытался вот что сказать: Вы включаете нумерацию участников в процесс игры.
Дайте полный алгоритм вашей игры (с учетом нумерации) и мы посчитаем вероятность.

Еще раз. Задача: Выбрать случайного участника используя монету (1 или 2, 0 или 1, орёл или решка) НЕЗАВИСИМО от начального их порядка.

Или так: Есть генератор случайного бита (0 или 1). Дать алгоритм построения случайного натурального числа меньше заданного N.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Выбор победителя с помощью монеты
СообщениеДобавлено: 11 авг 2017, 11:06 
Не в сети
Оракул
Зарегистрирован:
17 окт 2013, 20:46
Сообщений: 933
Cпасибо сказано: 65
Спасибо получено:
365 раз в 287 сообщениях
Очков репутации: 132

Добавить очки репутацииУменьшить очки репутации
Конечно, правильных алгоритмов можно придумать много. И все они будут иметь недостак - отсутствия гарантиранного время работы при [math]n\ne 2^k[/math]. Алгоритм Space - тоже, насколько я понял, без лишних усложнений, кто забил гол (выпала решка), продолжает в следующий круг
Talanov писал(а):
но можно улучшить для ускорения процесса. Из двух групп пусть выбывает большая
Для улучшения (ускорения) процесса все таки пусть будет меньшая.

Но мат. ожидание количества бросков у алгоритм swan намного меньше. При больших n, в худшем случае (когда [math]n=2^k+1[/math]
и вероятность повтора игры примерно 1/2)

[math]2\lceil\log_2 n\rceil[/math]

А у другого алгоритма, примерно [math]2n[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Shadows "Спасибо" сказали:
sibedir, venjar
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 54 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Выбор с возвращением

в форуме Теория вероятностей

KsushaSha

1

57

15 апр 2017, 20:13

Выбор с возвращением

в форуме Теория вероятностей

missb

9

376

08 окт 2014, 19:02

Бросание монеты

в форуме Теория вероятностей

sonorthie

15

261

23 июн 2017, 23:44

Выбор с возвращением

в форуме Теория вероятностей

andrey546

28

734

17 окт 2013, 16:54

Задача про монеты

в форуме Теория вероятностей

Evrica

4

439

25 апр 2013, 10:30

Задача про монеты

в форуме Начала анализа и Другие разделы школьной математики

Elephant

6

369

12 ноя 2014, 14:54

Выбор без возвращения

в форуме Теория вероятностей

mad_math

2

45

17 май 2017, 13:32

Задача про монеты

в форуме Теория вероятностей

Andrew_

2

56

09 апр 2017, 15:17

Монеты и сундуки

в форуме Комбинаторика и Теория вероятностей

rafael_

2

154

27 ноя 2016, 02:23

Выбор метода

в форуме Исследование операций и Задачи оптимизации

Ivann

0

138

24 окт 2015, 16:29


Часовой пояс: UTC + 4 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: Google [Bot] и гости: 27


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved