Версия для печати темы

Автор: alan 1.8.2015, 18:07

Задумался (признаться, не сильно)) ) над такой задачей:

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


Решения не знаю.

Автор: Loban 1.8.2015, 19:17

Вы не верите в симметрию?

Автор: Owen 1.8.2015, 19:37

Напрашивается 50, конечно.
Для 1 и 2 компов это вроде выигрыш.

Автор: Loban 1.8.2015, 19:37

Может лучше, угадывают?

Автор: netvoe 1.8.2015, 21:42

когда то задавал обратную задачу - Жребий.
Ведущий загадывает число 1-100. Остальные пикапят числа в этом же диапозоне. Проигрывает тот, кто назовет число ближайшее к загаданному. Тогда мне подтвердили идею, что самый оптимальный вариант для игроков называть крайние числа - 1 и 100. Эта задача кажется обратной...

Автор: Breghnev 1.8.2015, 23:45

Задача не кажется обратной. Она очевидно обратная и есть. Только вот ответ отнюдь не очевиден, в отличие от вашего случая.

Автор: alan 2.8.2015, 10:32

Верю. А что тут симметрия говорит? Максимум то, что если Х это оптимум, то и 100-Х будет оптимумом. Так чему равен Х? А точнее "равнЫ";)

Автор: BAS14 2.8.2015, 20:33

Попытался решить матанализом. Составил функцию вероятности выигрыша в зависимости от называемого числа и количества компьютеров-противников. Остается найти точку ее максимума. Для 1 и 2 компов она действительно получается в середине отрезка (т.е. 50 в данном случае). Но вот при достаточно большом числе компов середина отрезка, похоже, уже не максимум вероятности выигрыша, а наоборот - локальный минимум, а где же максимум - неочевидно. Хотя там такая куча формул получилась, что мог и ошибиться где-то.

P.S. Кстати числа целые или действительные?

Автор: 0 2.8.2015, 21:27

А если пойти дальше?
Не обязательно от середины отражать.
Можно отразить от 25. (верхную половину можно не рассматривать из-за уже замеченной симметрии)
Получим что если Х<25 это оптимум то 50-X тоже оптимум. Обратное не верно из-за возможности выигрыша если загаданное число >50

Автор: BAS14 3.8.2015, 11:20

Не думаю, что это утверждение верно. Называя Х<25 вместо 50-Х мы действительно уменьшаем свои шансы угадать число, если оно >50 (правда не до нуля, т.к. компы все еще могут проиграть, назвав еще меньшие числа), но зато получаем дополнительную возможность выигрыша, если загаданное число меньше нашего названного или достаточно близко к нему, а компы назовут >50. Правда навскидку вероятность первой ситуации представляется больше второй (хотя это еще посчитать надо), но это уже исключает возможность отражения относительно 25 (пусть и в одну сторону) - по одну и другую сторону от 25 возможности разные.

Автор: alan 3.8.2015, 20:44

Целые. Но для действительных результат тоже интресен.

Автор: Breghnev 3.8.2015, 21:29

Есть ощущение, что 50 действительно максимизирует шанс выигрыша, но преимущество такого выбора должно существенно снижаться с ростом количества компьютеров, с которыми мы соревнуемся. Будет неплохо, если кто-то посчитает, например, методами программирования шанс выигрыша при выборе 10, 20, 30, 40 и 50 в качестве стратегии для количества компьютеров от 1 до 5 хотя бы (а лучше для 10). Думаю, можно будет наблюдать устойчивую тенденцию и сделать определённые выводы. Нужно только определиться, что будет в случае, если победителей несколько. Считать ли это за победу (если мы в числе победителей) или нет. Впрочем, можно рассмотреть оба варианта. Пусть машина вычисляет :-)

Автор: BAS14 3.8.2015, 23:22

Может сначала для действительных рассмотреть? Там задача попроще кажется как минимум по 4 причинам:
1) не важно, какой отрезок брать, поэтому можно взять [0;1] и не мучаться с нормированием;
2) не нужно рассматривать случаи совпадения названного числа с загаданным или с одним из названных компами (бесконечно малая вероятность);
3) непрерывность позволяет использовать методы матанализа (дифференцирование и интегрирование);
4) в случае целых чисел выражения для вероятности выигрыша вроде как сводятся к сумме N-х степеней, которую сложно свернуть в отличие от ее непрерывного аналога - интегрирования функции x^N.
Я начал решать для случая действительных чисел, вывел в явном виде формулу для вероятности выигрыша у N компов в зависимости от названного числа, но максимум в общем виде не смог найти (могу выписать эту формулу сюда или кому-нибудь в ЛС, если интересно или для проверки, вдруг накосячил где-то).
С целыми я вообще пас.

