На 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

изменен 13 Апр '12 23:58

DocentI's gravatar image


10.0k52252

Стратегия непонятна. Приведите пример!
Я вынимаю бумажку с числом $%\pi$%. Что мне говорить?

(14 Апр '12 0:00) DocentI

с вероятностью f(Pi) говорить "больше" в остальных случаях говорить меньше. Предполагается что наши вычислительные способности неограниченны и мы можем подбросить в уме монетку с заранее заданной вероятностью.

(14 Апр '12 13:52) shambalaxx
10|600 символов нужно символов осталось
1

Не очень понятны слова "Это если стратегия оккупантов выбирать какие-то конкретные числа. Даже если мы их не знаем мы будем выигрывать. Однако если оккупанты загадывают равновероятно a, b на множестве всех вещественных чисел, то..."

Мне кажется, если мы не знаем этих чисел, то для нас это как раз и означает, что они равномерно и независимо распределены на числовой плоскости.
Чудес все-таки не бывает!

ссылка

отвечен 14 Апр '12 17:48

Ну почему, если провести сколь угодно большое количество испытаний, в которых оккупанты будут выбирать конкретные 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
10|600 символов нужно символов осталось
1

В идеальном случае (то есть в текущей формулировке) решений нет.

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

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

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

Равномерное распределение по всем вещественным числам действительно обламывает подобные стратегии, так как нельзя найти матожидание. Но не все вещественные числа удовлетворяют условиям "может быть записано".

ссылка

отвечен 16 Апр '12 8:40

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

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

Пока не уверен что это не правильно, однако возможно я зря употребил термин "равновероятно"...

(16 Апр '12 12:10) shambalaxx
10|600 символов нужно символов осталось
1

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

ссылка

отвечен 16 Апр '12 16:29

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×4,105
×36

задан
13 Апр '12 18:05

показан
4120 раз

обновлен
16 Апр '12 23:04

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru