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


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

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

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

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

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

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

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

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

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

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

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

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


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




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

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


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

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

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

I-2-1
1-1
-23
01

В схеме первого хода пока отсутствуют следственные комбинации, получение которых противоречит выигрышной стратегии. Рассмотрим теперь все варианты первого хода другого игрока (второй ход игры).

II1-1
4-1
13
31
-23
13
-27
05
01
31
05
23

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

II1-1
4-1
13
31
-23
13
-27
05
01
31
05
23

Как видно из схемы второго хода игры, перед третьим ходом существуют пять различных комбинаций (производящие комбинации третьего хода), которые имеет смысл рассматривать. Обратите внимание, что, например, комбинации {1, 3} и {3, 1} не совпадают, ведь все комбинации, получаемые в игре, являются упорядоченными парами! Материал на эту тему можно прочитать в §2 раздела "Дискретная математика"/"Элементы теории множеств". Также имеет смысл посмотреть пример получения упорядоченных пар из того же параграфа.

Покажем, в чём состоят возможности третьего хода.

III4-1
7-1
43
61
13
43
17
35
31
61
35
53
05
35
09
27
23
53
27
45

Здесь уже применено введённое нами ранее условное обозначение. Мы видим, что второй ход "первого" игрока (он же — третий в игре) допускает возможность его поражения в одном из случаев. Но гипотезу строить пока рано: необходимо построить дерево игры до конца.

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

IV43
73
47
65
53
83
57
75

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

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

Первая гипотеза касается поражения "второго" игрока и, соответственно, победы "первого" (ведь тактический проигрыш приходится на описание хода "второго" игрока).

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

IV43
73
47
65
53
83
57
75

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

III4-1
7-1
43
61
13
43
17
35
31
61
35
53
05
35
09
27
23
53
27
45

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

III4-1
7-1
43
61
13
43
17
35
31
61
35
53
05
35
09
27
23
53
27
45

Условные обозначения показывают, что на предыдущем ходе следует отыскать все производящие комбинации третьего хода, кроме {0, 5}. Отметим их:

II1-1
4-1
13
31
-23
13
-27
05
01
31
05
23

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

II1-1
4-1
13
31
-23
13
-27
05
01
31
05
23

Такая комбинация — единственная {1, -1}. Отметим её на первом ходе:

I-2-1
1-1
-23
01

Мы добрались до первого хода выигрывающего по выдвинутой гипотезе игрока и видим, что его верным начальным ходом является смещение фишки вправо. Только в этом случае "первый" игрок сможет победить. Гипотеза доказана!

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

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



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


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

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

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



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