infoegehelp.ru

Успешно сдать ЕГЭ по информатике
  • Главная
  • Контакты
  • Карта сайта
  • Помощь сайту
Важно
  • Демо варианты ЕГЭ
  • Учим числа: 2 в степени
  • Биты, байты, килобайты
Решение задач
  • Задачи вне основных разделов информатики
Разделы информатики
  • 2011-12-18-14-33-54Системы счисления
  • 2011-12-18-16-45-20Алгебра логики
  • 2011-12-18-16-55-26Программирование
  • 2011-12-18-16-53-40Кодирование информации
  • 2011-12-18-16-56-19Компьютерные сети и Интернет
  • -excelЭлектронные таблицы (Excel)
  • 2011-12-18-16-57-50Базы данных
  • 2011-12-18-16-58-50Графы
  • 2011-12-18-17-00-15Файловая система
  • Устройство компьютера
  • ПО компьютера

Разбор задачи C3 (демо ЕГЭ 2007)

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

Введем обозначения:

х - первая куча,

у - вторая куча.

Старт: (х, у).

Варианты хода игроков: (х*3,у), (х,у*3), (х+1,у), (х, у+1).

Игрок выйграет, когда число камней в 2-х кучах станет ≥16 (х+у≥16). Изобразим ход игры в виде дерева решений. Необходимо ветвить дерево до того момента, когда все варианты последнего хода станут выйгрышными.

После первого хода дерево будет выглядеть так:

Задача С3 ЕГЭ по информатике 2007 первый ход

На дереве изображены все возможные варианты ходов. Одним цветом в строке подчертнуты одинаковые значения количества камней в кучах. По ходу игры будем ветвить только разные координаты.

После первых 2-х ходов дерево будет выглядеть так:

Задача С3 ЕГЭ по информатике 2007 второй ход

Когда 2-й игрок совершает 2-й ход, он выигрывает, когда попадает в позиции: (27,2) и (3,18), т.к. сумма х и у в этих случаях больше 16. На рисунке выйгрышная позиция 2-го игрока выделена сплошной рамкой.

Мы не рассматривали остальные позиции (обозначены как "..."), если встречали выйгрышную позицию.  Игроки играют безошибочно, поэтому 2-й игрок пойдет только по выйгрышной ветке. Соответственно, нет смысла рассматривать все позиции. Например, из позиции (9,2) 2-й игрок обязательно пойдет в (27,2), а не в (9,6), например.

Смотрим предыдущий ход. Чтобы 2-й игрок не выйграл, 1-й игрок на 1-м ходе не должен идти в позиции (9,2) и (3,6). Он может идти в остальные позиции. Запретные позиции для 1-го игрока перечеркнуты красным:

Задача С3 ЕГЭ по информатике 2007 запретные позиции 1-го игрока

Рассматривая дальнейшие ходы не будем ветвить позиции, которые идут из позиций (9,2) и (3,6). После 3-х ходов дерево будет выглядеть так:

Задача С3 ЕГЭ по информатике 2007 третий ход

Когда 1-й игрок совершает 3-й ход, он выигрывает, когда попадает в позиции: (36,2), (12,6), (15,2), (27,3) и (9,9), т.к. сумма х и у в этих случаях ≥16. На рисунке выйгрышные позиции 1-го игрока на 3-м ходу выделены сплошной рамкой.

Смотрим предыдущий ход. Чтобы 1-й игрок не выйграл, 2-й игрок на 2-м ходе не должен идти в позиции (12,2), (4,6), (5,2) и (9,3), (3,9). Он может идти в остальные позиции. Запретные позиции для 2-го игрока перечеркнуты красным:

Задача С3 ЕГЭ по информатике 2007 запретные позиции 2-го игрока

Рассматривая дальнейшие ходы не будем ветвить позиции, которые идут из позиций (12,2), (4,6), (5,2) и (9,3), (3,9). После 4-х ходов дерево будет выглядеть так:

Задача С3 ЕГЭ по информатике 2007 четвертый ход

Из рисунка видно, что любой ход 2-ого игрока на 4-м ходу будет выйгрышным. Поэтому, выигрывает 2-й игрок.

Представим решение также в виде таблицы (выйгрышные ходы выделены розовым):


1 ход2 ход3 ход4 ход
Старт1-й игрок
(все ходы)
2-й игрок
(выйгрышный ход)
1-й игрок
(все ходы)
2-й игрок
(выйгрышный ход
(один из вариантов))
3,2 9,2 27,2 -
-
3,6 3,18 --
4,2
4,3
12,3
36,3
4,9
12,9
5,3
15,3
4,4
12,4
3,3
4,3
те же ходы, что описаны выше
3,4
9,4
27,4
3,12
9,12
4,4
12,4
3,5
3,15

Выигрывает 2-й игрок.
Варианты его первого хода представлены в таблице выше, в столбце, выделенном розовым. Если 1-й игрок 1-м ходом утраивает число камней в 1-й или 2-й куче, то 2-й игрок выигрывает своим 1-м ходом, попадая в позиции (27,2) и (3,18). При остальных ходах 1-го игрока 2-й игрок выигрывает своим 2-м ходом.

Перейти к другим задачам.

 

Rambler's Top100

© Латыпова В.А., 2012-2020. Все права защищены.
Копирование материалов сайта только с разрешения администрации сайта