IPB

Добро пожаловать, гость ( Вход | Регистрация )

> Правила раздела

Публикующим:
     1. Задачу можно опубликовать двумя способами:
          - создав для нее отдельную тему с информативным названием;
          - добавив задачу в готовый сборник (например «Бескрылки», «Мини-задачи», «Вопросы ЧГК») или создав свой (например, «Загадки от /для Светы»).
     2. Если вы публикуете задачу, решение которой не знаете, напишите об этом. По умолчанию считается, что вам известен правильный ответ и вы готовы проверять других игроков.
Решающим:
     1. В темах запрещается писать ответы и подсказки, если возможность открытого обсуждения не оговорена отдельно (в случае открытого обсуждения для текста следует использовать цвет фона или белый, оставляя другим игрокам возможность самостоятельного решения).
     2. Правильность решения можно проверить, написав личное сообщение автору.

2 Страниц V  1 2 >  
Ответить в эту темуОткрыть новую тему
> Угадывание
alan
1.8.2015, 18:07
Сообщение #1


zzz...
*****

Группа: Администраторы Braingames
Сообщений: 12 309
Регистрация: 23.2.2009
Из: Симферополь
Пользователь №: 13 114



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

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


Решения не знаю.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Loban
1.8.2015, 19:17
Сообщение #2


Активный участник
***

Группа: Пользователи Braingames
Сообщений: 609
Регистрация: 1.12.2008
Пользователь №: 11 245



Вы не верите в симметрию? smile.gif
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Owen
1.8.2015, 19:37
Сообщение #3


Kорифей
****

Группа: Администраторы Braingames
Сообщений: 2 519
Регистрация: 6.3.2013
Пользователь №: 43 989



Напрашивается 50, конечно.
Для 1 и 2 компов это вроде выигрыш.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Loban
1.8.2015, 19:37
Сообщение #4


Активный участник
***

Группа: Пользователи Braingames
Сообщений: 609
Регистрация: 1.12.2008
Пользователь №: 11 245



QUOTE(alan @ 1.8.2015, 18:07) *
Число так же угадывает компы

Может лучше, угадывают? smile.gif
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
netvoe
1.8.2015, 21:42
Сообщение #5


Бывалый
****

Группа: Пользователи Braingames
Сообщений: 1 081
Регистрация: 22.4.2007
Из: Tampa, FL
Пользователь №: 216



QUOTE(Owen @ 1.8.2015, 11:37) *
Напрашивается 50, конечно.
Для 1 и 2 компов это вроде выигрыш.

когда то задавал обратную задачу - Жребий.
Ведущий загадывает число 1-100. Остальные пикапят числа в этом же диапозоне. Проигрывает тот, кто назовет число ближайшее к загаданному. Тогда мне подтвердили идею, что самый оптимальный вариант для игроков называть крайние числа - 1 и 100. Эта задача кажется обратной...
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Breghnev
1.8.2015, 23:45
Сообщение #6


Новичок
*

Группа: Пользователи Braingames
Сообщений: 39
Регистрация: 8.5.2008
Из: Йошкар-Ола
Пользователь №: 7 813



QUOTE(netvoe @ 1.8.2015, 21:42) *
когда то задавал обратную задачу - Жребий.
Ведущий загадывает число 1-100. Остальные пикапят числа в этом же диапозоне. Проигрывает тот, кто назовет число ближайшее к загаданному. Тогда мне подтвердили идею, что самый оптимальный вариант для игроков называть крайние числа - 1 и 100. Эта задача кажется обратной...

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

Сообщение было отредактировано Breghnev: 1.8.2015, 23:45
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
alan
2.8.2015, 10:32
Сообщение #7


zzz...
*****

Группа: Администраторы Braingames
Сообщений: 12 309
Регистрация: 23.2.2009
Из: Симферополь
Пользователь №: 13 114



QUOTE(Loban @ 1.8.2015, 17:17) *
Вы не верите в симметрию? smile.gif

Верю. А что тут симметрия говорит? Максимум то, что если Х это оптимум, то и 100-Х будет оптимумом. Так чему равен Х? А точнее "равнЫ";)
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
BAS14
2.8.2015, 20:33
Сообщение #8


Активный участник
***

Группа: Модераторы BrainGames
Сообщений: 366
Регистрация: 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 331
Регистрация: 26.3.2009
Пользователь №: 13 618



QUOTE(alan @ 2.8.2015, 10:32) *
Верю. А что тут симметрия говорит? Максимум то, что если Х это оптимум, то и 100-Х будет оптимумом. Так чему равен Х? А точнее "равнЫ";)

