Первый ход ничего не значит
ИнфоКонсалтинг
Образовательный сервис


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

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

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

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

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

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

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

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

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

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

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

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


"Первый ход ничего не значит"


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

"Первый ход ничего не значит"

    • Предложенный ниже вариант задачи до настоящего времени не встречался и, вероятно, не мог встретиться в реальных текстах КИМ ЕГЭ по информатике. Это можно утверждать по той причине, что рекомендуемых 30 минут для её решения явно мало. Однако рассматриваемый пример весьма полезен всем тем, кто собрался сдавать этот экзамен, поскольку позволяет применить методику решения подобных задач в наиболее полном виде.

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


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

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

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

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

I12
32
22
14
14

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

II32
52
62
34
34
22
42
42
24
24
14
34
24
16
18

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

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

Итак, третий ход игры:

III52
72
102
54
54
62
82
122
64
64
34
54
64
36
38
42
62
82
44
44
16
36
26
18
112
18
38
28
110
116

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

III52
72
102
54
54
62
82
122
64
64
34
54
64
36
38
42
62
82
44
44
16
36
26
18
112
18
38
28
110
116

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

IV72
92
142
74
74
102
122
202
104
104
54
74
104
56
58
82
102
162
84
84
122
142
242
124
124
64
84
124
66
68
36
56
66
38
312
38
58
68
310
316
62
82
122
64
64
44
64
84
46
48
18
38
28
110
116
112
312
212
114
124
110
310
210
112
120

Описание пятого хода станет самым длинным. Его схема содержит 16 производящих комбинаций:

V92
112
182
94
94
74
94
144
76
78
122
142
242
124
124
104
124
204
106
108
56
76
106
58
512
58
78
108
510
516
102
122
202
104
104
84
104
164
86
88
66
86
126
68
612
68
88
128
610
616
38
58
68
310
316
310
510
610
312
320
82
102
162
84
84
64
84
124
66
68
110
310
210
112
120
112
312
212
114
124

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

VI112
132
222
114
114
94
114
184
96
98
76
96
146
78
712
58
78
108
510
516
122
142
242
124
124
104
124
204
106
108
86
106
166
88
812
310
510
610
312
320
102
122
202
104
104
84
104
164
86
88
66
86
126
68
612
112
312
212
114
124

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

VII104
124
204
106
108
86
106
166
88
812
122
142
242
124
124

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

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

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

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

VII104
124
204
106
108
86
106
166
88
812
122
142
242
124
124

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

VI112
132
222
114
114
94
114
184
96
98
76
96
146
78
712
58
78
108
510
516
122
142
242
124
124
104
124
204
106
108
86
106
166
88
812
310
510
610
312
320
102
122
202
104
104
84
104
164
86
88
66
86
126
68
612
112
312
212
114
124

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

VI112
132
222
114
114
94
114
184
96
98
76
96
146
78
712
58
78
108
510
516
122
142
242
124
124
104
124
204
106
108
86
106
166
88
812
310
510
610
312
320
102
122
202
104
104
84
104
164
86
88
66
86
126
68
612
112
312
212
114
124

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

V92
112
182
94
94
74
94
144
76
78
122
142
242
124
124
104
124
204
106
108
56
76
106
58
512
58
78
108
510
516
102
122
202
104
104
84
104
164
86
88
66
86
126
68
612
68
88
128
610
616
38
58
68
310
316
310
510
610
312
320
82
102
162
84
84
64
84
124
66
68
110
310
210
112
120
112
312
212
114
124

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

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

IV72
92
142
74
74
102
122
202
104
104
54
74
104
56
58
82
102
162
84
84
122
142
242
124
124
64
84
124
66
68
36
56
66
38
312
38
58
68
310
316
62
82
122
64
64
44
64
84
46
48
18
38
28
110
116
112
312
212
114
124
110
310
210
112
120

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

III52
72
102
54
54
62
82
122
64
64
34
54
64
36
38
42
62
82
44
44
16
36
26
18
112
18
38
28
110
116

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

Значит, выигрывает всё-таки "первый" игрок, это — наша новая гипотеза. Но её надо доказать, определить стратегию и выяснить первый ход "первого" игрока.

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

VI112
132
222
114
114
94
114
184
96
98
76
96
146
78
712
58
78
108
510
516
122
142
242
124
124
104
124
204
106
108
86
106
166
88
812
310
510
610
312
320
102
122
202
104
104
84
104
164
86
88
66
86
126
68
612
112
312
212
114
124

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

V92
112
182
94
94
74
94
144
76
78
122
142
242
124
124
104
124
204
106
108
56
76
106
58
512
58
78
108
510
516
102
122
202
104
104
84
104
164
86
88
66
86
126
68
612
68
88
128
610
616
38
58
68
310
316
310
510
610
312
320
82
102
162
84
84
64
84
124
66
68
110
310
210
112
120
112
312
212
114
124

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

IV72
92
142
74
74
102
122
202
104
104
54
74
104
56
58
82
102
162
84
84
122
142
242
124
124
64
84
124
66
68
36
56
66
38
312
38
58
68
310
316
62
82
122
64
64
44
64
84
46
48
18
38
28
110
116
112
312
212
114
124
110
310
210
112
120

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

III52
72
102
54
54
62
82
122
64
64
34
54
64
36
38
42
62
82
44
44
16
36
26
18
112
18
38
28
110
116

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

II32
52
62
34
34
22
42
42
24
24
14
34
24
16
18
I12
32
22
14
14

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

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

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

    • Если бы вопрос касался первого значимого для выигрывающего игрока хода, то следовало бы предоставить, например, такой ответ:

      Выигрывает игрок, делающий в игре ход первым. Первым имеющим значение ходом является второй его ход, на котором он должен получить в одной из кучек 7, 8 или 12 камней при условии, что во второй кучке 2 камня; 6 камней при условии, что в другой кучке 3 камня; или 4 камня, если во второй кучке тоже 4 камня.



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


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

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

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



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