|
|
 |
Условие
У игрока есть m золотых и n серебряных монет. В начале каждого раунда игрок ставит какие-то монеты на красное, какие-то на чёрное (можно вообще ничего не ставить на один из цветов, часть монет можно никуда не ставить). В конце каждого раунда крупье объявляет, что один из цветов выиграл. Ставку на выигравший цвет крупье отдаёт игроку, удваивая в ней количество монет каждого вида, а ставку на проигравший цвет забирает себе. Игрок хочет, чтобы монет одного вида у него стало ровно в три раза больше, чем другого (в частности, его устроит остаться совсем без денег). При каких m и n крупье не сможет ему помешать?
Решение
Пусть перед каким-то раундом у игрока осталось a золотых и b серебряных монет. Посмотрим, что происходит с a и b за один раунд. Допустим, игрок поставил на красное x золотых и p серебряных, а на чёрное – y золотых и q серебряных монет. Тогда в зависимости от выбора крупье либо количество золотых увеличится на z = x – y, a серебряных – на r = p – q, либо количество монет каждого типа уменьшится на эти числа. Ясно, что |z| ≤ a и
|r| ≤ b и что любые z и r в указанных диапазонах можно обеспечить.
Предположим, что a > 3b. Тогда крупье может добиться того, чтобы это неравенство сохранилось и после раунда. В самом деле, если оно нарушается при любом выборе крупье, то a – z < 3(b – r) и a + z < 3(b + r). Складывая эти неравенства, получаем, что 2a < 6b, что не так. Значит, если в начале количества монет отличаются более чем в 3 раза, крупье может сделать так, чтобы они все время отличались более чем в 3 раза.
При m = 3n или n = 3m задача уже решена. Осталось рассмотреть случай, когда
m < 3n и n < 3m.
Попробуем подобрать z и r так, чтобы при любом исходе отношение количеств монет стало равно 3. Составим систему уравнений: a + z = 3(b + r), 3(a – z) = b – r. Решая её, находим: z = 5a/4 – 3b/4, r = 3a/4 – 5b/4. При a и b, отличающихся менее чем в 3 раза, |z| < a, |r| < b. Заметим, что если a + b кратно 4, то z и r будут также целыми. Значит, в этом случае игрок сможет достичь цели за один раунд.
Осталось показать, что игрок может сделать a + b кратным 4. Действительно, поставив все монеты на красное, игрок может добиться, чтобы либо всё пропало (что его устраивает), либо общее количество монет удвоилось.
Повторив эту процедуру еще раз, игрок сделает так, что общее число монет
будет делиться на 4. При этом соотношения a < 3b и b < 3a сохранятся.
Ответ
При m и n, отличающихся не более чем в 3 раза.
Замечания
Попробуем решить более общую задачу – пусть игрок хочет, чтобы у него монет одного вида стало ровно в k раз больше, чем монет другого.
Аналогично случаю k = 3, можно доказать, что если вначале количества монет разных видов отличаются более чем в k раз, то крупье сможет помешать игроку. Если же отношение количеств меньше k, попробуем применить тот же алгоритм, что и в решении. Тогда при вычислении ставки в знаменателе получится число k² – 1 (или ½ (k² – 1), если k нечётно). Поскольку мы умеем удваивать начальные числа, наше решение пройдёт, если
k² – 1 – степень двойки. Но такое число k только одно – 3.
Поэтому при k ≠ 3 наш алгоритм работает не всегда, даже если начальное отношение количеств монет менее k. Это не случайно – на самом деле, при k ≠ 3 ответ зависит не только от отношения m к n.
отношение чисел m и n не превышает k;
существует такое натуральное r, что 2r(m + n) кратно k + 1;
существует такое натуральное s, что 2s(m – n) кратно k – 1.
