Решение задачи C3 (2009 г.)
ИнфоКонсалтинг
Образовательный сервис


Новости сайта

02.10.2017 С наступающим Днём Учителя, дорогие наши учителя!

24.08.2017 Успейте подобрать репетитора на новый учебный год! Это можно сделать на соответствующей странице нашего сайта, притом по любому предмету, в любом городе России и с учётом индивидуальных требований.

Сервис предоставлен Ассоциацией репетиторов.

Найти репетитора

Отправить заявку

24.08.2017 Страницы сайта переиндексированы для системы поиска ИнфоКонсалтинг.

Поиск по нашему сайту

04.10.2016 В разделе "К экзамену" появилось решение задачи 23 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 23 демо-версии 2017 г. по информатике

04.10.2016 В разделе "К экзамену" появилось решение задачи 26 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 26 демо-версии 2017 г. по информатике


Решение задачи C3 на примере официальной демо-версии КИМ ЕГЭ 2009 г.


Perfect Money

Решение задачи C3 на примере официальной демо-версии КИМ ЕГЭ 2009 г.

Текст задачи. Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (5, 2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x, y) в одну из трёх точек: или в точку с координатами (x+3, y), или в точку с координатами (x, y+3), или в точку с координатами (x, y+4). Выигрывает игрок, после хода которого расстояние по прямой от фишки до точки с координатами (0, 0) не меньше 13 единиц. Кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.


Решение. Данная задача относится к первому типу задач, ведь в ней фактически говорится о том, что "выигрывает игрок, сделавший ход…" Представим решение схематическим способом, из частичных схем которого видны все возможные действия игроков.

Выполним первый пункт Плана решения задачи (см. Теоретическое введение).

Покажем все возможные варианты первого хода (относящегося к игроку, которого можно условно именовать "первым"):

I52
82
55
56

В схеме первого хода пока отсутствуют следственные комбинации, получение которых противоречит выигрышной стратегии. Рассмотрим теперь все варианты первого хода другого игрока (второй ход игры), учитывая, что все следственные комбинации на протяжении всей игры следует расценивать как упорядоченные пары (см. соответствующие определения в §2 раздела "Дискретная математика"/"Элементы теории множеств", а также пример получения упорядоченных пар в том же параграфе).

II82
112
85
86
55
85
58
59
56
86
59
510

Заметим, что некоторые следственные комбинации нельзя получать "второму" игроку, иначе он проиграет. Введём условное обозначение, заключающееся в заливке красным цветом тех комбинаций, получение которых противоречит условию (не соответствует выигрышной стратегии). Тогда схема первого хода "второго" игрока будет выглядеть так:

II82
112
85
86
55
85
58
59
56
86
59
510

Докажите самостоятельно, что получение "вторым" игроком комбинаций, отмеченных красной заливкой, приведёт к его проигрышу.

Обратите внимание, что комбинации {8, 5} и {5, 8} не представляют собой одну и ту же ситуацию, ведь все комбинации, получаемые в игре, — упорядоченные пары! И даже не потому, что содержат координаты. Напомним, что материал на эту тему можно прочитать в §2 раздела "Дискретная математика"/"Элементы теории множеств", где есть пример получения упорядоченных пар.

Как видно из схемы второго хода игры, перед третьим ходом существуют всего две комбинации (производящие комбинации третьего хода), которые имеет смысл рассматривать.

III85
115
88
89
86
116
89
810

Взятые вместе, с учётом их следственных комбинаций, они образуют тактический проигрыш, что означает завершение процесса построения дерева игры. Значит, можно начать выполнение второго этапа Плана решения задачи (см. Теоретическое введение).

Необходимо выдвинуть гипотезу о выигрывающем игроке (п. 2а). Сразу заметим, что дерево содержит два локальных проигрыша, составляющих один тактический. Третий ход в игре, на котором завершилось построение дерева игры, — за "первым" игроком. Из схемы этого хода видно, что он проигрывает, потому что все следственные комбинации — "красные", т. е. любой ответный ход соперника приводит к его же (соперника) выигрышу (задача первого типа). Значит, гипотеза, которую мы рассмотрим, состоит в том, что выигрывает "второй" игрок.

Приступим к доказательству или опровержению нашей гипотезы (п. 2б). Итак, для того, чтобы выиграть, "второму" игроку нужно получить перед третьим ходом в игре одну из комбинаций {8, 5} или {8, 6}. Обозначим жёлтым цветом комбинации, выгодные для "второго" игрока.

III85
115
88
89
86
116
89
810

На предыдущем ходе игры найдём все "жёлтые" комбинации и отметим их точно так же:

II82
112
85
86
55
85
58
59
56
86
59
510

Ход (II) — первый ход выигрывающего по нашей гипотезе игрока, значит, переход к предыдущему ходу осуществлять не требуется. Мы видим, что любая производящая комбинация второго хода игры предполагает хотя бы одну удачную следственную комбинацию для "второго" игрока, из чего вытекает, что нам удалось доказать выдвинутую гипотезу.

    • В данной задаче другого решения быть не могло: дерево игры содержит один тактический проигрыш при отсутствии локальных проигрышей, не составляющих тактический. В реальных задачах КИМ ЕГЭ такая ситуация — большая редкость.

Осталось выполнить третий этап Плана решения задачи (см. Теоретическое введение) — записать ответ. Заметим, что частью ответа является продемонстрированное решение, ведь в условии задачи упомянуто об обосновании ответа.

Итак, выигрывает игрок, делающий в игре ход вторым. Для того, чтобы выиграть, он должен сделать такой свой первый ход, чтобы абсцисса фишки оказалась равной 8.



Поддержите нас!


Обращаем Ваше внимание:

Ваш браузер недостаточно эффективен. Установите достойный браузер здесь.

Все анонсы? / ?



Индекс цитирования
CY, Page Rank
Яндекс.Метрика