Игра начинается с числа 1000. За ход разрешается вычесть из имеющегося числа любое, не превосходящее его, натуральное

   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, то при правильной игре первый всегда выигрывает.

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