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


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

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

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

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

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

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

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

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

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

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

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

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


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


doPDF

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

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


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

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

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

I34
74
64
38
38

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

II74
114
144
78
78
64
104
124
68
68
38
78
68
312
316

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

III114
154
224
118
118
144
184
284
148
148
78
118
148
712
716
104
144
204
108
108
124
164
244
128
128
68
108
128
612
616
312
712
612
316
324
316
716
616
320
332

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

III114
154
224
118
118
144
184
284
148
148
78
118
148
712
716
104
144
204
108
108
124
164
244
128
128
68
108
128
612
616
312
712
612
316
324
316
716
616
320
332

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

IV154
194
304
158
158
118
158
228
1112
1116
184
224
364
188
188
148
188
288
1412
1416
712
1112
1412
716
724
716
1116
1416
720
732
144
184
284
148
148
204
244
404
208
208
108
148
208
1012
1016
164
204
324
168
168
128
168
248
1212
1216
612
1012
1212
616
624
616
1016
1216
620
632
316
716
616
320
332
320
720
620
324
340

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

V194
234
384
198
198
158
198
308
1512
1516
1112
1512
2212
1116
1124
716
1116
1416
720
732
184
224
364
188
188
148
188
288
1412
1416
1012
1412
2012
1016
1024
204
244
404
208
208
168
208
328
1612
1616
1212
1612
2412
1216
1224
616
1016
1216
620
632
320
720
620
324
340

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

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

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

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

V194
234
384
198
198
158
198
308
1512
1516
1112
1512
2212
1116
1124
716
1116
1416
720
732
184
224
364
188
188
148
188
288
1412
1416
1012
1412
2012
1016
1024
204
244
404
208
208
168
208
328
1612
1616
1212
1612
2412
1216
1224
616
1016
1216
620
632
320
720
620
324
340

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

IV154
194
304
158
158
118
158
228
1112
1116
184
224
364
188
188
148
188
288
1412
1416
712
1112
1412
716
724
716
1116
1416
720
732
144
184
284
148
148
204
244
404
208
208
108
148
208
1012
1016
164
204
324
168
168
128
168
248
1212
1216
612
1012
1212
616
624
616
1016
1216
620
632
316
716
616
320
332
320
720
620
324
340

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

IV154
194
304
158
158
118
158
228
1112
1116
184
224
364
188
188
148
188
288
1412
1416
712
1112
1412
716
724
716
1116
1416
720
732
144
184
284
148
148
204
244
404
208
208
108
148
208
1012
1016
164
204
324
168
168
128
168
248
1212
1216
612
1012
1212
616
624
616
1016
1216
620
632
316
716
616
320
332
320
720
620
324
340

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

III114
154
224
118
118
144
184
284
148
148
78
118
148
712
716
104
144
204
108
108
124
164
244
128
128
68
108
128
612
616
312
712
612
316
324
316
716
616
320
332

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

III114
154
224
118
118
144
184
284
148
148
78
118
148
712
716
104
144
204
108
108
124
164
244
128
128
68
108
128
612
616
312
712
612
316
324
316
716
616
320
332

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

II74
114
144
78
78
64
104
124
68
68
38
78
68
312
316

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

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

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



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


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

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

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



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