СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости


Задания
Версия для печати и копирования в MS Word
Задание 26 № 3599

Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй — 6 камней. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 24 камней. Кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

Решение.

Выигрывает первый игрок, своим первым ходом он должен добавить 2 камня в первую кучу. Для доказательства рассмотрим неполное дерево игры, оформленное в виде таблицы, где в каждой ячейке записаны пары чисел, разделённые запятой. Эти числа соответствуют количеству камней на каждом этапе игры, в первой и второй кучах соответственно.
2 ход3 ход4 ход5 ход
Позиция после первого ходаII-й игрок (все варианты хода)I-й игрок (выигрышный ход)II-й игрок (все варианты хода)I-й игрок (один из вариантов)Пояснение
5,65,87,814,828,8Первый игрок выигрывает на пятом ходу, после любого ответа второго игрока, например, удвоив число камней в самой большой куче.
9,818,8
7,167,32
7,107,20
7,67,8Те же варианты четвёртого и пятого ходов.
5,125,24Первый игрок выиграл.
10,620,6Первый игрок выиграл.
Таблица содержит все возможные варианты ходов второго игрока. Из неё видно, что при любом ответе второго игрока у первого имеется ход, приводящий к победе.