[Из цикла "ДДТ или Детство Девочки Тани"]

После того, как соседский мальчик Вова, известный в школе математик-компьютерщик, раскусил ее первый лохотрон

Автор: vadimcher
Дата: 24.08.07

, она, не долго думая, пришла к нему снова...

"На этот раз все по-честному," -- начала Таня. -- "Мы с тобой сыграем в игру 'Удача-2'. Ты загадываешь ЛЮБЫЕ два различные числа. Одно из них любое называешь мне, а я отвечаю больше ли второе загаданное число или меньше. Вероятность угадать, разумеется, одна вторая. Если я угадала, ты мне рубь, если нет -- я тебе."

По-моему, все честно, не правда ли?

--------------------------------------------------------------------------------
Вот реализация этой игры, функция Вовы randomBig неизвестна, функцию Тани isTheOtherBigger требуется реализовать.

#include <iostream>
#include <math.h>

using namespace std;

class CStudent { // class for a student
    virtual int getGrade(void) = 0;
};

class CVova: public CStudent { // Vova-student, can produce and memorize big numbers!
private:
    BigNumber x, y;

    BigNumber randomBig(void);
public:
    virtual int getGrade(void) { return 5; }

    BigNumber guess(void) {
        x = randomBig();
        y = randomBig();
        if (rand() & 1) swap(x, y);
        return x;
    }
    BigNumber cash(bool theOtherIsBigger) {
        if ((theOtherIsBigger && y > x) || (!theOtherIsBigger && y < x)) return 1/*buck*/;
        else return -1/*buck*/;
    }
} Vova;

class CTanya: public CStudent { // Tanya-student, can answer stupid questions and get cash
private:
    BigNumber cash;
public:
    virtual int getGrade(void) { return rand()&1 ? 3 : 2; }

    bool isTheOtherBigger(BigNumber n); // TODO

    BigNumber getCash(BigNumber check) { return cash += check; }
} Tanya;

/******* MAIN *******/
void main(void) {
    BigNumber iteration = 0;
    while (1) {
        BigNumber hercash;
        cout << "Tanya's cash: "
            << (hercash = Tanya.getCash(
                    Vova.cash(
                            Tanya.isTheOtherBigger(
                                    Vova.guess()
                            )
                    )
                ))
            << " She wins with probability: " << (hercash + ++iteration) / 2. / iteration
            << '\n';
    }
}

Здравствуйте, vadimcher, Вы писали:

V>«На этот раз все по-честному», — начала Таня. — «Мы с тобой сыграем в игру „Удача-2“. Ты загадываешь ЛЮБЫЕ два различные числа. Одно из них любое называешь мне, а я отвечаю больше ли второе загаданное число или меньше. Вероятность угадать, разумеется, одна вторая. Если я угадала, ты мне рубь, если нет — я тебе».

V>По-моему, все честно, не правда ли?

Вова называет всегда 42, а другое число — равновероятный выбор из 0 и 73.

50%.

