Задача 67. Задача на повторение понятий «перед каждой бусиной», «после каждой бусины». В ответе должно получиться слово КАРТОШКА.
Задача 68. Первое, что требуется в этой задаче, — осуществить полный перебор всех возможных ходов Первого и все эти ходы (их четыре, как подсказывает картинка) изобразить. Дальше нужно посмотреть, какие из получившихся позиций заключительные. Оказывается, что заключительных позиций из этих четырёх три и во всех трёх соответствующих партиях Первый проиграл. Для оставшейся четвёртой позиции в соответствии с условием задачи нужно найти все возможные варианты хода Второго и нарисовать все получающиеся позиции. Когда мы это сделаем, то окажется, что во всех позициях третьего уровня Второй проиграл, так что игра закончена.
Ответ:
Задача 69. В ходе решения подобных задач устанавливается связь между веткой дерева игры и отдельными партиями игры. Для начала ребятам необходимо понять, как связано дерево Н с цепочкой Q. Должны выполняться два условия: окончание цепочки Q — это путь дерева Н и число отрезков в заключительной позиции пути дерева Н должно соответствовать заданной длине цепочки Q. Ребята к настоящему моменту должны понимать: если в цепочке 9 бусин, значит, в партии сделано 8 ходов. Теперь ясно, что заключительными позициями партий с цепочкой Q могут быть лишь листья третьего уровня дерева Н.
Урок «Исследуем позиции на дереве игры»
К настоящему моменту ребята уже знакомы с понятием «выигрышная стратегия». Они умеют находить выигрышную стратегию для игры «камешки» с опорой на раскрашенную числовую линейку. Однако этот способ не является универсальным — с его помощью не получается найти выигрышную стратегию во всех играх с полной информацией. Причина проста: в других играх не удаётся расположить все позиции на числовой линейке, да и позиции часто не равноценны относительно двух игроков. Чтобы проанализировать все позиции большинства игр с полной информацией, необходимо построить дерево игры. В таком дереве имеются все возможные позиции игры и, начиная с листьев, эти позиции можно определить как выигрышные или проигрышные (если игра не допускает ничьей) по тем же правилам, которые были описаны на с. 27. (Если же игра допускает ничьи, то некоторые позиции будут ничейными.) Проанализировав все позиции в дереве, можно найти выигрышную стратегию для одного из игроков. Часто такую стратегию нельзя описать в виде простого правила и приходится искать различные способы, как описать её полно (для любой игры соперника), но более-менее кратко. Порой приходится описывать последовательность ходов для каждого варианта хода противника. Иногда помогают некоторые геометрические или арифметические соображения, позволяющие объединить разные позиции в группы и тем самым уменьшить объём описания стратегии. Вообще, в разных ситуациях проблема описания выигрышной стратегии может решаться по-разному. В примере на с. 45 в каждом случае вариант хода Первого единствен, поэтому выигрышная стратегия формулируется достаточно просто — одним предложением.
В процессе поиска выигрышной стратегии по дереву возникает только одна проблема — полное дерево игры для большинства игр очень большое и построить его затруднительно. Поэтому часто дети будут анализировать только ветку из дерева игры. Иногда дерево оказывается возможным «разобрать» на несколько веток, каждую из которых можно проанализировать, а затем собрать результаты воедино. Именно этим ребята будут заниматься в проекте «Стратегия победы». По сути, тема этого листа определений готовит ребят к проведению проекта.
Заметим, что даже в случае игры «камешки» (которую можно проанализировать с помощью числовой линейки) анализ позиций по дереву игры может быть полезен. Особенно это актуально в том случае, когда стратегия не формулируется в виде простого правила (проигрышные позиции не подчиняются строгой закономерности). В этом случае часто приходится рассматривать разные варианты ходов противника и для каждого указывать ответный ход игрока. Это, конечно, гораздо проще сделать по дереву, где все возможные варианты ходов из каждой позиции представлены явно. Например, попробуем сформулировать выигрышную стратегию для игры, описанной на с. 44. Начальная позиция проигрышная, значит, выигрышная стратегия имеется у Второго. При этом Первый может сделать любой первый ход, и необходимо рассмотреть все варианты. По дереву видно, что если Первый на первом ходу возьмёт 1 камешек, то Второй должен взять 4 камешка и оставить Второму проигрышную позицию 2. Дальше исход игры оказывается предопределён. Если Первый на первом ходу возьмёт 3 камешка, то Второй должен взять 4 камешка и выиграть. Если Первый на первом ходу возьмёт 4 камешка, то Второй может взять любое число камешков (исход игры в обоих случаях предопределён).
Решение задач 70—75 из учебника
Задача 70. Построение дерева игры «камешки» — дело для ребят уже знакомое. Здесь интересно другое — при выполнении второго задания ребята наверняка заметят, что все проигрышные позиции находятся на уровнях с нечётными номерами, а все выигрышные — на уровнях с чётными номерами (если дети не заметят это сами, попросите их пометить уровни римскими цифрами I и II — номерами игроков, которые привели игру к этой позиции,). Это означает, что Первый не может выиграть в этой игре никогда. Соответственно Второй может играть как угодно, и выигрышная стратегия ему просто не нужна. Таким образом, Первый будет принудительно проигрывать, а Второй принудительно выигрывать. Вот почему любая партия данной игры будет разумной. Кого-то из ребят такая ситуация может смутить, поэтому приготовьтесь её прояснить. Если ребята решали задачу 42, возможно, стоит её вспомнить (а если не решали — стоит её решить, перед тем как решать задачу 70).
Ответ:
Задача 71. В этой задаче мы продолжаем готовить ребят к проекту «Стратегия победы». Для успешной работы с проектом необходимо уметь: во-первых, строить дерево игры, во-вторых, это дерево анализировать. Здесь ветка дерева уже построена. Чтобы выяснить, выигрышной или проигрышной является корневая позиция, кто из игроков обладает выигрышной стратегией из неё и в чём она заключается, необходимо, как обычно, проанализировать все позиции дерева, начиная с листьев. Для начала обведём все листья синим — это проигрышные позиции для игрока, чья очередь делать ход. Каждая позиция третьего уровня, которая не является листом, выигрышная, поскольку из неё можно сделать ход только в проигрышную позицию. Теперь проанализируем позиции второго уровня. Верхняя позиция проигрышная, поскольку все ходы из неё (а ход в данном случае один!) ведут в выигрышные позиции. Средняя позиция выигрышная, поскольку из неё существует ход в проигрышную позицию (в данном случае таких ходов два). Нижняя позиция также выигрышная, поскольку из неё существует ход в проигрышную позицию (вторую снизу позицию третьего уровня). Таким образом, корневая позиция выигрышная, поскольку из неё существует ход в проигрышную позицию (верхнюю позицию второго уровня). Значит, выигрышную стратегию из данной позиции имеет Первый. Цепочка разумной игры из корневой позиции совпадает с самым верхним путём дерева L.
Задача 72. Построение дерева D — задача, знакомая ребятам, вряд ли здесь потребуется ваша помощь. Заметим, что дерево D — ветка дерева с листа определений на с. 44. Поэтому, если кто-то затрудняется с построением дерева, попросите его ещё раз разобраться с листом определений. Все позиции, конечно, будут иметь те же цвета, что и на листе определений. В результате оказывается, что начальная позиция выигрышная, значит, выигрышную стратегию имеет Первый. У него есть возможность привести игру к одной из трёх позиций — 4, 2 и 1. При этом если он следует выигрышной стратегии, то должен сделать ход в проигрышную позицию 2. После этого исход игры определяется однозначно, и единственная разумная партия игры: 5 — 2 — 1 — 0.
Задача 73. Задача на повторение темы «Склеивание мешков цепочек», которая изучалась в курсе 2 класса. Напомним, что результатом склеивания двух мешков цепочек будет мешок, который состоит из всех цепочек, получающихся при склеивании цепочек из первого мешка с цепочками из второго мешка (к каждой цепочке из первого мешка приклеивается каждая цепочка из второго мешка). В данном случае длина каждой цепочки в мешке-результате равна 2, поэтому либо все цепочки в первом и втором мешках имеют длину 1, либо в одном из мешков лежат цепочки длины 0, а все цепочки во втором — длины 2. По условию в каждом из мешков есть непустая цепочка, значит, второй вариант исключается, остаётся только первый вариант. Ясно, что в первом мешке лежит цифра 2, а во втором — все цифры от 0 до 9. Только в этом случае при склеивании получается мешок М.
Задача 74. Необязательная. Ветка в задаче не нарисована полностью, а лишь намечена: во всех позициях, кроме корневой, нужно поставить ещё крестики и нолики. Посоветуйте детям не спешить, можно начать строить дерево на отдельном листе бумаги (используя запасные поля на вкладыше тетради проектов) или работать в тетради карандашом. Затрудняющимся в решении можно задать следующие вопросы:
1. Кто должен ходить из корневой позиции?
2. Сколько у него есть возможных ходов?
3. Есть ли среди этих ходов такой, который позволит выиграть сразу?
Если на все эти вопросы получены ответы, можно вернуться к решению задачи. Теперь ясно, где нужно нарисовать ход в позиции второго уровня, которая является листом. Остальные три возможных хода можно произвольно распределить по оставшимся вершинам уровня.
Следующие ходы крестиками также возникнут естественно. Учащиеся уже понимают, почему за корневой позицией у нас шло четыре позиции, а теперь за каждой позицией — только три. Важно сформировать здесь некоторую дисциплинированность работы, привычку к систематичности. В частности, полезно, как только сделан очередной выбор, т. е. дорисована позиция в одной из позиций, передать этот выбор по цепочке, точнее, по ветке, начинающейся в данной позиции. Это потребует определённой аккуратности и сосредоточенности. Далее надо не забывать отмечать заключительные позиции — сразу рисовать стрелки и не пытаться что-то выстраивать за ними.
На вид полученные детьми деревья могут различаться из-за того, что учащиеся могли в разном порядке перебирать возможности, однако в математическом смысле все эти деревья одинаковы. Мы приводим один из возможных вариантов дерева Q:
Второе задание (анализ позиций) не представляет большой сложности. Проигрышными здесь будут только позиции-листья, а все остальные позиции будут выигрышными. Действительно, у каждой позиции, которая не является листом, есть хотя бы один следующий лист (проигрышная позиция). Значит, из каждой такой позиции есть ход в проигрышную позицию (а сама позиция является выигрышной). Корневая позиция также является выигрышной, следовательно, выигрышная стратегия имеется у игрока, очередь которого делать ход (Второго). Вопрос об этой стратегии в задаче не приводится, поскольку ответ на него тривиален — Второй может выиграть у Первого за один ход, поставив нолик в верхний левый угол. Ответ на последний вопрос задачи также не представляет большой сложности. Чтобы построить искомую цепочку, достаточно найти хотя бы один лист на пятом уровне и построить ведущий в него путь. В данном случае таких листов два, поэтому имеется две подходящие цепочки.
Задача 75. Необязательная. При выполнении первого задания предоставьте ребятам полную свободу, такие задания уже должны быть по силам каждому. По окончании его выполнения напомните детям о необходимости проверки, которую можно провести как в индивидуальном порядке, так и в парах. В любом случае полезно спросить ребят, какие именно условия должны выполняться, чтобы цепочка была нарисована верно. Во-первых, все 4 точки на окружности должны быть попарно соединены. Это означает, что в заключительной позиции проведено 6 отрезков, а цепочка игры состоит из семи позиций. Во-вторых, при переходе от одной позиции к другой всегда должен добавляться один отрезок определённого цвета. В-третьих, в заключительной позиции (и предыдущей перед ней) не должно быть одноцветного треугольника, иначе партия не закончится ничьей. При выполнении второго задания полезно дать ребятам время подумать, а затем выслушать все мнения. Скорее всего, учащиеся сообразят, что игра на окружности с тремя точками всегда заканчивается ничьей, и выскажут свои соображения, которые вам, возможно, придётся обобщить. Действительно, на окружности с тремя точками, соединив все возможные пары точек, мы получим 3 отрезка. Учитывая очерёдность хода, два из них будут ходами Первого, один — ходом Второго, значит, одноцветного треугольника не возникнет.
Проект «Стратегия победы»
1-й этап. Работа с листом определений (тетрадь проектов, с. 3)
Цель данного проекта — обучение поиску выигрышной стратегии с помощью дерева игры на примере игры «ползунок» на поле 3×3. Из учебника ребятам известен следующий алгоритм поиска выигрышной стратегии:
1. Раскрасить все позиции игры красным или синим (как выигрышные или проигрышные), начиная с заключительной и вплоть до корневой позиции.
2. Выяснить, у кого в данной игре есть выигрышная стратегия: если корневая позиция красная, то у Первого; если синяя, то у Второго.
3. Сформулировать выигрышную стратегию либо в виде общего правила (игрок должен делать на каждом ходу так, чтобы...), либо в виде описания последовательности ходов в зависимости от ходов противника.
Иногда все возможные позиции нужно располагать на числовой линейке, как в игре «камешки», иногда на круглой числовой линейке, как в игре «стрелки», иногда на шахматном поле, как в игре «король». Позиции для игры «ползунок» удобнее всего анализировать по дереву игры.
Итак, нам нужно построить дерево игры «ползунок». Это дерево очень большое. Чтобы справиться с поставленной задачей, на листе определений ребята знакомятся с понятием «одинаковые позиции» для данной игры. Действительно, с точки зрения продолжения игры такие позиции не различаются, а значит, все одинаковые позиции либо одинаково выигрышные, либо проигрышные. Для демонстрации того, что две позиции одинаковы, полезно иметь заготовки прозрачных полей для «ползунка» 3×3, на которых можно нарисовать две данные позиции и совместить их наложением.
После того как ребята поработают с листом определений, устройте общее обсуждение, в ходе которого станет ясно, хорошо ли усвоили дети понятие «одинаковые позиции». Для этого достаточно нарисовать на доске несколько пар позиций и спросить, какие из них одинаковы.
Теперь при построении дерева игры «ползунок» мы можем прорисовывать лишь одну из всех веток, выходящих из одинаковых позиций.
2-й этап. Изучение начального фрагмента дерева игры для первых пяти уровней (тетрадь проектов, с. 4—6)
На этом этапе происходит общее обсуждение, в ходе которого все ребята должны разобраться, каким образом построены первые пять уровней дерева. Можно начать строить первые два уровня дерева и без опоры на рисунок на с. 4. Для этого надо нарисовать корневую позицию на доске и попросить ребят нарисовать все возможные позиции, которые могут получиться после первого хода Первого. Мешок позиций составляется всем классом, каждый учащийся, который считает, что на доске не все позиции, может выйти и предложить новые позиции. После этого нужно вместе проверить, все ли позиции нарисованы на доске (всего их должно быть 12). Затем необходимо рассортировать позиции — выделить одинаковые и оставить только по одному экземпляру. Если вы чувствуете, что такая работа пошла очень тяжело, попросите ребят открыть тетрадь проектов на с. 4 и просто рассмотреть первые три уровня.
Можно аналогично поработать и с позициями третьего уровня — для двух различных позиций второго уровня (2a и 2i) нарисовать все возможные следующие, затем среди всех получившихся позиций третьего уровня найти одинаковые. Завершая эту работу, ребята должны обратиться к с. 4 и проверить, совпадают ли первые три уровня дерева, построенные в ходе общего обсуждения, с началом дерева в тетради проектов. Здесь же необходимо ответить на все возникшие в ходе работы вопросы.
Далее ребята работают с позициями четвёртого и пятого уровней. Попросите детей разобрать фрагменты дерева по готовому рисунку. При этом сильным учащимся можно предложить сначала попытаться построить мешок всех позиций соответствующего уровня самостоятельно. Другой вариант (групповой) — разбить детей на 5 групп, выдать каждой группе одну позицию третьего уровня и попросить построить мешок всех следующих за ней позиций (четвёртого уровня). Затем всю полученную информацию следует отобразить на доске и выделить среди позиций четвёртого уровня одинаковые. Различные позиции четвёртого уровня опять раздаются по группам (их снова будет 5), и для каждой из них группа ищет мешок всех следующих позиций. Работа завершается выделением на пятом уровне всех различных позиций (их можно нарисовать на доске). В любом случае обсуждение того, почему какие-то позиции одинаковы, следует проводить всем классом. |
