математика

597400 · Сообщение **597400** » 10 мар 2008, 15:40

У игрока есть M золотых и N серебрянных монет.B начале каждого раунда игрок ставит какие-то монеты на красное, ккакие-то на черное(можно вообще ничего не ставить).B конце каждого раунда крупье объявляет, что один из цветов выиграл. Ставку на выигравший цвет крупье отдаёт игроку, удваивая в ней количество монет каждого вида, a ставку на проигравший цвет забирает себе.
Игрок хочет, чтобы монет одного вида у него стало ровно в три раза больше, чем другого(в частности, его устроит остаться совсем без денег).При каких M и N крупье не сможет ему помешать?

Мне кажется, что M должно быть равно N

CD_Eater · Сообщение **CD_Eater** » 11 мар 2008, 00:05

Крупье не сможет помешать, если изначально отношение количества золотых и серебряных монет лежит в диапазоне от 1/3 до 3 (включительно). Причём игроку достаточно всего 3 игры (вроде бы).

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

CD_Eater · Сообщение **CD_Eater** » 11 мар 2008, 12:11

Алгоритм такой:
Сначала есть M золотых и N серебряных монет.
Первые 2 игры ставим всё что есть на красное. Если портье скажет, что мы банкроты, то мы достигли цели. Поэтому портье вынужден будет удваивать наши монеты и после двух игр у нас будет 4M золотых и 4N серебряных монет.
Третью игру ставим:
на красное $\max\{0,\ 5M-3N\}$ золотых и $\max\{0,\ 3M-5N\}$ серебряных монет,
на чёрное $\max\{0,\ 3N-5M\}$ золотых и $\max\{0,\ 5N-3M\}$ серебряных.

A если у нас изначально M/N < 1/3, то алгоритм портье прост - выбирать выигравший цвет так, чтобы отношение M/N не увеличивалось - он всегда сможет так сделать.

597400 · Сообщение **597400** » 11 мар 2008, 13:00

УХ,СПАСИБО!

597400 · Сообщение **597400** » 29 мар 2008, 13:11

Кому интересно-наконец-то дали решение
[url=http://olympiads.mccme.ru/mmo/2008/solutions.pdf]http://olympiads.mccme.ru/mmo/2008/solutions.pdf[/url]

CD_Eater · Сообщение **CD_Eater** » 29 мар 2008, 18:03

Красивое решение по индукции!

yourdomain.com