Внеклассная работа с одаренными детьми


МБОУ «СОШ №143» г. Красноярска,
Учитель математики высшей категории
Князькина Татьяна Викторовна,
2013год.
Внеклассная работа с одаренными детьми.
Игры
Задачи про игры - весьма популярный вид олимпиадных задач, особенно в младших классах. Как показывает опыт, наиболее общая проблема у начинающих - понять, "что вообще от нас хотят", какие рассуждения являются правильным решением задачи, а какие - нет.
Обычно предполагается (и мы не будем в дальнейшем это специально указывать!), что играют двое, делая ходы по очереди (пропускать свой ход нельзя!), а в задаче спрашивают "кто выиграет при правильной игре?"
Стандартная ошибка по сути - понимать слова "при правильной игре" так, как будто оба противника играют оптимальным для себя образом (тем более, что решающий задачу часто неправильно понимает, что такое "оптимальным образом"!).
Тогда придумывается выигрышная стратегия, дающая ответ только на оптимальный ход противника (обычно еще "оптимальным" считается такой ход, когда противник следует придуманной нами же стратегии - хотя для другого игрока такая стратегия может быть, наоборот, совсем никудышной!!!).
На самом деле, надо уметь придумывать ответ на любой ход противника, каким бы идиотским он нам не казался.
Обычно правильная стратегия, в отличие от липы, не имеет случаев разной сложности, а с одинаковой легкостью находит достойный ответ на любой ход!
Под понятием математической игры мы понимаем игру двух соперников, обладающую следующим свойством:
В каждый момент игры состояние характеризуется позицией, которая может изменяться только в зависимости от ходов игроков.
Для каждого из игроков некоторые позиции объявляются выигрышными.
Добиться выигрышной для себя позиции и есть цель каждого.
Иногда игры допускают ничью. Это означает, что ни один из игроков не может добиться выигрышной для него позиции, или некоторые позиции объявлены ничейными.
Например, шахматы, шашки, крестики-нолики являются математическими играми. А игры в кости, домино, большинство карточных игр математическими играми не являются, так как состояние игры зависит не только от ходов соперника, но и от расклада или результата бросания кости.
В математических играх существуют понятия выигрышной стратегии, т. е. набора правил (можно сказать, инструкции или алгоритма), следуя которым, один из игроков обязательно выиграет (не зависимо от того, как играет его соперник), и ничейной стратегии, следуя которой один
из игроков обязательно добьётся либо выигрыша, либо ничьей.
В любой математической игре существует либо выигрышная стратегия для одного из игроков, либо ничейные стратегии для обоих (если игра допускает ничью). В зависимости от этого игра называется выигрышной для первого или второго игрока, или ничейной.
Например крестики-нолики (на доске 3 × 3) являются ничейной игрой. К какому из перечисленных случаев относятся шахматы и шашки неизвестно. Хотя стратегия (либо выигрышная, либо ничейная) в этих играх существует, она не найдена, поэтому соревнования по этим играм пока представляют интерес.
Виды игр:
Игры- шутки
Симметрия
Выигрышная позиция
Анализ выигрышной позиции
Игры- шутки
Самый первый и простой класс игр — игры-шутки.
Это игры, исход которых не зависит от того, как играют соперники.
Поэтому для решения такой игры-задачи не нужно указывать выигрышную стратегию. Достаточно лишь доказать, что выигрывает тот или иной игрок (независимо от того, как будет играть!).
Для доказательства обычно находится какая-то величина, которая понятно чему равна в начале и конце и понятно как изменяется на каждом ходу - тут даже часто число ходов до конца однозначно посчитать можно. Либо какой-то инвариант (т.е. что-то, не меняющееся ни при каком ходе), однозначно зависящий от начальной позиции (чаще всего - от четности) и определяющий выигравшего в конце.
Советы для преподавателей:
-Игры-шутки позволяют снять напряжение и усталость, дают школьникам возможность отдохнуть.
-Удобно давать их по одной после изложения трудного материала, в критический момент или в конце занятия.
-Не следует проводить целое занятие, посвященное играм-шуткам.
-Полезно перед решением задачи-игры дать школьникам возможность немного поиграть друг с другом.
Игры шутки
Задача 1: Двое по очереди ломают шоколадку 5x8. За ход можно разломать любой кусок по прямой линии между дольками. Проигрывает тот, кто не может сделать ход.
Решение: Долек всегда будет 5x8=40 штук, а шоколадка в начале была одна. Заметим, что на каждом ходу один кусок шоколадки всегда разламывается на 2, т.е. количество различных кусков шоколадки увеличивается на 1. В начале это кол-во было равно 1, а в конце, как мы заметили, 40. Значит, игра продолжалась ровно 39 ходов ("ходом" мы называем ход одного игрока, а не пару "ход - ответный ход"). Поэтому последний (39-й) ход был обязательно ходом первого (его ходы - первый, третий и все с нечетными номерами) - и первый выиграл.
Вот такая получилась шутка - как ни ходи, первый всегда выигрывает .
Задача 2: Решить ту же задачу в общем виде, про шоколадку MxN.
Решение: (Должно получиться, что второй выигрывает, если M и N оба нечетные, а иначе выигрывает первый.)
Задача 3: На доске написаны 10 нулей и 10 единиц. За ход можно стереть две любые цифры и написать вместо них 0, если они были одинаковые или 1, если они были разные. Если на доске остается 1 - выигрывает первый. Если 0 - второй.
Решение: Выигрыш зависит от четности последнего числа. Действительно, сумма двух одинаковых цифр - четна и, вычитая ее, мы прибавляем четный ноль. А сумма двух разных цифр - нечетна (0+1=1), и мы прибавляем вместо нее нечетную единицу. Исходно сумма всех чисел четна, т.к. среди них четное число нечетных – единиц, поэтому и в конце будет четна. А это значит, что последнее число, оставшееся в конце игры, будет четным, т.е. оно будет нулем - и выигрывает второй.
Задача 4: Числа от 1 до 20 выписаны в строчку. Игроки по очереди расставляют между ними плюсы и минусы. После того, как все места заполнены, подсчитывается результат. Если он четен, то выигрывает первый игрок, если нечетен, то второй.
Решение: Четность результата не зависит от расстановки плюсов и минусов, а зависит только от количества нечетных числе в первоначальном наборе. Так в данном случае их 10 (т.е. четное число), то выигрывает всегда первый игрок.
Симметрия
Пример: Двое по очереди кладут пятаки на круглый стол так, чтобы они не накладывались друг на друга. (Проигрывает, как обычно, тот, кто не может сделать ход.)
Решение: В этой игре первый игрок может выиграть, положив свою монету в центр стола, а затем повторяя ходы второго симметрично относительно центра.
(Симметрия относительно точки - поворот вокруг неё на 1800.) Если второму игроку удалось положить монету на пустое место так, что она не упала, то есть и пустое симметричное место, куда тоже можно положить монету (и она тоже не упадёт). И так далее.
Задача 1. Двое по очереди ставят слонов в клетки шахматной доски так, чтобы они не били друг друга (цвет слонов значения не имеет). Проигрывает тот, кто не может сделать ход.
Решение: 1) Поскольку шахматная доска симметрична относительно своего центра, то естественно попробовать симметричную стратегию. Но на этот раз (первым ходом нельзя поставить слона в центр доски) симметрию может поддерживать второй игрок.
Казалось бы, по аналогии с предыдущей задачей, это и есть выигрышная стратегия. Однако, следуя ей, второму игроку не удастся сделать даже свой первый ход! Слон, только что поставленный первым игроком, может бить центрально-симметричное поле.
2) Решение поставленной задачи легко осуществить, применяя не центральную, а осевую симметрию шахматной доски. За ось симметрии можно взять прямую, разделяющую, например, четвертую и пятую горизонтали. Симметричные относительно нее поля имеют разный цвет, и, тем самым, слон, поставленный на одно из них, не препятствует ходу на другое.
Итак, в этой игре выигрывает все-таки второй игрок.
Задача 2. В строчку написано несколько минусов. Два игрока по очереди переправляют один или два соседних минуса на плюс; выигрывает переправивший последний минус. Кто выигрывает при правильной игре: начинающий или его партнёр?
Решение. В этой игре выигрывает первый игрок, независимо от числа минусов в строке.
Для этого он должен переправить на плюс средний минус (если минусов нечётное число и средний есть) или два средних минуса (если минусов чётное число). После этого игра разбивается на две независимые части, и остаётся лишь повторять ходы противника в другой части, поддерживая симметрию.
Задача 3. Есть две кучки камней, по 17 в каждой. За ход можно взять несколько камней, из одной кучки.
Решение. В этой игре при помощи симметричной стратегии побеждает второй игрок: каждым своим ходом он должен брать столько же камней, сколько предыдущим ходом взял первый игрок, но из другой кучки. Таким образом, у второго игрока всегда есть ход.
Симметрия в этой задаче состоит в равенстве числа камней в кучках.
А если бы кучки были неравны, то выиграл бы первый. Первым ходом он взял бы из большей кучки столько камней, чтобы уравнять ее с меньшей, а далее пользовался бы изложенной выше стратегией.
Задача 4. На столе лежат две кучки спичек: в одной 10, в другой – 7. Игроки ходят по очереди. За один ход можно взять любое число спичек (1, 2, 3 …) из одной из кучек ( по выбору игрока). Кто не может сделать ход (спичек не осталось) проигрывает.
Решение. Первый игрок может гарантировать выигрыш, если сначала уровняет кучки, взяв три спички из большей. После этого он должен повторять ходы второго, но брать из другой кучки, восстанавливая нарушенное равновесие.
Задача 5. На столе лежит 25 спичек. Играющие по очереди могут взять от 1 до 4 спичек. Кто не может сделать ход проигрывает.
Решение. В этой игре второй игрок может гарантировать себе выигрыш. Для этого он должен дополнять ход первого до 5 спичек (если первый взял 1, второй берет 4 и т.д.). Тогда после хода второго останется 20 спичек, затем 15, затем 10, 5 и, наконец 0 – первый проиграл.
Примечание:
В случае, когда симметричность многовариантна, для решения задачи нужно правильно выбрать центр или ось симметрии.
При доказательстве правильности симметричной стратегии нельзя забывать о том, что очередному симметричному ходу может помешать ход, только что сделанный противником.
Чтобы решить игру-задачу при помощи симметричной стратегии необходимо найти симметрию, при которой только что сделанный противником ход не препятствует осуществлению избранного плана.
Выигрышные позиции
Пример 1. Имеются две кучки конфет: в одной - 20, в другой - 21. За ход нужно съесть одну из кучек, а вторую разделить на две не обязательно равные кучки. Проигрывает тот, кто не может сделать ход.
Решение: Выигрывает первый игрок. Выигрышными являются позиции с двумя нечетными кучками. Первый ход — съесть кучку из 21 конфеты и разделить кучку из 20 конфет на любые две нечетные кучки.
Пример 2. В коробке лежат 300 спичек. За ход разрешается взять из коробки не более половины имеющихся в нем спичек. Проигрывает тот, кто не может сделать ход.
Решение: Выигрышными являются позиции, при которых в коробке остается 2n — 1 спичка. Первым ходом начинающий игру оставляет 255, т. е. (28 - 1) спичек, далее, следуя выигрышным позициям, побеждает.
Пример 3. Ладья стоит на поле a1. За ход разрешается сдвинуть ее на любое число клеток вправо или на любое число клеток вверх. Выигрывает тот, кто поставит ладью на поле h8.
Решение: В этой игре побеждает второй игрок. Его стратегия очень проста: каждым своим ходом он возвращает ладью на большую диагональ a1-h8.
Объясним, почему, играя так, второй игрок выигрывает. Дело в том, что первый игрок любым своим ходом вынужден будет уводить ладью с этой диагонали, а второй игрок после этого будет иметь возможность вернуть ладью на линию a1-h8. Так как поле h8 принадлежит диагонали, то на него сумеет встать именно второй игрок.
Задача 1. Король стоит на поле a1. За один ход его можно передвинуть на одно поле вправо, или на одно поле вверх, или на одно поле по диагонали «вправо — вверх». Выигрывает тот, кто поставит короля на поле h8.
Решение: Занумеруем горизонтали и вертикали шахматной доски в естественном порядке. Координаты поля a1 - (1; 1), поля h8 - (8; 8). Выигрышными являются позиции, в которых король стоит на поле с четными координатами. Первый ход - на поле Ь2.
Выигрывает первый игрок.
Анализ с конца - поиск выигрышных позиций
При решении задач на класс выигрышных позиций могло появиться ощущение, что поиск выигрышных позиций основан лишь на интуиции, а поэтому, как правило, непрост.
Сейчас мы разберем общий метод, позволяющий найти выигрышные позиции во многих играх.
Вернемся к задаче 1 про короля.
(Король стоит на поле a1. За один ход его можно передвинуть на одно поле вправо, или на одно поле вверх, или на одно поле по диагонали «вправо — вверх». Выигрывает тот, кто поставит короля на поле h8.)
Попробуем найти выигрышные позиции исходя из их свойств:
завершающая позиция игры — выигрышная;
за ход нельзя из одной выигрышной позиции попасть в другую;
из любой невыигрышной позиции за один ход можно попасть в какую-либо выигрышную.
Как всегда, завершающая позиция игры (король стоит на h8) — выигрышная. Поэтому в клетку h8 поставим «+». Так же мы будем отмечать все найденные выигрышные позиции.
8 +
7 6 5 4 3 2 1 a b c d e f g h
В клетках, соответствующих проигрышным позициям, будем ставить «—».
Так как позиции, из которых король может за один ход попасть на выигрышное поле h8, — проигрышные, то возникает расстановка, изображенная на следующем рисунке.
8 - +
7 - -
6 5 4 3 2 1 a b c d e f g h
С полей h6 и f8 за один ход можно попасть только на проигрышные поля. В этих клетках нужно поставить «+» - они выигрышные.
8 + - +
7 - -
6 +
5 4 3 2 1 a b c d e f g h
Только что полученные выигрышные позиции порождают набор новых проигрышных позиций - h5, g5, g6, f7, e7, e8.
8 - + - +
7 - - - -
6 - +
5 - -
4 3 2 1 a b c d e f g h
Продолжим анализ далее. После получения очередного набора минусов отмечаем плюсом те поля, из которых каждый ход ведет в проигрышную позицию. После этого отмечаем минусом те поля, из которых существует хотя бы один ход в выигрышную ситуацию.
8 + - + - +
7 - - - -
6 + - +
5 - -
4 +
3 2 1 a b c d e f g h
В итоге плюсы и минусы будут расставлены так, как на последнем рисунке.
8 - + - + - + - +
7 - - - - - - - -
6 - + - + - + - +
5 - - - - - - - -
4 - + - + - + - +
3 - - - - - - - -
2 - + - + - + - +
1 - - - - - - - -
a b c d e f g h
Примечание. Только что описанный метод нахождения выигрышных позиций называется «анализом с конца».
Применяя его к задаче с ладьей из примера 3, легко получаем набор выигрышных позиций.
8 - - - - - - - +
7 - - - - - - + -
6 - - - - - + - -
5 - - - - + - - -
4 - - - + - - - -
3 - - + - - - - -
2 - + - - - - - -
1 + - - - - - - -
a b c d e f g h
Задача 3. Есть две кучки камней: в одной m, в другой n. За ход можно взять несколько камней из одной кучки.
Решение: Наверно, вы уже заметили, что эта игра по существу совпадает с одной
из уже рассмотренных - а именно, игрой с двумя кучками спичек. Позиция (m; n) (в одной кучке m спичек, а в другой n) соответствует клетке в m-ой вертикали и n-ой горизонтали (если начинать счёт с нуля), см. рис.
4 (0,4) (1,4) (2,4) (3,4) (4,4)
3 (0,3) (1,3) (2,3) (3,3) (4,3)
2 (0,2) (1,2) (2,2) (3,2) (4,2)
1 (0,1) (1,1) (2,1) (3,1) (4,1)
0 (0,0) (1,0) (2,0) (3,0) (4,0)
0 1 2 3 4
Математики сказали бы, что эти две игры изоморфны.
Взятие спичек из одной кучи уменьшает первую координату и сдвигает ладью влево; взятие спичек из другой кучи сдвигает ладью вниз. В угловой клетке (0; 0) ладья не может сделать хода (спичек не осталось ни в одной из кучек).
Чтобы выиграть, надо возвращать ладью на диагональ; на языке спичек - уравнивать число спичек в обеих кучках (как мы и говорили).
В этом случае выигрышная стратегия нам по существу уже была известна.
Рассмотрим чуть более сложный пример, изменив немного правила игры.
Задача 4. Есть две кучки камней: в одной 6, в другой 5. За ход можно взять несколько камней из одной кучки или поровну камней из обеих кучек.
Решение:
Занесем позиции в таблицу, где по двум осям будем отмечать количество камней в двух кучках.
5 (0,5) (1,5) (2,5) (3,5) (4,5) (5,5) (6,5)
4 (0,4) (1,4) (2,4) (3,4) (4,4) (5,4) (6,4)
3 (0,3) (1,3) (2,3) (3,3) (4,3) (5,3) (6,3)
2 (0,2) (1,2) (2,2) (3,2) (4,2) (5,2) (6,2)
1 (0,1) (1,1) (2,1) (3,1) (4,1) (5,1) (6,1)
0 (0,0) (1,0) (2,0) (3,0) (4,0) (5,0) (6,0)
0 1 2 3 4 5 6
Финальная позиция (0,0) - нижний левый угол, начальная - верхний правый.
Возможные переходы: влево по горизонтали, вниз по вертикали или влево-вниз по диагонали на любое количество клеток.
Если мы отметим финальную выигрышную позицию и все, откуда на нее можно пойти, то получим картину, как на табл. сверху.
Результат окончательного нахождения позиций можно видеть на табл. снизу.
Опять начальная позиция проигрышная и выигрывает первый.
5 - - - + - - -
4 - - - - - - -
3 - - - - - + -
2 - + - - - - -
1 - - + - - - -
0 + - - - - - -
0 1 2 3 4 5 6

Приложенные файлы


Добавить комментарий