Еще игра!
31 марта 2008 в 06:06
4892
20
По утверждению Партизана, он придумал эту задачку лет тридцать назад. Не удивлюсь, если так оно и есть.
А игра такая. Берем сто бумажек. Вы пишете на них любые числа из диапазона от 1 до миллиона. Перемешиваете все бумажки.
Теперь я наудачу тяну бумажки из кучи и смотрю записанное число. Моя задача — найти число самое старшее. В какой-то момент я прочту бумажку и скажу, что это число самое старшее. Причем если я бумажку отложил, то вернуться к ней уже не могу.
Понятно, что во-первых, я могу ошибочно назвать число старшим, поскольку в оставшейся куче может оказаться более крупное. А во-вторых, могу ошибочно отложить самое старшее число и продолжить тянуть бумажки, уже «вмертвую».
Ну собственно и все. Берусь угадать число самое старшее. Каким ответите? Кто укажет выгодную стратегию?
А игра такая. Берем сто бумажек. Вы пишете на них любые числа из диапазона от 1 до миллиона. Перемешиваете все бумажки.
Теперь я наудачу тяну бумажки из кучи и смотрю записанное число. Моя задача — найти число самое старшее. В какой-то момент я прочту бумажку и скажу, что это число самое старшее. Причем если я бумажку отложил, то вернуться к ней уже не могу.
Понятно, что во-первых, я могу ошибочно назвать число старшим, поскольку в оставшейся куче может оказаться более крупное. А во-вторых, могу ошибочно отложить самое старшее число и продолжить тянуть бумажки, уже «вмертвую».
Ну собственно и все. Берусь угадать число самое старшее. Каким ответите? Кто укажет выгодную стратегию?
Если ты не знаешь распределение чисел на бумажках...
Кто сможет указать стратегию?
Можем сыграть )
Делим всю кучу на две равные части.
Вопрос. Какова вероятность, что числа N1 и N2 окажутся в разных кучах?
1. Делим кучу на две равные части. 2.Переворачиваем всю первую часть до конца и запоминаем старшее число из увиденных.
3. Переходим ко второй части.
4. Как только увидим число, старше самого старшего из первой части, говорим"Стоп!"
Мы нашли самое старшее число во всей куче.
Что скажете?
Пересчитал сам, получилась вероятность того, что мы угадаем максимальное число p=0.349
Кто-нибудь найдёт оптимальное количество бумажек в первой куче?
В этом случае вероятность угадывания максимального числа р=0.371.
В текстовом варианте тяжеловато писать сложные формулы, но попробую описать вывод функции зависимости вероятности угадывания от размера первой кучи:
Пусть Х - число бумажек в первой куче.
Обозначим макс. число за 100, следующее - 99 итд.
Рассмотрим все варианты наибольшего числа в первой куче. Сумма их вероятностей и будем искомой величиной.
Старшее число в первой куче - 100. Вероятность этого состояния р=x/100.
Очевидно, в этом случае мы не угадываем.
Итерация 1.
Старшее число в первой куче - 99. Вероятность этого состояния
р=(x/100) * (100-x)/99)
В этом случае мы угадываем макс. число из второй кучи в 100 %. p2=1.
Итерация 2.
Старшее число в первой куче - 98. Вероятность этого состояния
р=(x/100) * (100-x)*(99-x)/(99*98))
В этом случае мы угадываем макс. число из второй кучи в 50 %. p2=1/2.
Перемножив эти вероятности, получим
р=(x/100) * (100-x)*(99-x)/(99*98)) * (1/2)
Преобразовав это выражение, получим
р=(x/2) * (99-2)!*(100-x)! / (100! * (100-2-х)!)
Заметим, цифра 2 в формуле является номером итерации.
В общем виде формула для i-ой итерации будет выглядеть так:
р=(x/i) * (99-i)!*(100-x)! / (100! * (100-i-х)!).
Выше по тексту мы писали, что искомая функция есть произведение вероятностей вариантов, всего вариантов 100-Х.
Следовательно, искомая функция
F(x) = Сумма [i=1, 100-x] { (x/i) * (99-i)!*(100-x)! / (100! * (100-i-х)!) }
Нахождение максимума этой функции я осуществил банальным перебором вариантов в Экселе.
Конечно, мог накосячить в расчётах, но идея, думаю, ясна.