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

Вид материала

Задача

Содержание Симметричные стратегии

Подобный материал:

• А. С. Пушкина «Капитанская дочка» Первое условие успешности любого высказывания, устного, 50.05kb.
• I. Цели и задачи, 209.8kb.
• Аннотация примерной программы дисциплины «Математический анализ» Рекомендуется для, 311.3kb.
• Рабочая учебная программа дисциплины (модуля) Математический анализ, 233.89kb.
• Положени е о Всероссийских соревнованиях по пулевой стрельбе на 2008 год, 2314.46kb.
• Положение о городской научно технической олимпиаде по триз общие положения, 26.51kb.
• Положение о проведении городских соревнования по баскетболу среди учащейся молодежи,, 23.37kb.
• Московская городская олимпиада по информатике, 453.6kb.
• Рабочая программа учебной дисциплины «Математический анализ» Направление подготовки, 275.11kb.
• Программа курса «Основы математического моделирования» Осень 2007, 25.35kb.

Игры и стратегии

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

Прежде чем приступить к рассмотрению задач, нам потребуется осознать, что соображения типа «если он ходит так, то я хожу так» не являются, как правило, решением игры. На самом деле, для решения игровой задачи необходимо, во-первых, грамотно и четко сформулировать стратегию, во-вторых, доказать, что она действительно ведет к выигрышу, и, в-третьих, показать, что описанная стратегия реализуема. Особое внимание следует обратить именно на третий пункт: именно про него чаще всего забывают и именно из-за него, казалось бы, совершенно правильная стратегия оказывается не более чем бессмысленным набором действий, который далеко не всегда сможет обеспечить выигрыш в игре.

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


Игры-шутки

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

Задача 1. Числа от 1 до 20 выписаны в строчку. Игроки по очереди расставляют между ними плюсы и минусы. После того, как все места заполнены, подсчитывается результат. Если он четен, то выигрывает первый игрок, если нечетен, то второй.

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

Задача 2. Дана клетчатая доска размерами

а) 9 × 10; б) 10 × 12; в) 9 × 11.

За ход разрешается вычеркнуть любую горизонталь или любую вертикаль, если в ней к моменту хода есть хотя бы одна невычеркнутая клетка. Проигрывает тот, кто не может сделать ход.

Решение. Эта игра – не совсем шутка. В ней выигрывающий, допустив ошибку, может проиграть. Эта ошибка состоит в том, что он после своего хода оставляет невычеркнутые клетки только в одном столбце или только в одной строке, предоставляя противнику возможность выиграть в один ход. Проигравшим в этой игре является, тем самым, тот, кто сделает этот роковой ход. Заметим, что оставшуюся после вычеркивания горизонтали часть клетчатой доски m×n можно представить себе как доску (m – 1)×n. Аналогично, после вычеркивания вертикали остается доска m×(n – 1). Ситуация, в которой каждый ход является «роковым», только одна – это доска 2×2. Таким образом, выигрывает игрок, после хода которого она возникла. Однако, как мы видели, при каждом ходе суммарное количество горизонталей и вертикалей на доске уменьшается на 1. Поэтому четность этой суммы в начале игры определяет победителя. В пункте а) выигрывает первый игрок, а в пунктах б) и в) – второй. Заметим, что в пункте б) решающим соображением может быть и симметричная стратегия второго игрока, с принципами которой мы ознакомимся чуть позже.

Задача 3. Двое по очереди ломают шоколадку 6×8. За ход разрешается сделать прямолинейный разлом любого из кусков вдоль углубления. Проигрывает тот, кто не сможет сделать ход. Кто выиграет в этой игре?

Решение. Основное соображение: после каждого хода количество кусков увеличивается ровно на 1. Сначала был один кусок. В конце игры, когда нельзя сделать ни одного хода, шоколадка разломана на маленькие дольки 1×1. А их 48! Таким образом, игра будет продолжаться ровно 47 ходов. Последний, 47-й ход (так же, как и все другие ходы с нечетными номерами) сделает первый игрок. Поэтому он в этой игре побеждает, причем независимо от того, как будет играть.


Симметричные стратегии

Рассмотрим следующую игру.

Задача 4. Двое по очереди кладут пятаки на круглый стол, причем так, чтобы они не накладывались друг на друга. Проигрывает тот, кто не может сделать ход.

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

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

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

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

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

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

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

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

Решение задачи 5. Оказывается, решение этой задачи легко провести, применяя не центральную, а осевую симметрию шахматной доски. За ось симметрии можно взять прямую, разделяющую четвертую и пятую горизонтали. Симметричные относительно нее поля имеют разный цвет, и, тем самым, слон, поставленный на одно из них, не препятствует ходу на другое. Итак, в этой игре выигрывает все-таки второй игрок.