Решение задачи C3: первая демо-версия КИМ ЕГЭ (2013 г.)
ИнфоКонсалтинг
Образовательный сервис


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

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

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

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

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

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

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

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

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

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

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

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


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




Решение задачи C3 на примере демо-версии КИМ ЕГЭ 2013 г.,
предложенной для общественно-профессионального обсуждения

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


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

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

Покажем все возможные варианты первого хода (Пети):

I43
63
123
45
49

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

I43
63
123
45
49

Теперь рассмотрим все варианты ответа Вани — его первого хода:

II63
83
183
65
69
45
65
125
47
415
49
69
129
411
427

Здесь уже видно, что задача имеет "смешанный" тип: Ваня, выполняя ход и получая 27 камней во второй куче, проигрывает! Поэтому мы и воспользовались тем же условным обозначением (красной заливкой) для комбинации {4, 27}, получение которой означает непосредственный проигрыш. Так же будем поступать и далее. Рассмотрим теперь второй ход Пети:

III65
85
185
67
615
125
145
365
127
1215
415
615
1215
417
445
129
149
369
1211
1227
411
611
1211
413
433

Вероятно, появляется ощущение, что Петя проиграет: в большинстве своём какой бы ход он ни сделал, — либо ошибка, либо проигрыш. Однако гипотезу строить всё-таки рано! Лучше определимся со всеми вариантами второго хода Вани:

IV85
105
245
87
815
67
87
127
69
621

Что ж, для Пети остаётся возможность выполнения своего третьего хода:

V105
125
305
107
1015
815
1015
2415
817
845

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

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

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

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

V105
125
305
107
1015
815
1015
2415
817
845

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

IV85
105
245
87
815
67
87
127
69
621

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

IV85
105
245
87
815
67
87
127
69
621

Отыщем все "жёлтые" производящие комбинации четвёртого хода на третьем ходе игры. Впрочем, такая комбинация единственная:

III65
85
185
67
615
125
145
365
127
1215
415
615
1215
417
445
129
149
369
1211
1227
411
611
1211
413
433

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

III65
85
185
67
615
125
145
365
127
1215
415
615
1215
417
445
129
149
369
1211
1227
411
611
1211
413
433

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

II63
83
183
65
69
45
65
125
47
415
49
69
129
411
427

И тут выясняется очень плохая для Вани новость: он может выиграть только в том случае, если Петя сделает свой первый ход, утроив количество камней во второй куче. А зачем Петя будет это делать? Ведь такой ход противоречит выигрышной стратегии Пети. Если она, конечно, есть. Вот теперь как раз и требуется доказать наличие такой стратегии. То есть, нам придётся отказаться от выдвинутой первоначально гипотезы, потому что мы её только что опровергли. Итак, пусть выигрывает Петя… Рассмотрим, как Ваня проиграет игру, изучив для начала её четвёртый ход. Введём ещё одно условное обозначение: пусть удачные теперь уже для Пети комбинации будут отмечены зелёной заливкой.

IV85
105
245
87
815
67
87
127
69
621

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

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

IV85
105
245
87
815
67
87
127
69
621

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

III65
85
185
67
615
125
145
365
127
1215
415
615
1215
417
445
129
149
369
1211
1227
411
611
1211
413
433

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

III65
85
185
67
615
125
145
365
127
1215
415
615
1215
417
445
129
149
369
1211
1227
411
611
1211
413
433

а затем отыщем на втором:

II63
83
183
65
69
45
65
125
47
415
49
69
129
411
427

Здесь, кстати, комбинация {4, 27} тоже "поменяла цвет".

Что естественно, для первого хода Пети выбирается только комбинация {6, 3}:

II63
83
183
65
69
45
65
125
47
415
49
69
129
411
427

Её и отметим тем же зелёным цветом на схеме первого хода:

I43
63
123
45
49

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

Выигрывает Петя. Для того, чтобы выиграть, он должен своим первым ходом добавить 2 камня в кучку с бо́льшим количеством камней.



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


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

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

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



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