Решение задачи 329

Условие:

На столе лежат 100 спичек. Двое ходят по очереди. За один ход можно взять 1, 2, 4, 8, . . . (любую степень двойки) спичек. Проигрывает тот, кому нечего брать. Кто выиграет при правильной игре: тот, кто делает первый ход, или его партнёр?

Решение:

У первого игра есть победная стратегия: после каждого своего хода оставлять число спичек, кратное трем. Он так может делать, потому что если число спичек не кратно трем, то он берет одну или две спички, и их количество становится кратно трем. Также нетрудно заметить, что если из числа, кратного трем, вычесть степень двойки, то полученное число не будет делиться на 3. Значит, после каждого хода второго игрока количество спичек будет не кратно трем. Осталось заметить, что ноль кратен трем, значит последнюю спичку возьмет первый игрок.

Ответ: Первый игрок.