Автор: BAS14 4.8.2015, 16:04

Похоже дорешал задачу для действительных чисел. Для 1,2,3,4 компов максимум вероятности выигрыша в середине отрезка. А вот если компов 5 или больше, в середине будет локальный минимум, а для максимума получается уравнение, корни которого вряд ли выражаются в общем виде, но это не такая большая проблема, т.к. их нетрудно подобрать численно даже в экселе. Например, для 5 компов вероятность выиграть, назвав середину отрезка, получается примерно 0,1797, а максимум будет в точке, делящей отрезок примерно как 3:7, там вероятность около 0,1829. Это все, конечно, при условии, что я правильно вывел формулу вероятности выигрыша, но я ее вывел двумя способами - интегрированием и более простыми рассуждениями, получилось одинаково.

Автор: Loban 5.8.2015, 16:35

Эт точно, погорячился.
При 5 компах на 11 точках у меня получилось в средней точке 0.267, а максимум в соседних - 0.269.
Правда, 11 это не 101. Но может это не так и важно?

Автор: Breghnev 5.8.2015, 18:21

Правильно я понял, что для 5 компов вероятность выигрыша при выборе середины отрезка у BAS14 получилась 0.18, а у Loban при тех же условиях - 0.267?

Автор: BAS14 5.8.2015, 20:06

Не при тех же условиях. Насколько я понимаю, Loban считал для случая целых точек от 0 до 10, т.е. всего 11 вариантов выбора числа. Исходная задача ставилась для 101 варианта. А я считал для непрерывного случая, когда выбирать можно не только целые числа, а любые действительные из данного отрезка. Т.е. я решал немного не ту задачу, но по идее это должен быть предельный случай этой задачи при стремлении количества точек к бесконечности. Такое большое расхождение результатов для дискретного случая с 11 точками и непрерывного может объясняться тем, что 11 не такое большое число, может быть, если взять оригинальные 101 - результаты будут лучше соответствовать. Вообще для непрерывного случая вероятность выиграть при выборе середины получается 1/(N+1)+N/((N+1)*2^(N+1)), т.е. при хоть сколько-нибудь больших N лишь ненамного больше 1/(N+1), которые получатся, если называть число совершенно наугад, как это делают компы. Но примечательно, что середина таки не является лучшим вариантом, хоть и разница в вероятности между серединой и оптимальным выбором невелика. И что именно для 5 компов так проявилось, как и в непрерывном случае, хотя казалось бы, непонятно, что кардинально может отличаться именно для 5 компов.

Автор: Loban 5.8.2015, 20:09

Нет.
У BAS14 решение для действительных чисел, у меня для целых /всего-то для N=11/. Чем больше N, тем ближе к 0.18. Если никто не ошибся.
Но для меня интересен сам факт того, что средняя точка - не всегда решение.

Автор: Loban 8.8.2015, 9:39

Несложно оказалось посчитать и для 101 точки.
Для 5 компов в т. 51 - 0.18998, в т. 31,71 - 0.19281.

Автор: BAS14 21.8.2015, 18:45

Рассмотрел для действительных чисел, что происходит при стремлении числа компов N к бесконечности.
Оказывается, при достаточно большом N при выборе середины отрезка вероятность выигрыша ~1/(N+1), т.е. назвать середину при большом N - практически все равно что самому назвать случайное число из этого же отрезка, подобно компам - вероятность выигрыша практически такая же (в пределе - такая же).
А вот оптимальным выбором будет разделить отрезок в отношении примерно 2 к N (т.е. для отрезка [0;1] назвать 2/(N+2) или N/(N+2)), в этом случае вероятность выигрыша ~(1+1/(2*e^2))/(N+1), т.е. больше примерно на 6,8% (в пределе, реально - еще чуть больше). Парадоксальный результат - чем больше N, тем ближе к концу отрезка нужно выбирать число.

Автор: WildKOT 12.9.2015, 13:05

Нужно уточнить условия задачи:

Играет ли компьютер оптимальным образом?
Если да, то стратегия выбора будет сводиться к функции распределения вероятности выбрать число.
То есть надо копать в строну теории игр.
Если выбрать оптимальную стратегию в виде числа, то компьютер её доминирует легко.

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

Автор: BAS14 12.9.2015, 13:14

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