Математикадан облыстық олимпиада, 2002-2003 оқу жылы, 9 сынып

Тақта үстінде 2003 тас жатыр. Екі ойыншы кезекпен бірден кем емес, бірақ қалған тастардың жартысынан аспайтын бірнеше тас алады. Жүрісінен кейін бір тас қалған ойыншы жеңіледі. Ойыншылардың қайсысы (біріншісі ме, екіншісі ме) әрқашан дұрыс ойнап жеңе алады?

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

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

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

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

Условие задачи

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

Решение

1. Определим стратегию игры.

Позиции в игре делятся на выигрышные и проигрышные:

- Проигрышная позиция — та, из которой любой ход приводит к выигрышной позиции противника.

- Выигрышная позиция — та, из которой можно оставить противнику проигрышную позицию.

2. Рассмотрим базовые случаи:

- Если на столе остаётся $n = 3$ камня, то текущий игрок, каким бы ни был его ход, оставляет противнику $n = 1$ камень, и проигрывает. Таким образом, $n = 3$ — проигрышная позиция.

- Если на столе $n = 4$, игрок может убрать 1 камень, оставив противнику 3. Тогда противник проиграет. Значит, $n = 4$ — выигрышная позиция.

- Если $n = 5$, игрок не может избежать того, чтобы оставить противнику выигрышную позицию (4 или 3). Значит, $n = 5$ — проигрышная позиция.

3. Общий вывод:

- Проигрышными позициями являются числа $n = 2^k - 1$, где $k \geq 1$. То есть $n = 3, 7, 15, 31, \dots$.

- Все остальные позиции являются выигрышными.

4. Проверим $n = 2003$:

- Найдём ближайшее число вида $2^k - 1$, меньшее 2003.

Поскольку $2^{11} - 1 = 2047 > 2003$, берём $2^{10} - 1 = 1023$.

- Позиция $n = 1023$ проигрышная, но $n = 2003$ — не проигрышная. Значит, $2003$ — выигрышная позиция.

Ответ: Первый игрок победит при правильной игре.