Игра начинается с числа 1000. За ход разрешается вычесть из имеющегося числа любое, не превосходящее его, натуральное число, являющееся степенью двойки (1 = 20). Выигрывает тот, кто получит ноль. Кто выиграет при правильной игре?

1. Докажем с помощью математической индукции, что числа, кратные 3, являются проигрышными позициями, остальные - выигрышными.

2. Для этого число n представим в виде:

n - 1 = 3k + r; n = 3k + r + 1, где k = 0, 1, 2, ...; r = 0, 1, 2 - остаток от деления числа n - 1 на 3.

3. При k = 0 получим три значения для n: 1, 2, 3. Очевидно, что 3 - проигрышная, а 1 и 2 - выигрышные позиции.

4. Предположим, что для k = m > 0, верно наше предположение, т. е. все числа в промежутке от 1 до 3m + 3, которые делятся на 3, являются проигрышными, а остальные - выигрышными позициями. Докажем, что при k = m + 1, из следующих трех чисел - 3m + 4, 3m + 5, 3m + 6, проигрышным является лишь число 3m + 6, кратное 3:

a) n = 3m + 4. Отнимаем 1 и передаем проигрышное число n = 3m + 3 сопернику;

b) n = 3m + 5. Отнимаем 2 и передаем проигрышное число n = 3m + 3 сопернику;

c) n = 3m + 6 = 3 (m + 2). Поскольку n делится на 3, то невозможно вычесть степень двойки, и снова получить число, кратное 3. Следовательно, 3m + 6 - проигрышная позиция, что и требовалось доказать.

5. Поскольку число 1000 не делится на 3, то при правильной игре первый всегда выигрывает.

Ответ: первый выигрывает.