А если пойти дальше?
Не обязательно от середины отражать.
Можно отразить от 25. (верхную половину можно не рассматривать из-за уже замеченной симметрии)
Получим что если Х<25 это оптимум то 50-X тоже оптимум. Обратное не верно из-за возможности выигрыша если загаданное число >50
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
BAS14
3.8.2015, 11:20
Сообщение #10


Активный участник
***

Группа: Модераторы BrainGames
Сообщений: 366
Регистрация: 25.7.2014
Из: Псков
Пользователь №: 50 487



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


Не думаю, что это утверждение верно. Называя Х<25 вместо 50-Х мы действительно уменьшаем свои шансы угадать число, если оно >50 (правда не до нуля, т.к. компы все еще могут проиграть, назвав еще меньшие числа), но зато получаем дополнительную возможность выигрыша, если загаданное число меньше нашего названного или достаточно близко к нему, а компы назовут >50. Правда навскидку вероятность первой ситуации представляется больше второй (хотя это еще посчитать надо), но это уже исключает возможность отражения относительно 25 (пусть и в одну сторону) - по одну и другую сторону от 25 возможности разные.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
alan
3.8.2015, 20:44
Сообщение #11


zzz...
*****

Группа: Администраторы Braingames
Сообщений: 12 309
Регистрация: 23.2.2009
Из: Симферополь
Пользователь №: 13 114



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

Целые. Но для действительных результат тоже интресен.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Breghnev
3.8.2015, 21:29
Сообщение #12


Новичок
*

Группа: Пользователи Braingames
Сообщений: 39
Регистрация: 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
Сообщений: 366
Регистрация: 25.7.2014
Из: Псков
Пользователь №: 50 487



QUOTE(alan @ 3.8.2015, 20:44) *
Целые. Но для действительных результат тоже интресен.


Может сначала для действительных рассмотреть? Там задача попроще кажется как минимум по 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
Сообщений: 366
Регистрация: 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
Сообщений: 609
Регистрация: 1.12.2008
Пользователь №: 11 245



QUOTE(alan @ 2.8.2015, 10:32) *
Верю. А что тут симметрия говорит? Максимум то, что если Х это оптимум, то и 100-Х будет оптимумом. Так чему равен Х? А точнее "равнЫ";)

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

Сообщение было отредактировано Loban: 5.8.2015, 16:36
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Breghnev
5.8.2015, 18:21
Сообщение #16


Новичок
*

Группа: Пользователи Braingames
Сообщений: 39
Регистрация: 8.5.2008
Из: Йошкар-Ола
Пользователь №: 7 813



Правильно я понял, что для 5 компов вероятность выигрыша при выборе середины отрезка у BAS14 получилась 0.18, а у Loban при тех же условиях - 0.267?
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
BAS14
5.8.2015, 20:06
Сообщение #17


Активный участник
***

Группа: Модераторы BrainGames
Сообщений: 366
Регистрация: 25.7.2014
Из: Псков
Пользователь №: 50 487



QUOTE(Breghnev @ 5.8.2015, 18:21) *
Правильно я понял, что для 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
Сообщений: 609
Регистрация: 1.12.2008
Пользователь №: 11 245



QUOTE(Breghnev @ 5.8.2015, 18:21) *
Правильно я понял, что для 5 компов вероятность выигрыша при выборе середины отрезка у BAS14 получилась 0.18, а у Loban при тех же условиях - 0.267?

Нет.
У BAS14 решение для действительных чисел, у меня для целых /всего-то для N=11/. Чем больше N, тем ближе к 0.18. Если никто не ошибся. smile.gif
Но для меня интересен сам факт того, что средняя точка - не всегда решение.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Loban
8.8.2015, 9:39
Сообщение #19


Активный участник
***

Группа: Пользователи Braingames
Сообщений: 609
Регистрация: 1.12.2008
Пользователь №: 11 245



QUOTE(Loban @ 5.8.2015, 16:35) *
Правда, 11 это не 101.

Несложно оказалось посчитать и для 101 точки.
Для 5 компов в т. 51 - 0.18998, в т. 31,71 - 0.19281.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
BAS14
21.8.2015, 18:45
Сообщение #20


Активный участник
***

Группа: Модераторы BrainGames
Сообщений: 366
Регистрация: 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
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения

2 Страниц V  1 2 >
Ответить в эту темуОткрыть новую тему
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0 -

 



- Упрощённая версия Сейчас: 4.12.2020, 15:11