Красная и черная

[mathclimber]

Известная задачка, с красивым решением. Дано: хорошо перемешанная стандартная колода карт (52 шт.). Игрок открывает карты по очереди; один (и только один) раз за игру он должен сказать "красная!". Если следующая открытая карта красная, то игрок выиграл, если черная -- проиграл

Comments

[niktoinikak]

Задача мне кажется не до конца определённой. Именно. Ищется вероятность по данной конкретной раскладке, или по всему множеству раскладок (надеюсь, Вы меня поняли)? Конечно, похоже что эти вероятности одинаковы, но так сразу я доказательства не вижу.

[mathclimber]

Имеется в виду, что сначала колоду тасуют, потом дают игроку. Т.е., он применяет свою стратегию к случайному порядку карт.

[niktoinikak]

Т е стратегия - функция на последовательностях (цвет1, цвет2, ..... цвет50). Тогда да, мой вопрос дурацкий. Я сразу не осознал.

[ext_4080204]

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

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

[mathclimber]

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

[ext_4080204]

Похоже, да. Такой расклад возможен с невысокой вероятностью, но возможен, да.

[simplegary]

Дождаться, пока не откроется больше черных, чем красных, потом сказать.

[mathclimber]

Однако, этого можно и не дождаться :)

[niktoinikak]

Конечно, эта стратегия моментально приходит в голову. но доказать, что она решает задачу ...
Мне пока не удалось ...

[mathclimber]

Попробуйте посчитать, как работает эта стратегия на колоде из 4х карт.

[a_shen]

не приходит в голову ничего более простого, чем по индукции доказывать, что при любой стратегии для случайной кучи с данными количествами вероятности равны доле количеств - но, может быть, есть какое-то более концептуальное (кажется, так говорят учёные люди?) решение?

[mathclimber]

Есть.

https://arxiv.org/pdf/1910.02515.pdf
("Red Now", на второй странице)

[relf]

Опять там старушку мурыжат :)

[mathclimber]

Благородные доны имеют право иногда и поразвлечься :)

[zlata_gl]

Я сделала программу-симулятор.
Не на случайных числах, а на всех раскладах колоды.
52 карты - это много для полного перебора, я попробовала на 16, 24, 26.
Получается 50% выигрышей абсолютно точно.

Алгоритм такой:
Берем все 2^N битовых массивов.
Из них выбираем только те, в которых поровну единиц и нулей. Это "Расклады".
Дальше применяем к каждому раскладу такой алгоритм: открываем по одной карте, и когда оказывается открытых черных более половины от всех открытых, то объявляем следующую карту "красной".
Для интереса - выведены поля дождались/не дождались.
Не дождались - это когда остались последние 2 карты, а большинство открытых черных так и не наступило.
Просто открываем следующую.

Почему алгоритм не дает увеличения выигрышей, я не поняла.

[mathclimber]

Круто :)

Сейчас напишу решение ниже (почему для любой стратегии вероятность выигрыша строго 1/2).