[Gump]

Играют двое: первый пишет 15 чисел (любых, положительных)
Второй поднимает одну из 15ти бумажек и говорит, либо дальше, либо стоп игра. Возвращаться к бумажкам, которые уже посмотрел нельзя. Задача второго сказать стопигра на максимальном числе, написанном на этих 15 бумажках.

Какая наилучшая стратегия может быть в этой задачке и с какой вероятностью можно угадывать, что это число максимальное, пользуясь этой стратегией?

PS Видел, как в эту игру один человек (математически оч подкованный) в казино предлагает сыграть всем желающим с кэфом 1(если не угадает) к 5(если угадает).

[CLON]

Оптимальная стратегия - это наблюдение за мимикой "писавшего" числа. Очевдно, что писавший числа сам себя выдает.

Похоже, что кто-то очень хороший физиономист.

[Gump]

Сообщение от CLON писал пн, 03 сентября 2007 11:25

Оптимальная стратегия - это наблюдение за мимикой "писавшего" числа. Очевдно, что писавший числа сам себя выдает.

Похоже, что кто-то очень хороший физиономист.

Этим он тоже обладает, но интересует все-таки математическая сторона вопроса. Допустим игра проходит по интернету.

PS Забыл написать - все 15 чисел разные.

[CLON]

Предлагаю упростить задачу сведя её до задачи с ТРЕМЯ бумажками с числами.

Тогда, Открытие 1 и 2 бумажки обязательно?!

А открытие 3-ей в зависимости от того, число на какой бумажке больше:
1. Вариант:
1 Число > 2 Числа - тогда открываем 3-ю бумажку.

2. Вариант:
1 Число < 2 Числа - тогда говорим "стоп".

Вопрос: оптимальна ли данная стратегия?

[CLON]

Рассмотрим подробно ВСЕ возможные варианты для задачи с 3-мя бумажками (пусть числа по старшинству равны 1-2-3):
1. 1-2-3
2. 1-3-2
3. 2-1-3
4. 2-3-1
5. 3-1-2
6. 3-2-1

Итого ВСЕГО возможных 6 вариантов, причем 1-2-3 - это не цифры на бумажк, а порядок по страшинству (1-самая маленькое число, 3 - самое большое число).

Тогда:
1 - проигрыш, т.к. 2 < 3.
2 - выигрыш, т.к. 3 > 2.
3 - выигрыш, т.к. открыли все три бумажки и 3 > 2.
4 - выигрыш, т.к. 3 > 1.
5 - проигрыш, т.к. 3 > 2.
6 - проигрыш, т.к. 3 > 1.
Итого, получили вероятность выиграть против вероятности проиграть 50% на 50%.

Для 15 бумажек, стратегия должна быть аналогичной открываем первых 2 бумажки и продолжаем открывать до тех пор пока не получим наибольшую бумажку из ВСЕХ открытых.

[CLON]

В догонку:

При разработке оптимальной стратегии необходимо учесть выплаты по выигрышу и проигрышу, а их связать с количеством первоначально открываемых карт.

При соотношении 5 : 1 оптимально в начале открывать не 2 бумажки, а минимум три, а далее алгоритм скорее всего иммено такой, т.е. открываем бумажки до первой которая больше всех открытых.

ЗЫ: Думаю, что данную задачу можно решить программным путем, т.к. всего возможных комбинаций 1.308*10^12, т.е. число перестановок 15 чисел равно 15!.

Gump, а если играют игру многократно, то бумажки каждый раз переписывают или играют одними и теми же? Если одними и темиже, то оптимальная стратегия будет другой.

Думаю, придет Коровин и все решит!

[Gump]

Сообщение от CLON писал пн, 03 сентября 2007 12:06

Gump, а если играют игру многократно, то бумажки каждый раз переписывают или играют одними и теми же? Если одними и темиже, то оптимальная стратегия будет другой.

Конечно каждый раз переписываются.

Я сам еще детально не думал над этой задачей, но даже не видя как он играл в нее, сходу сказал, что стоп игра он говорит минимум с 3го открытия карты (а скорее всего минимум с 4го), хотя он начал там что-то рассказывать, что может остановить если уже в первое открытие увидит нереально большое число .

PS Мне просто стало интересно МО его игры

[CLON]

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

