Ошибочная гипотеза
ИнфоКонсалтинг
Образовательный сервис


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

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

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

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

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

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

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

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

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

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

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

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


"Ошибочная гипотеза"


Payeer

"Ошибочная гипотеза"

Вашему вниманию предлагается СТАНДАРТНЫЙ аналог задачи КИМ ЕГЭ. Задачи подобного рода встречались в условиях реального экзамена.

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


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

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

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

I35
65
95
310
315

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

II65
125
185
610
615
95
185
275
910
915
310
610
910
320
330
315
615
915
330
345

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

II65
125
185
610
615
95
185
275
910
915
310
610
910
320
330
315
615
915
330
345

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

III125
245
365
1210
1215
185
365
545
1810
1815
610
1210
1810
620
630
615
1215
1815
630
645
910
1810
2710
920
930
915
1815
2715
930
945
320
620
920
340
360

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

IV1210
2410
3610
1220
1230
1215
2415
3615
1230
1245
1810
3610
5410
1820
1830
1815
3615
5415
1830
1845
620
1220
1820
640
660
920
1820
2720
940
960

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

V1220
2420
3620
1240
1260
1820
3620
5420
1840
1860

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

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

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

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

V1220
2420
3620
1240
1260
1820
3620
5420
1840
1860

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

IV1210
2410
3610
1220
1230
1215
2415
3615
1230
1245
1810
3610
5410
1820
1830
1815
3615
5415
1830
1845
620
1220
1820
640
660
920
1820
2720
940
960

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

IV1210
2410
3610
1220
1230
1215
2415
3615
1230
1245
1810
3610
5410
1820
1830
1815
3615
5415
1830
1845
620
1220
1820
640
660
920
1820
2720
940
960

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

III125
245
365
1210
1215
185
365
545
1810
1815
610
1210
1810
620
630
615
1215
1815
630
645
910
1810
2710
920
930
915
1815
2715
930
945
320
620
920
340
360

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

III125
245
365
1210
1215
185
365
545
1810
1815
610
1210
1810
620
630
615
1215
1815
630
645
910
1810
2710
920
930
915
1815
2715
930
945
320
620
920
340
360

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

II65
125
185
610
615
95
185
275
910
915
310
610
910
320
330
315
615
915
330
345

Как видно, с гипотезой мы ошиблись. Перед нами — схема первого хода якобы выигрывающего игрока. Мы видим, что если "первый" начнёт игру, выполнив комбинацию {6, 5}, "второй" ответит комбинацией {6, 10}; если "первый" сделает комбинацию {9, 5}, "второй" сможет удачно составить {9, 10}; если "первый" своим ходом выполнит {3, 10}, то у "второго" есть целых три удачных ответа. Только вот "второй" ничего полезного для себя не сможет сделать в ответ на ход "первого" {3, 15}.

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

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

IV1210
2410
3610
1220
1230
1215
2415
3615
1230
1245
1810
3610
5410
1820
1830
1815
3615
5415
1830
1845
620
1220
1820
640
660
920
1820
2720
940
960

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

III125
245
365
1210
1215
185
365
545
1810
1815
610
1210
1810
620
630
615
1215
1815
630
645
910
1810
2710
920
930
915
1815
2715
930
945
320
620
920
340
360

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

III125
245
365
1210
1215
185
365
545
1810
1815
610
1210
1810
620
630
615
1215
1815
630
645
910
1810
2710
920
930
915
1815
2715
930
945
320
620
920
340
360

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

II65
125
185
610
615
95
185
275
910
915
310
610
910
320
330
315
615
915
330
345

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

II65
125
185
610
615
95
185
275
910
915
310
610
910
320
330
315
615
915
330
345

Хотя бы одна такая комбинация нашлась. Посмотрим её на первом ходе и сделаем соответствующий вывод:

I35
65
95
310
315

Гипотеза о том, что выигрывает "первый" игрок, доказана!

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

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



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


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

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

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



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