Маленькая игра

[ivana]

На столе лежат a красные и b зелёные камни. Два игрока, Маша и Саша, играют попеременно.
При каждом ходе игрок выбирает цвет и удаляет X камней этого цвета.
X должен бить делителем настоящего числа камней другого цвета.
Кто возьмёт последний камень, тот выиграет.

Кто может выиграть, Маша или Саша?

[worm2]

Я так понимаю, Маша ходит первой?

(1) Если a и b разной чётности, то Маша выигрывает. Её стратегия - вычесть из чётного числа 1 (если чётное число = 0, то, очевидно, нужно забрать оставшиеся камни) и прийти к ситуации, когда a и b оба нечётные.
(2) Если a и b оба нечётные, то выигрывает Саша. Ибо Маша вынуждена из одного нечётного числа вычесть также нечётное число, и получить чётное, т.е. ситуацию из п. (1), выигрышную для ходящего.
(3) Если a и b оба чётные, то каждый игрок вынужден отнимать чётное число камней, ибо иначе он приходит к ситуации п. (1), выигрышной для ходящего. Поэтому мы можем рассматривать не камни, а пары камней, и решение задачи для (2a, 2b) эквивалентно решению задачи для (a, b).
(4) Применяя (3) несколько раз, получаем, что если a и b представляются в виде $2^k(2m+1)$ и $2^k(2n+1)$ соответственно, т.е. в двоичной записи имеют одинаковое число нулей на конце, то выигрывает Саша. Иначе --- Маша.