Забавная задачка, для интервью сгодится

[spamsink]

Играют двое. Каждый получает случайное число, равномерно распределенное между 0 и 1. Каждый имеет право выбросить полученное число и получить новое с тем же распределением, ничего не зная о числе, полученном противником или его действиях. Выигрывает тот, у кого оказалось большее число. Найти оптимальную стратегию.

Комменты, естественно, скринятся.

(Я уже послал свое решение, Upd: которое, похоже, оказалось неверным.)

Комменты открыты.

Comments

[gmz.livejournal.com]

Эта не та же задача, что про остановку в выборе невесты?

[spamsink]

Не вижу сходства. Заменить число можно только однажды.

[gmz.livejournal.com]

Значит я не понял условия.

[spamsink]

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

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

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

[gmz.livejournal.com]

Первое, что приходит в голову: вторую попытку делать с вероятностью 1-x, где х - первое число.

[spamsink]

Оказывается, это неверно, судя по симуляции. Мое решение (просить второе число, если первое меньше sqrt(0.5)), как мне казалось, было эквивалентно твоему, но и оно выигрывает у твоего.

[gmz.livejournal.com]

А ты знаешь про нетранзитивные игральные кости? Может здесь такая же фигня?

[spamsink]

Нет, здесь ответ "просить новое, если меньше 1/ф", но почему именно, я пока не понял.

Ответ на ответ

[spamsink]

Это, конечно, удовлетворяет условию "красиво - значит правильно", но почему это правильно? Есть ли более удобные эквивалентные стратегии?

[rkatsyv.livejournal.com]

Все наверное не так просто, но мне кажется что оптимальная стратегия - при первом числе < 0.5 просить второе, а при > 0.5 оставлять первое. Шансы улучшить результат в первом случае > 50%, а во втором < 50%.

[spamsink]

Все действительно не так просто.

[rkatsyv.livejournal.com]

ОК. Но с этим утверждением ты согласен: Шансы улучшить результат в первом случае > 50%, а во втором < 50%?

[spamsink]

Это верно, но ответа это не дает.

[siludin.livejournal.com]

Если бы нужно было максимизировать мат. ожидание, то действительно, такая стратегия была бы оптимальна и давала бы что-то вроде 5/8, если не ошибаюсь.

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

Кстати, в исходном тексте говорится не об оптимальной стратегии, а о стратегии, которая _гарантирует_ выигрыш в >50% случаев. Разница есть, поскольку критерии оптимизации могут быть разными.

[spamsink]

В исходном тексте >= 50% случаев, а это как раз и есть оптимальная стратегия: она дает ровно 50%, если и противник пользуется ею же, или более 50% во всех остальных случаях.

[ilvyanyatka.livejournal.com]

щаг 1 - сравнивать с 0.5
шаг 2 и далее - сравнивать с числом соперника на предыдущем шаге. (Если наше меньше - просить другое)

[spamsink]

Это интересный вариант (в пределе действительно гарантирующий 50%, как мне кажется), но как быть, если игроки сдают бумажки с числами судье, и число соперника им не сообщают?

[yigal_s]

странно, вроде нужно получать новое, если предыдущее меньше, чем sqrt(1/2).

Но попытка проверить ответ, устроив соревнование двух стратегий на компьютере ничего хорошего не дала. То ли генератор случайных чисел подвёл, то ли что-то посчитал неправильно.

[spamsink]

Я послал именно это решение (потому что оно дает максимальную медиану), но выигрыша оно, похоже, действительно не гарантирует, судя по симуляции. 0.6 оказывается лучше.

[yigal_s]

Всегда полезно парой слов переброситься:

нашел у себя ошибку.

[yigal_s]

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

[yigal_s]

готово. Ответ - золотая пропорция

( -1+sqrt(5) ) / 2

но увы, тупое решение на пол-cтраницы, никакой изящности достигнуть не удалось.

[siludin.livejournal.com]

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

[spamsink]

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

[siludin.livejournal.com]

Мой ответ - фи-маленькое, золотое сечение, (sqrt(5)-1)/2

Однако элегантного решения я не нашел. Просто тупо рассмотрел что происходит, если стратегия А играет со стратегией B. Нарисовал на квадратиках линии и подсчитал площади, таким образом долучил формулу P(A,B). Потом нашел экстремум, через dP/dA и dP/dB, и так можно показать, что фи дает выигрыш против любой другой стратегии. Смешанные стратегии тоже не помогают.

Послал им вчера ответ.

[syarzhuk.livejournal.com]

(до чтения комментариев и хождения по ссылке; в предположении, что менять число можно не более одного раза)
Получив число p₁, самостоятельно сгенерировать так же распределённое число p (например, функцией Random). Если p > p₁, попросить заменить p₁ на новое p₂

[spamsink]

Этот способ (или эквивалентный ему - просить, когда число меньше, чем sqrt(2)/2, чем достигается максимум медианы распределения) - тот, на который все ловятся.