Тест 11 Моделирование на графах Вариант 1. Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй 4 камня. У каждого игрока неограниченно много камней. Ходят игроки по очереди. Делая очередной ход, игрок или увеличивает в какой-то кучке число камней в 2 раза, или добавляет в какую-то кучку 3 камня. Выигрывает тот игрок, после хода которого общее число камней в двух кучках становится не менее 23. Кто выиграет - игрок, делающий ход первым (первый игрок), или игрок, делающий ход вторым (второй игрок)?

Разберем возможные сценарии игры, чтобы определить победителя. Начальная позиция: 3 и 4 камня. Общее количество: 7 камней. Для выигрыша необходимо набрать не менее 23 камней. Ход 1: Игрок 1 * Удвоить первую кучку: 6 и 4. Сумма: 10. * Удвоить вторую кучку: 3 и 8. Сумма: 11. * Добавить 3 в первую кучку: 6 и 4. Сумма: 10. * Добавить 3 во вторую кучку: 3 и 7. Сумма: 10. Ход 2: Игрок 2 Рассмотрим лучший ход для Игрока 1: удвоить вторую кучку (3 и 8. Сумма: 11). Теперь Игрок 2 может: * Удвоить первую кучку: 6 и 8. Сумма: 14. * Удвоить вторую кучку: 3 и 16. Сумма: 19. * Добавить 3 в первую кучку: 6 и 8. Сумма: 14. * Добавить 3 во вторую кучку: 3 и 11. Сумма: 14. Ход 3: Игрок 1 Рассмотрим лучший ход для Игрока 2: удвоить вторую кучку (3 и 16. Сумма: 19). Теперь Игрок 1 может выиграть, удвоив вторую кучку: 3 и 32. Сумма: 35. То есть, первый игрок может гарантированно победить своим третьим ходом. Ответ: Первый игрок гарантированно побеждает своим третьим ходом.