На braingames.ru есть такая задача: Оккупанты, известным только им образом, выбирают два различных вещественных числа и записывают их на двух бумажках. Затем предлагают Мегамозгу выбрать любую бумажку, посмотреть на написанное там число и угадать, больше число на другой бумажке или меньше. Докажите, что у Мегамозга есть стратегия, которая позволит ему угадать с вероятностью больше 50%. Насколько я понимаю решение к ней такое: Введем ф-цию f(x) - вероятность того что мы ответим "больше" и 1-f(x), что ответим меньше, такую что: a>b => f(a)>f(b) оккупанты загадывают два таких числа a>b. Мы вытаскиваем какое-то из них с вероятностью 1/2. Тогда наш шанс угадать: P(угадать) = 1/2f(a) + 1/2(1-f(b)) = 1/2 + (f(a)-f(b))*1/2 >0 Однако это если стратегия оккупантов выбирать какие-то конкретные числа. Даже если мы их не знаем мы будем выигрывать. Однако если оккупанты загадывают равновероятно a, b на множестве всех вещественных чисел, то не вдаваясь в подробности будем иметь: P(угадать) = 1/2 + (интеграл от среднего значения f(a)-f(b) на бесконечности равен 0) = 1/2 Собственно вопрос правильно ли сформулирована исходная и задача и есть ли в ней решение, в таком виде как она записана? задан 13 Апр '12 18:05 shambalaxx |
Не очень понятны слова "Это если стратегия оккупантов выбирать какие-то конкретные числа. Даже если мы их не знаем мы будем выигрывать. Однако если оккупанты загадывают равновероятно a, b на множестве всех вещественных чисел, то..." Мне кажется, если мы не знаем этих чисел, то для нас это как раз и означает, что они равномерно и независимо распределены на числовой плоскости. отвечен 14 Апр '12 17:48 DocentI Ну почему, если провести сколь угодно большое количество испытаний, в которых оккупанты будут выбирать конкретные 2 числа, то ММ по своей стратегии будет выигрывать больше половины раз, не зная этих чисел, за счет того что в своей стратегии он использует то число которое ему показывают.
(14 Апр '12 17:55)
shambalaxx
Если оккупанты будут выбирать конкретные два числа, то через пару испытаний мы узнаем, какие они, так что выигрывать будем в 100% случаев!
(14 Апр '12 17:57)
DocentI
ММ не может менять стратегию. Все стратегии записываются перед испытаниями. Мы же испытываем стратегию а не мегамозга.
(14 Апр '12 18:40)
shambalaxx
А, он просто тупой! Тогда стратегия правильная.
(14 Апр '12 19:48)
DocentI
Ну в случае когда оккупанты загадывают конкретные числа да. Вопрос когда оккупанты загадывают случайные числа.
(14 Апр '12 21:34)
shambalaxx
Тут никакая стратегия не поможет, но строгого доказательства я не знаю. Просто интуитивно. В силу симметрии задачи.
(14 Апр '12 21:35)
DocentI
Не очень понял предыдущий комментарий?
(15 Апр '12 2:24)
shambalaxx
показано 5 из 7
показать еще 2
|
В идеальном случае (то есть в текущей формулировке) решений нет. При серии испытаний решение появляется в виде стратегии, завязанной на то, что количество символов на бумаге, которыми можно записать число, конечно; при записи используются числа, знакомые оккупантам, то есть можно выявить область возможных чисел и в зависимости от известного 1 числа определять вероятность появления второго числа из диапазона возможных значений. Здесь есть контрстратегии оккупантов, но они быстро исчерпываются их знаниями о числах и возможностью записывать. То есть, чтобы задача имела решение, требуется доказать ограниченность числа наборов предложенных оккупантами пары. Равномерное распределение по всем вещественным числам действительно обламывает подобные стратегии, так как нельзя найти матожидание. Но не все вещественные числа удовлетворяют условиям "может быть записано". отвечен 16 Апр '12 8:40 sunny Ну данная задача судя по всему чисто теоретическая, поэтому мы считаем что можем записать любое действительное число. Однако мне приводят в качестве аргумента принципиальную невозможность выбора случайного числа равновероятно на неограниченном интервале. Пока не уверен что это не правильно, однако возможно я зря употребил термин "равновероятно"...
(16 Апр '12 12:10)
shambalaxx
|
Процессы записи числа на бумагу и его чтения - это процессы информационного обмена, а любая информация может кодироваться только целыми числами (например, кодами написанных символов). Поэтому данная задача никогда не выйдет за пределы задачи перебора на конечном множестве. Выражение "любое действительное число" в данном случае не имеет смысла. отвечен 16 Апр '12 16:29 Андрей Юрьевич |
Стратегия непонятна. Приведите пример!
Я вынимаю бумажку с числом $%\pi$%. Что мне говорить?
с вероятностью f(Pi) говорить "больше" в остальных случаях говорить меньше. Предполагается что наши вычислительные способности неограниченны и мы можем подбросить в уме монетку с заранее заданной вероятностью.