V>class CTanya: public CStudent { // Tanya-student, can answer stupid questions and get cash

http://www.jelovic.com/articles/stupid_naming.htm ! !! !!!

Здравствуйте, Roman Odaisky, Вы писали:

RO>Здравствуйте, vadimcher, Вы писали:

V>>«На этот раз все по-честному», — начала Таня. — «Мы с тобой сыграем в игру „Удача-2“. Ты загадываешь ЛЮБЫЕ два различные числа. Одно из них любое называешь мне, а я отвечаю больше ли второе загаданное число или меньше. Вероятность угадать, разумеется, одна вторая. Если я угадала, ты мне рубь, если нет — я тебе».

V>>По-моему, все честно, не правда ли?

RO>Вова называет всегда 42, а другое число — равновероятный выбор из 0 и 73.
RO>50%.

Вова "работает" по-другому. Он придумывает два числа и называет одно из них случайно. Чтобы начать загадывать как-то по-другому, надо сначала понять, в чем подвох.

V>>class CTanya: public CStudent { // Tanya-student, can answer stupid questions and get cash
RO>http://www.jelovic.com/articles/stupid_naming.htm ! !! !!!

А это к чему? Кого-то раздражет обилие букв C перед именами классов? Не увидел в статье ни одного довода, почему это вредно. Не используйте C перед именами классов, так как это было сделано по ошибке? Если бы Вы знали, сколько полезных вещей в этом мире сделано по ошибке! Кроме того, это вещь весьма субъективная. "Почему у Вас телевизор круглый?" "А потому, что мне так нравится!"

Здравствуйте, vadimcher, Вы писали:

RO>>Вова называет всегда 42, а другое число — равновероятный выбор из 0 и 73.
RO>>50%.

42 — наш ответ Чемберлену (на вопрос о жизни, вселенной и всём таком)

V>Вова "работает" по-другому. Он придумывает два числа и называет одно из них случайно. Чтобы начать загадывать как-то по-другому, надо сначала понять, в чем подвох.

Подвох в том, что если Вова работает с натуральными числами, то второе число с большей (с бесконечно большей) вероятностью больше первого. То же относится и к конечному множеству чисел: интервалы [min,X) vs (X,max] неравноценны, но тут уже Тане надо знать min и max, чтобы делать выводы.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, vadimcher, Вы писали:

RO>>>Вова называет всегда 42, а другое число — равновероятный выбор из 0 и 73.
RO>>>50%.

К>42 — наш ответ Чемберлену (на вопрос о жизни, вселенной и всём таком)

V>>Вова "работает" по-другому. Он придумывает два числа и называет одно из них случайно. Чтобы начать загадывать как-то по-другому, надо сначала понять, в чем подвох.

К>Подвох в том, что если Вова работает с натуральными числами, то второе число с большей (с бесконечно большей) вероятностью больше первого. То же относится и к конечному множеству чисел: интервалы [min,X) vs (X,max] неравноценны, но тут уже Тане надо знать min и max, чтобы делать выводы.

У Тани есть вполне определенная стратегия, чтобы выигрывать с вероятностью >1/2, даже если Вова придумывает любые два числа из Z или R.

Здравствуйте, vadimcher, Вы писали:

V>"На этот раз все по-честному," -- начала Таня. -- "Мы с тобой сыграем в игру 'Удача-2'. Ты загадываешь ЛЮБЫЕ два различные числа. Одно из них любое называешь мне, а я отвечаю больше ли второе загаданное число или меньше. Вероятность угадать, разумеется, одна вторая. Если я угадала, ты мне рубь, если нет -- я тебе."

По сути, Таня пытается предсказать генератор Вовы на основе "почти" случайной подпоследовательности его результатов. Если предположить, что Вова использует какой-нибудь неадаптируемый генератор, то подойдет, наверное, следующая стратегия: первый ответ — случайный, остальные ответы строятся исходя из сравнения называемого Вовой числа со средним ранее названных чисел. В простейшем случае ответ Тани равен результату сравнения. В более сложном стоит давать его с вероятностью успеха второго и последующих произведенных шагов.

Здравствуйте, andyJB, Вы писали:

JB>По сути, Таня пытается предсказать генератор Вовы на основе "почти" случайной подпоследовательности его результатов. Если предположить, что Вова использует какой-нибудь неадаптируемый генератор, то подойдет, наверное, следующая стратегия: первый ответ — случайный, остальные ответы строятся исходя из сравнения называемого Вовой числа со средним ранее названных чисел. В простейшем случае ответ Тани равен результату сравнения. В более сложном стоит давать его с вероятностью успеха второго и последующих произведенных шагов.
Тьфу, не со средним, конечно, а с числом, относительно которого одинаковое число результатов слева и справа. То есть, если Вова называл 100, 3 и три раза 1, то надо сравнивать с 2.
В общем случае, когда Вова может использовать произвольный генератор, ответ 1/2.

Здравствуйте, vadimcher, Вы писали:

RO>>>>Вова называет всегда 42, а другое число — равновероятный выбор из 0 и 73.

V>У Тани есть вполне определенная стратегия, чтобы выигрывать с вероятностью >1/2, даже если Вова придумывает любые два числа из Z или R.

И какая именно для вышеописанной стратегии Вовы?

Здравствуйте, Roman Odaisky, Вы писали:

RO>Здравствуйте, vadimcher, Вы писали:

RO>>>>>Вова называет всегда 42, а другое число — равновероятный выбор из 0 и 73.

V>>У Тани есть вполне определенная стратегия, чтобы выигрывать с вероятностью >1/2, даже если Вова придумывает любые два числа из Z или R.

RO>И какая именно для вышеописанной стратегии Вовы?

Для вышеописанной стратегии Вовы -- я думаю 1/2. Однако Вова, для того, чтобы применять что-то особенное, должен сначала понять, в чем подвох.

Хорошо, давайте так. Представьте, что ему надо загадать два числа, написать их на бумажках и отдать Тане. Она откроет одну из них (случайно) и ответит про второе число, больше ли оно, или меньше. После чего откроет вторую бумажку и проверит.

Здравствуйте, vadimcher, Вы писали:

V>[Из цикла "ДДТ или Детство Девочки Тани"]

V>После того, как соседский мальчик Вова, известный в школе математик-компьютерщик, раскусил ее первый лохотрон

Автор: vadimcher
Дата: 24.08.07

, она, не долго думая, пришла к нему снова...

V>"На этот раз все по-честному," -- начала Таня. -- "Мы с тобой сыграем в игру 'Удача-2'. Ты загадываешь ЛЮБЫЕ два различные числа. Одно из них любое называешь мне, а я отвечаю больше ли второе загаданное число или меньше. Вероятность угадать, разумеется, одна вторая. Если я угадала, ты мне рубь, если нет -- я тебе."

V>По-моему, все честно, не правда ли?

Давайте так.

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

Может ли Таня выиграть с вероятностью больше 1/2?

Здравствуйте, vadimcher, Вы писали:

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

V>Может ли Таня выиграть с вероятностью больше 1/2?
Без дополнительной информации — нет (в формуле условной вероятности все 1/2 успешно сократятся).

Здравствуйте, andyJB, Вы писали:

JB>Здравствуйте, vadimcher, Вы писали:

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

V>>Может ли Таня выиграть с вероятностью больше 1/2?
JB>Без дополнительной информации — нет (в формуле условной вероятности все 1/2 успешно сократятся).

А поподробнее? Не в смысле, что это ответ, а просто, чтобы понять ход мысли.

Здравствуйте, vadimcher, Вы писали:

V>Здравствуйте, andyJB, Вы писали:

JB>>Здравствуйте, vadimcher, Вы писали:

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

V>>>Может ли Таня выиграть с вероятностью больше 1/2?
JB>>Без дополнительной информации — нет (в формуле условной вероятности все 1/2 успешно сократятся).

V>А поподробнее? Не в смысле, что это ответ, а просто, чтобы понять ход мысли.

Поподробнее — очень просто. Если предположить, что Вова выбирает любое число из, например Z ( натуральные числа здесь не подойдут ) случайным образом с равномерным распределением и сообщает одно из двух чисел Тане, причем выбор какое из двух чисел сообщается делается случайным образом ( то есть образом, не зависящим от такого какие числа выбраны ), то это эквивалентно тому, что у Вовы есть функция rand(), возвращающая результат в Z, и Вова вызывает ее два раза и результат первого вызова сообщает Тане. Но вероятность того, что второе число больше первого равна 1/2, как вероятность того, что оно меньше первого. Таким образом Таня здесь поделать ничего не сможет. Другое дело, что в реальной жизни, Вова будет выбирать числа из конечного диапазона.

Здравствуйте, vadimcher, Вы писали:

V>А поподробнее? Не в смысле, что это ответ, а просто, чтобы понять ход мысли.

        P(x=x0|x>y)P(x>y)
P(x>y|x=x0) = -------------------------------------

P(x=x0|x>y)P(x>y)+P(x=x0|x<=y)P(x<=y)
P(x>y) = P(x<=y) = 1/2

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, vadimcher, Вы писали:

V>>А поподробнее? Не в смысле, что это ответ, а просто, чтобы понять ход мысли.
А>

        P(x=x0|x>y)P(x>y)
А>P(x>y|x=x0) = -------------------------------------
А>

P(x=x0|x>y)P(x>y)+P(x=x0|x<=y)P(x<=y)
А>P(x>y) = P(x<=y) = 1/2

Оба ответа свелись к тому, что вероятность того, что другое число больше равна 1/2.
Это так (никаких трюков с натуральными, кривыми диапазонами и т.д. я не предлагаю).

Но значит ли это, что Таня может угадать с вероятностью 1/2 только?
Если бы Таня играла в закрытую, то она бы могла сразу выбрать одну бумажку и, не открывая, сказать, "второе число больше", например. Таня видит одно число, дает ли это ей какое-то преимущество?

Здравствуйте, vadimcher, Вы писали:

V>Но значит ли это, что Таня может угадать с вероятностью 1/2 только?
V>Если бы Таня играла в закрытую, то она бы могла сразу выбрать одну бумажку и, не открывая, сказать, "второе число больше", например. Таня видит одно число, дает ли это ей какое-то преимущество?

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

V>Если бы Таня играла в закрытую, то она бы могла сразу выбрать одну бумажку и, не открывая, сказать, "второе число больше", например. Таня видит одно число, дает ли это ей какое-то преимущество?

P(x>y) = P(x<=y) = 1/2

              P(x=x0|x>y)P(x>y)
P(x>y|x=x0) = ------------------------------------- = 
               P(x=x0|x>y)P(x>y)+P(x=x0|x<=y)P(x<=y)

            P(x=x0|x>y)
= ------------------------------------- 
    P(x=x0|x>y) + P(x=x0|x<=y)

Утверждение, что P(x>y|x=x0)>1/2 соответствует тому, что P(x=x0|x>y) > P(x=x0|x<=y).

V>Но значит ли это, что Таня может угадать с вероятностью 1/2 только?
V>Если бы Таня играла в закрытую, то она бы могла сразу выбрать одну бумажку и, не открывая, сказать, "второе число больше", например. Таня видит одно число, дает ли это ей какое-то преимущество?

Если игра продолжается достаточно долго, то Таня может по получаемым числам оценивать диапазон чисел используемых Вовой, MIN..MAX, постоянно его корректируя. Тогда если названное число <= середины диапазона, то неназванное с вероятностью >= 1/2 больше.

Если же Вова догадается об этой стратегии, то его контрстратегия будет заключаться в ... В чем?

Когда же умная девочка Таня догадается о контрстратегии Вовы, то она перейдет к стратегии2. Какой?

jmp PC — 2

Здравствуйте, Аноним, Вы писали:

V>>Но значит ли это, что Таня может угадать с вероятностью 1/2 только?
V>>Если бы Таня играла в закрытую, то она бы могла сразу выбрать одну бумажку и, не открывая, сказать, "второе число больше", например. Таня видит одно число, дает ли это ей какое-то преимущество?

А>Если игра продолжается достаточно долго, то Таня может по получаемым числам оценивать диапазон чисел используемых Вовой, MIN..MAX, постоянно его корректируя. Тогда если названное число <= середины диапазона, то неназванное с вероятностью >= 1/2 больше.

А>Если же Вова догадается об этой стратегии, то его контрстратегия будет заключаться в ... В чем?

А>Когда же умная девочка Таня догадается о контрстратегии Вовы, то она перейдет к стратегии2. Какой?

А>jmp PC — 2

Не, для простоты игра идет один раз. Мы уже договорились.

Здравствуйте, andyJB, Вы писали:

JB>Утверждение, что P(x>y|x=x0)>1/2 соответствует тому, что P(x=x0|x>y) > P(x=x0|x<=y).
Что, опять же из P(x>y) = P(x<=y), равносильно P(x=x0 & x>y) > P(x=x0 & x<=y). Откуда P(x>y) > P(x<=y)!?