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


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

24.08.2017 Поздравляем учителей, преподавателей, учащихся и их родителей с началом нового учебного года! Пусть он окажется успешным и даст много полезных и нужных знаний.

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

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

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

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

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

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

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

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

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

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


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


doPDF

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

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


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

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

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

I12
32
32
14
16

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

I12
32
32
14
16

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

Все варианты первого хода другого игрока (второго хода игры) строятся на основе двух оставшихся производящих комбинаций: {3, 2} и {1, 4}.

II32
52
92
34
36
14
34
34
16
112

Здесь мы уже обозначили ходы, приводящие к проигрышу, но теперь они относятся ко "второму" игроку. Как видно, на третий ход в игре остаётся единственно возможная производящая комбинация — {3, 4}.

III34
54
94
36
312

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

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

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

III 34
54
94
36
312

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

II32
52
92
34
36
14
34
34
16
112

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

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

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

Итак, выигрывает игрок, делающий в игре ход вторым. Для того, чтобы выиграть, он должен получить (или сохранить) после своего первого хода 4 камня во второй кучке.

    • А что, разве не так? Согласно поставленному условию, ответ просто замечательный.

    • Разумеется, ответ можно сформулировать по-другому, сделав акцент, например, на количестве камней в первой кучке (правда, ограничивая количество камней во второй). В данном случае вообще можно указать единственно возможную к получению "вторым" игроком комбинацию {3, 4}.



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


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

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

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



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