Областная олимпиада по математике, 2003 год, 9 класс

На столе лежит 2003 камня. Двое игроков по очереди убирают некоторое количество камней, не меньше одного, но не больше половины из оставшихся камней на каждом шагу. Проигрывает тот, после хода которого останется 1 камень. Какой из игроков, первый или второй, при правильной игре победит в данной игре?

Комментарий/решение

Ответ:первый.

Решение:Рассмотрим все выигрышные позиции.Это:2,5,11,23,47,95,191,383,767,1535 и 2003.Первый игрок запросто может оставить 1535 камней при первом ходе.Тогда второй может оставить от 1534 до 768 (1534 и 768

включительно) камней за ход.Судь в том что второй никак не может оставить после себя 767 камней.А первый после хода второго - может. Таким образом второй неизбежно будет прыгать только на проигрышные позиции в то время как у первого постоянно будут возможности спрыгнуть на выигрышную позицию.В конце концов первый доберется до последней выигрышной позиции, позиции 2. Тогда второй неизбежно должен будет оставить после себя 1 камень, что и приведет его к проигрышу.