Вопрос школьника
Сергій і Сашко грають у таку гру: по черзі беруть камінці з купи, у якій лежить 100 камінців. За один хід кожному дозволяється взяти або 1 камінець, або 3. Хто з них візьме останній камінець, якщо гру починає Сергій?
Ответ от учителя
Для розв’язання цієї задачі можна скористатися методом математичної індукції.
1. Базовий випадок: якщо в купі залишилося 1, 2 або 3 камінці, то гравець, який ходить перший, бере всі камінці і виграє гру.
2. Передположення: якщо в купі залишилося n камінців, де n > 3, то гравець, який ходить другим, може взяти таку кількість каменів, щоб залишити першому гравцю кратну трьом кількість каменів. Тоді перший гравець буде змушений взяти кількість каменів, яка не дорівнює 3, і гра перейде до другого гравця з купою, в якій залишилася кратна трьом кількість каменів.
3. Крок індукції: залишимо в купі 4 камені. Сергій бере 1 камінь, залишаючи 3. Сашко бере 3 камені, залишаючи 1. Сергій бере останній камінь і виграє гру.
Отже, якщо гру починає Сергій, то він може виграти, якщо він бере перший камінь. Якщо ж він бере 3 камені, то Сашко може взяти 1 камінь і залишити Сергію кратну трьом кількість каменів, тому Сергій буде змушений взяти кількість каменів, яка не дорівнює 3, і гра перейде до Сашка з купою, в якій залишилася кратна трьом кількість каменів. Таким чином, Сашко зможе виграти гру.
