Вопрос школьника
Сергей и Саша играют в такую игру: по очереди берут камни из кучи, в которой лежит 100 камней. За один ход каждому разрешается взять или 1 камень, или 3. Кто из них возьмет последний камень, если игру начинает Сергей?
Ответ от учителя
Для решения этой задачи можно использовать метод математической индукции.
Пусть на первом ходу Сергей возьмет один камень. Тогда останется 99 камней, и на следующем ходу Саша может взять либо один камень, либо три. Если он возьмет один камень, то останется 98 камней, и Сергей сможет взять три камня, оставив 95 камней. Если же Саша возьмет три камня, то останется 96 камней, и Сергей сможет взять один камень, оставив 95 камней. Таким образом, в обоих случаях остается 95 камней.
Предположим теперь, что при любом количестве камней от 1 до 4n-1 игрок, начинающий игру, может выиграть, а при количестве камней 4n игрок, начинающий игру, проигрывает.
Докажем, что при количестве камней 4n+1 игрок, начинающий игру, может выиграть. Пусть на первом ходу Сергей возьмет один камень. Тогда останется 4n камней, и на следующем ходу Саша может взять либо один камень, либо три. Если он возьмет один камень, то останется 4n-1 камней, и Сергей сможет выиграть, используя предположение индукции. Если же Саша возьмет три камня, то останется 4n-2 камней, и Сергей сможет взять три камня, оставив 4n-5 камней. Теперь независимо от того, сколько камней возьмет Саша, Сергей может взять столько камней, чтобы оставить 4n-1 камней, и выиграть, используя предположение индукции.
Таким образом, при количестве камней 100 игрок, начинающий игру, может выиграть, и это будет Сергей.