НО данную задачу проще всего решить программным путем, времени займет несколько минут.

Т.к. выплаты 1 к 5, то для получения +МО необходимо выигрывать не менее чем в 20% случаев, открыв три катры в начале и если карта с макисмальным числом не третья, то открываем до первой карты которая больше ВСЕХ уже открытых. При таком раскладе, МО > 0. А вот на сколько больше, можно промоделировать.

Да в программе, можно начать открывать с двух карт, и далее увеличивать до К, и получить оптимальное решение по МО игры.

[Cardinal]

не самое оптимальное решение таково.
с вер-ю 7/15 среди первых 7 чисел будет второе по величине.
с вер-ю 8/15 среди последних 8 чисел будет максимальное.

значит, если мы будем просматривать 7 чисел, запоминать наибольшее
и делать стоп, на первом же числе, которое больше запомненного,
то с вер-ю 56/225=0.2488 мы будем называть максимальное.
а это уже >1/6, что достаточно при данных условиях пари, чтобы быть в плюсе. Более строго эта задача решается через пределы и логарифмы, не помню как ))

[CLON]

Cardinal, ТЫ упускаешь из виду очень важный момент - требуется остановиться на максимальном числе!

Поэтому Твой метод - ТОЧНО не оптимален, т.к. Ты не можешь открыть 7 чисел, т.к. 7 число может быть минимальным из всех открытых, поэтому Тебе придеться открывать далее, до тех пор, пока не откроешь самое максимальное из всех открытых чисел.

Очевидно, что условие останова - именно Маскимальное число из всех открытых, причем должно быть открыто не мнее трех карт! Другими словами до 4-ой карты игрок будет доходить в 50% случаев, до 5 бумажки в 25%, до 6 бумажки в 12.5% и т.д. Исходя из этого и имея равномерное распределения перемешивания можно сделать аналитический расчет.

[Gump]

Сообщение от CLON писал пн, 03 сентября 2007 12:20

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

Брррр. Какой правильный выбор карт? Карты ты открываешь рандомно

Сообщение от CLON писал пн, 03 сентября 2007 12:06

Другими словами до 4-ой карты игрок будет доходить в 50% случаев, до 5 бумажки в 25%, до 6 бумажки в 12.5% и т.д

Это не правильно. Пусть загаданы числа от 1 до 15, вначале открыты 4, 7, 11. Вероятность открытия след числа выше 11ти равна 50%?

Сообщение от CLON писал пн, 03 сентября 2007 12:06

При разработке оптимальной стратегии необходимо учесть выплаты по выигрышу и проигрышу, а их связать с количеством первоначально открываемых карт.

Выплаты учитывать не надо. Про 5 к 1 я видимо зря написал.

Вопрос: какая стратегия оптимальна и какой справедливый кэф на выигрыш при этой стратегии

[tigra_7]

Если я ничего не напутал, то : пропускаем, первые пять и выбираем первое число, которое больше чем любые из этих пяти.

Сообщение от Цитата:

PS Видел, как в эту игру один человек (математически оч подкованный) в казино предлагает сыграть всем желающим с кэфом 1(если не угадает) к 5(если угадает).

Я правильно понял, что себе он отводит роль угадывающего? Я бы играл и с коэф 1 к 2 в этой роли .

[CLON]

Gump, читай внимательнее.

1. Речь идет о первоначально открываемых картах. Можно открыть одну карту и сказать стоп (это удовольствие будет стоить -60%), а можно открыть две карты (если К1 < К2 сказать стоп или К1 > К2, тянуть до первой которая больше К1), а можно открывать 3, 4 , 5 и т.д. карт. В зависимости от количества открываемых карт Меняется МО игры.

2. В примере из 3-х карт я показал, что в 50% случаев игрок проигрывает, а следовательно будет тянуть 4 карту. Если не понятно смотри пост выше. ПО аналогии для 4-х карт, в 25% случаев придеться открывать и 5 карту и т.д.

3. Выплаты надо учитывать обязательно, т.к. от них зависит МО игры.

4. Gump, напиши программу, которая генерует 15! перестановок и оттестируй свой алгоритм по ней - это самый точный метод, т.к. получишь в итоге абсолютно точное МО игры и стратегии.

5. Оптимизация игровой стратегии сведеться к одному: поиску начально открываемых карт с последующим догоном да максимума.

