Угадывание |
Добро пожаловать, гость ( Вход | Регистрация )
Публикующим:
1. Задачу можно опубликовать двумя способами:
- создав для нее отдельную тему с информативным названием;
- добавив задачу в готовый сборник (например «Бескрылки», «Мини-задачи», «Вопросы ЧГК») или создав свой (например, «Загадки от /для Светы»).
2. Если вы публикуете задачу, решение которой не знаете, напишите об этом. По умолчанию считается, что вам известен правильный ответ и вы готовы проверять других игроков.
Решающим:
1. В темах запрещается писать ответы и подсказки, если возможность открытого обсуждения не оговорена отдельно (в случае открытого обсуждения для текста следует использовать цвет фона или белый, оставляя другим игрокам возможность самостоятельного решения).
2. Правильность решения можно проверить, написав личное сообщение автору.
Угадывание |
alan |
1.8.2015, 18:07
Сообщение
#1
|
zzz... Группа: Администраторы Braingames Сообщений: 13 480 Регистрация: 23.2.2009 Из: Симферополь Пользователь №: 13 114 |
Задумался (признаться, не сильно)) ) над такой задачей:
Представьте что вы играете в лотерею против N компьютеров. Вам нужно угадать загаданное случайным образом число от 0 до 100. Число также угадывают компы, называя случайное число от 0 до 100. Вы победите, если ваше число окажется ближе всех к загаданному. Какое число вам лучше всего назвать? Все распределения равномерные. Решения не знаю. |
Loban |
1.8.2015, 19:17
Сообщение
#2
|
Активный участник Группа: Пользователи Braingames Сообщений: 633 Регистрация: 1.12.2008 Пользователь №: 11 245 |
Вы не верите в симметрию?
|
Owen |
1.8.2015, 19:37
Сообщение
#3
|
Kорифей Группа: Администраторы Braingames Сообщений: 2 817 Регистрация: 6.3.2013 Пользователь №: 43 989 |
Напрашивается 50, конечно.
Для 1 и 2 компов это вроде выигрыш. |
Loban |
1.8.2015, 19:37
Сообщение
#4
|
Активный участник Группа: Пользователи Braingames Сообщений: 633 Регистрация: 1.12.2008 Пользователь №: 11 245 |
|
netvoe |
1.8.2015, 21:42
Сообщение
#5
|
Бывалый Группа: Пользователи Braingames Сообщений: 1 081 Регистрация: 22.4.2007 Из: Tampa, FL Пользователь №: 216 |
Напрашивается 50, конечно. Для 1 и 2 компов это вроде выигрыш. когда то задавал обратную задачу - Жребий. Ведущий загадывает число 1-100. Остальные пикапят числа в этом же диапозоне. Проигрывает тот, кто назовет число ближайшее к загаданному. Тогда мне подтвердили идею, что самый оптимальный вариант для игроков называть крайние числа - 1 и 100. Эта задача кажется обратной... |
Breghnev |
1.8.2015, 23:45
Сообщение
#6
|
Участник Группа: Пользователи Braingames Сообщений: 113 Регистрация: 8.5.2008 Из: Йошкар-Ола Пользователь №: 7 813 |
когда то задавал обратную задачу - Жребий. Ведущий загадывает число 1-100. Остальные пикапят числа в этом же диапозоне. Проигрывает тот, кто назовет число ближайшее к загаданному. Тогда мне подтвердили идею, что самый оптимальный вариант для игроков называть крайние числа - 1 и 100. Эта задача кажется обратной... Задача не кажется обратной. Она очевидно обратная и есть. Только вот ответ отнюдь не очевиден, в отличие от вашего случая. Сообщение было отредактировано Breghnev: 1.8.2015, 23:45 |
alan |
2.8.2015, 10:32
Сообщение
#7
|
zzz... Группа: Администраторы Braingames Сообщений: 13 480 Регистрация: 23.2.2009 Из: Симферополь Пользователь №: 13 114 |
|
BAS14 |
2.8.2015, 20:33
Сообщение
#8
|
Активный участник Группа: Модераторы BrainGames Сообщений: 494 Регистрация: 25.7.2014 Из: Псков Пользователь №: 50 487 |
Попытался решить матанализом. Составил функцию вероятности выигрыша в зависимости от называемого числа и количества компьютеров-противников. Остается найти точку ее максимума. Для 1 и 2 компов она действительно получается в середине отрезка (т.е. 50 в данном случае). Но вот при достаточно большом числе компов середина отрезка, похоже, уже не максимум вероятности выигрыша, а наоборот - локальный минимум, а где же максимум - неочевидно. Хотя там такая куча формул получилась, что мог и ошибиться где-то.
P.S. Кстати числа целые или действительные? Сообщение было отредактировано BAS14: 2.8.2015, 20:35 |
0 |
2.8.2015, 21:27
Сообщение
#9
|
Охгдеж Группа: Пользователи Braingames Сообщений: 1 335 Регистрация: 26.3.2009 Пользователь №: 13 618 |
Верю. А что тут симметрия говорит? Максимум то, что если Х это оптимум, то и 100-Х будет оптимумом. Так чему равен Х? А точнее "равнЫ";) А если пойти дальше? Не обязательно от середины отражать. Можно отразить от 25. (верхную половину можно не рассматривать из-за уже замеченной симметрии) Получим что если Х<25 это оптимум то 50-X тоже оптимум. Обратное не верно из-за возможности выигрыша если загаданное число >50 |
BAS14 |
3.8.2015, 11:20
Сообщение
#10
|
Активный участник Группа: Модераторы BrainGames Сообщений: 494 Регистрация: 25.7.2014 Из: Псков Пользователь №: 50 487 |
А если пойти дальше? Не обязательно от середины отражать. Можно отразить от 25. (верхную половину можно не рассматривать из-за уже замеченной симметрии) Получим что если Х<25 это оптимум то 50-X тоже оптимум. Обратное не верно из-за возможности выигрыша если загаданное число >50 Не думаю, что это утверждение верно. Называя Х<25 вместо 50-Х мы действительно уменьшаем свои шансы угадать число, если оно >50 (правда не до нуля, т.к. компы все еще могут проиграть, назвав еще меньшие числа), но зато получаем дополнительную возможность выигрыша, если загаданное число меньше нашего названного или достаточно близко к нему, а компы назовут >50. Правда навскидку вероятность первой ситуации представляется больше второй (хотя это еще посчитать надо), но это уже исключает возможность отражения относительно 25 (пусть и в одну сторону) - по одну и другую сторону от 25 возможности разные. |
alan |
3.8.2015, 20:44
Сообщение
#11
|
zzz... Группа: Администраторы Braingames Сообщений: 13 480 Регистрация: 23.2.2009 Из: Симферополь Пользователь №: 13 114 |
QUOTE P.S. Кстати числа целые или действительные? Целые. Но для действительных результат тоже интресен. |
Breghnev |
3.8.2015, 21:29
Сообщение
#12
|
Участник Группа: Пользователи Braingames Сообщений: 113 Регистрация: 8.5.2008 Из: Йошкар-Ола Пользователь №: 7 813 |
Есть ощущение, что 50 действительно максимизирует шанс выигрыша, но преимущество такого выбора должно существенно снижаться с ростом количества компьютеров, с которыми мы соревнуемся. Будет неплохо, если кто-то посчитает, например, методами программирования шанс выигрыша при выборе 10, 20, 30, 40 и 50 в качестве стратегии для количества компьютеров от 1 до 5 хотя бы (а лучше для 10). Думаю, можно будет наблюдать устойчивую тенденцию и сделать определённые выводы. Нужно только определиться, что будет в случае, если победителей несколько. Считать ли это за победу (если мы в числе победителей) или нет. Впрочем, можно рассмотреть оба варианта. Пусть машина вычисляет :-)
Сообщение было отредактировано Breghnev: 3.8.2015, 21:31 |
BAS14 |
3.8.2015, 23:22
Сообщение
#13
|
Активный участник Группа: Модераторы BrainGames Сообщений: 494 Регистрация: 25.7.2014 Из: Псков Пользователь №: 50 487 |
Целые. Но для действительных результат тоже интресен. Может сначала для действительных рассмотреть? Там задача попроще кажется как минимум по 4 причинам: 1) не важно, какой отрезок брать, поэтому можно взять [0;1] и не мучаться с нормированием; 2) не нужно рассматривать случаи совпадения названного числа с загаданным или с одним из названных компами (бесконечно малая вероятность); 3) непрерывность позволяет использовать методы матанализа (дифференцирование и интегрирование); 4) в случае целых чисел выражения для вероятности выигрыша вроде как сводятся к сумме N-х степеней, которую сложно свернуть в отличие от ее непрерывного аналога - интегрирования функции x^N. Я начал решать для случая действительных чисел, вывел в явном виде формулу для вероятности выигрыша у N компов в зависимости от названного числа, но максимум в общем виде не смог найти (могу выписать эту формулу сюда или кому-нибудь в ЛС, если интересно или для проверки, вдруг накосячил где-то). С целыми я вообще пас. Сообщение было отредактировано BAS14: 3.8.2015, 23:25 |
BAS14 |
4.8.2015, 16:04
Сообщение
#14
|
Активный участник Группа: Модераторы BrainGames Сообщений: 494 Регистрация: 25.7.2014 Из: Псков Пользователь №: 50 487 |
Похоже дорешал задачу для действительных чисел. Для 1,2,3,4 компов максимум вероятности выигрыша в середине отрезка. А вот если компов 5 или больше, в середине будет локальный минимум, а для максимума получается уравнение, корни которого вряд ли выражаются в общем виде, но это не такая большая проблема, т.к. их нетрудно подобрать численно даже в экселе. Например, для 5 компов вероятность выиграть, назвав середину отрезка, получается примерно 0,1797, а максимум будет в точке, делящей отрезок примерно как 3:7, там вероятность около 0,1829. Это все, конечно, при условии, что я правильно вывел формулу вероятности выигрыша, но я ее вывел двумя способами - интегрированием и более простыми рассуждениями, получилось одинаково.
|
Loban |
5.8.2015, 16:35
Сообщение
#15
|
Активный участник Группа: Пользователи Braingames Сообщений: 633 Регистрация: 1.12.2008 Пользователь №: 11 245 |
Верю. А что тут симметрия говорит? Максимум то, что если Х это оптимум, то и 100-Х будет оптимумом. Так чему равен Х? А точнее "равнЫ";) Эт точно, погорячился. При 5 компах на 11 точках у меня получилось в средней точке 0.267, а максимум в соседних - 0.269. Правда, 11 это не 101. Но может это не так и важно? Сообщение было отредактировано Loban: 5.8.2015, 16:36 |
Breghnev |
5.8.2015, 18:21
Сообщение
#16
|
Участник Группа: Пользователи Braingames Сообщений: 113 Регистрация: 8.5.2008 Из: Йошкар-Ола Пользователь №: 7 813 |
Правильно я понял, что для 5 компов вероятность выигрыша при выборе середины отрезка у BAS14 получилась 0.18, а у Loban при тех же условиях - 0.267?
|
BAS14 |
5.8.2015, 20:06
Сообщение
#17
|
Активный участник Группа: Модераторы BrainGames Сообщений: 494 Регистрация: 25.7.2014 Из: Псков Пользователь №: 50 487 |
Правильно я понял, что для 5 компов вероятность выигрыша при выборе середины отрезка у BAS14 получилась 0.18, а у Loban при тех же условиях - 0.267? Не при тех же условиях. Насколько я понимаю, 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
Сообщение
#18
|
Активный участник Группа: Пользователи Braingames Сообщений: 633 Регистрация: 1.12.2008 Пользователь №: 11 245 |
Правильно я понял, что для 5 компов вероятность выигрыша при выборе середины отрезка у BAS14 получилась 0.18, а у Loban при тех же условиях - 0.267? Нет. У BAS14 решение для действительных чисел, у меня для целых /всего-то для N=11/. Чем больше N, тем ближе к 0.18. Если никто не ошибся. Но для меня интересен сам факт того, что средняя точка - не всегда решение. |
Loban |
8.8.2015, 9:39
Сообщение
#19
|
Активный участник Группа: Пользователи Braingames Сообщений: 633 Регистрация: 1.12.2008 Пользователь №: 11 245 |
|
BAS14 |
21.8.2015, 18:45
Сообщение
#20
|
Активный участник Группа: Модераторы BrainGames Сообщений: 494 Регистрация: 25.7.2014 Из: Псков Пользователь №: 50 487 |
Рассмотрел для действительных чисел, что происходит при стремлении числа компов 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, тем ближе к концу отрезка нужно выбирать число. Сообщение было отредактировано BAS14: 21.8.2015, 19:11 |
Упрощённая версия | Сейчас: 25.4.2024, 9:23 |