к tigra: с коэффициентом 1 : 2, ты точно вылетишь в трубу.

ЗЫ: Сейчас нет под рукой Делфи, но вечером постараюсь накидать программку для анализа и получения оптимальной стратегии.

[CorwinXX]

Сообщение от tigra писал пн, 03 сентября 2007 14:39

Если я ничего не напутал, то : пропускаем, первые пять и выбираем первое число, которое больше чем любые из этих пяти.

Угу. Вопрос в том, сколько чисел открыть (пропустить). Лень считать точно. На глазок (интуитивно) - 5 или 6, скорее 6.

[tigra_7]

Сообщение от CorwinXX писал пн, 03 сентября 2007 15:04

Угу. Вопрос в том, сколько чисел открыть (пропустить). Лень считать точно. На глазок (интуитивно) - 5 или 6, скорее 6.

Точно, если правильно помню, [количество карточек]/e.

[CLON]

Сообщение от CorwinXX писал пн, 03 сентября 2007 15:04

Угу. Вопрос в том, сколько чисел открыть (пропустить). Лень считать точно. На глазок (интуитивно) - 5 или 6, скорее 6.

С другой стороны, чем больше карт игрок открывает тем меньше его шанс остановиться на максимальной карте. Поэтому СРАЗУ открыть 5-6 карт, но мой взгляд, обойдется большими потерями в МО игрока.

Поэтому считаю, что оптимально открывать 3 карты и если К3 < K1 и К3 < K2, то открывать до тех пор пока вновь открытая карта не будет болше всех открытых карт до неё.

Интересно было бы получить график МО в зависимости от начально открытого количества карт К = 1 до 14.

[CLON]

Давайте прикинем МО игры при открытии:
1. 2-х карт.
2. 3-х карт.
3. 4-х карт.

Есть у кого-нибудь идеи как посчитать МО стратегии аналитически?

[Grey]

Это известная задача из теории оптимальной остановки случайных процессов. Иногда ее еще называют "выбор секретарши". Кому интересно, могут почитать популярную брошюрку об этой задаче: [Зарегистрироваться?].

Аннотация
Примерно 40 лет тому назад М. Гарднер придумал такую задачу: <В некотором царстве, в некотором государстве пришло время принцессе выбирать себе жениха. В назначенный день явились 1000 царевичей. Их построили в очередь в случайном порядке и стали по одному приглашать к принцессе. Про любых двух претендентов принцесса, познакомившись с ними, может сказать, какой из них лучше. Познакомившись с претендентом, принцесса может либо принять предложение (и тогда выбор сделан навсегда), либо отвергнуть его (и тогда претендент потерян: царевичи гордые и не возвращаются). Какой стратегии должна придерживаться принцесса, чтобы с наибольшей вероятностью выбрать лучшего?>.
В 1965 году формулировку этой задачи и её решение рассказал на своём семинаре Е. Б. Дынкин. Но его метод был необобщаем на другие варианты задачи: например, когда целью является выбор не наилучшего, а одного из трёх лучших. В таком виде задача была решена автором при помощи метода, который легко переносится и на ряд близких задач. Так из полушуточной задачи вырос новый раздел математики — т е о р и я о п т и м а л ь н о й о с т а н о в к и с л у ч а й н ы х п р о ц е с с о в.
Текст брошюры представляет собой обработку записи лекции, прочитанной автором 30 ноября 2002 года на Малом мехмате МГУ для школьников 9—11 классов (запись Ю. Л. Притыкина).
Брошюра рассчитана на широкий круг читателей: школьников, студентов, учителей.

[SunnyRay]

Всё правильно. В исходной задаче оптимально открывать 5 карт не глядя, дальше до первой, которая окажется больше всех предыдущих. При этом вероятность угадывания равна 0.3894, МО игры при выплате 5:1 аж 94.7%.

[CLON]

Сообщение от SunnyRay писал пн, 03 сентября 2007 16:08

Всё правильно. В исходной задаче оптимально открывать 5 карт не глядя, дальше до первой, которая окажется больше всех предыдущих. При этом вероятность угадывания равна 0.3894, МО игры при выплате 5:1 аж 94.7%.

SunnyRay, а можно огласить весь список, начиная от 2-х карт и до 14.

Заранее спасибо.