Семинар ДООМ Кружок 5-8, Игры (задачи на стратегию)

Руководитель команд ДООМ 2008 МОЗГИ ID 215 и Великие математики ID_214

Предлагаю ряд статей, обьединенных в цикл "олимпиадные задачи. Кружок 5-8." Все они вошли в состав сборников, один из которых вышел издательстве Легион (Е.Г. Коннова. Математика. Серия «Готовимся к олимпиаде». Ростов н/Д: Легион, 2008.), а второй готовится к печати.

Занятие 5. Игры-шутки

Игры-шутки – это игры, в которых исход не зависит от того, как делают ходы игроки. В таких задачах не нужно описывать стратегию, нужно лишь доказать, что выиграет тот или другой игрок.

Задача 1.

В таблице 6х9 двое по очереди зачеркивают по две клетки. Проигрывает тот, кто не может сделать хода. Кто выигрывает при правильной игре?

Решение.

В этой игре выигрывает начинающий. Всего возможно 27 ходов, ведь в таблице 54 клетки. Последний ход нечетный, значит, его сделает первый игрок.

Задача 2.

На столе 4 кучки с орехами, в двух по 20 орехов, в двух других по 15. За ход разрешено любую кучку разделить на две меньшие. Проигрывает тот, кто делает последний ход. Кто выигрывает при правильной игре?

Решение.

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

Задача 3.

На доске написаны 20 единиц и 10 двоек. За ход разрешается стереть две любые цифры и, если они были одинаковые, написать двойку, а если разные – единицу. Если последняя оставшаяся на доске цифра – единица, то выиграл первый игрок, если двойка – то второй. Кто выигрывает при правильной игре?

Решение.

Заметим, что четность числа единиц на доске после каждого хода не изменяется. Действительно, если стерли разные цифры и вместо них написали 1, то число единиц не изменилось. Если стерли две одинаковые цифры и написали двойку, то число единиц либо не изменилось, либо уменьшилось на две. То есть независимо от того, как будут ходить игроки, число единиц не будет увеличиваться и будет четно, значит, когда останется одна цифра, то это будет двойка. Поэтому выиграет второй игрок. Игра конечна, потому что число цифр при каждом ходе уменьшается.

Задача 4. 

Примерный ученик Саша купил тетрадь из 96 листов и пронумеровал страницы от 1 до 192. Хулиган Вася вырвал из тетради какие-то 25 листов. Саша предложил ему поиграть в такую игру: Вася вырывает еще один любой лист из тетради, они складывают номера страниц на этих листах, и если получится четный результат, то Вася покупает ему новую тетрадь, а если нечетный, на Саша решает за него контрольную по математике. Придется ли Васе покупать Саше тетрадь?

Решение.

Придется. Сумма цифр на одном листе всегда нечетна, вырванных листов четное число, значит сумма будет четна.

Задача 5.

Числа от 1 до 25 выписаны в ряд. Двое по очереди ставят между ними плюсы и минусы. Когда поставлены все знаки вычисляют значение выражения. Если ответ четный, побеждает первый игрок, если нечетный, второй. Кто выигрывает при правильной игре?

Решение.

Среди этих чисел 13 нечетных, а алгебраическая сумма нечетного числа нечетных чисел нечетна. Общий результат будет всегда нечетным, какие бы знаки не расставили. Значит, всегда будет выигрывать второй игрок.

Задача 6. (XXXI Всероссийская математическая олимпиада)

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

Решение.

Выигрывает второй игрок.

Рассмотрим момент, когда любой ход ведет к проигрышу, то есть закрашивание любой незакрашенной клетки ведет к тому, что на любом луче с началом в центральной клетке окажется закрашенная точка (помимо начала луча).В этот момент на каком-то луче I с началом в центральной клетке еще нет закрашенных точек. Луч I пересекает границу квадрата 3х3 в некоторой точке (назовем ее X). Тогда найдутся соседние по стороне клетки А и В (где В примыкает стороной к границе квадрата 5х5, а А — не примыкает), на границе которых находится X.(Другими словами, точку Х, лежащую на границе, включают хотя бы две клетки, одна из которых касается границы квадрата 5х5(В) а другая не касается(А) Луч I пересекает клетки А и В, поэтому они не закрашены. Для расположения пары клеток A, В существует два варианта (с точностью до поворотов и симметрии), и для каждого из этих вариантов есть луч с началом в центральной клетке, пересекающий только клетки А и В . Поэтому, если кроме этих клеток есть еще хотя бы одна незакрашенная, то ее можно закрасить, не проигрывая. Таким образом, в рассматриваемый нами момент незакрашенной остается только пара клеток А и В. Это означает, что к этому моменту времени было сделано 24 — 2 == 22 хода, то есть последний ход сделал второй игрок, а значит, первый игрок проиграет.

Задача 7.

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

Решение.

Заметим, что в этой игре любая позиция, которая может быть достигнута вообще, будет достигнута при игре вне зависимости от ходов игроков. Покажем, что могут быть достигнуты все числа от 1 до 36. 1-й ход: 36-25=11, на доске 25, 36, 11.

2-й ход: 25-11=14 (36-11=25, 36-25=11, эти числа уже были, поэтому такие ходы делать нельзя), на доске 25, 36, 11, 14.

Рано или поздно игроки получат число 3 (14-11=3, или другим способом), потому что они могут продолжать игру, пока не получат все возможные числа. Но тогда они получат и 1, так как 11-3-3-3=2, 3-2=1. Получив 1, они могут получить все числа от 1 до 36, которых еще не было. Так как повторяться им нельзя и два числа было изначально, то у них будет ровно 34 хода, т. е. игру закончит второй и выиграет.

Занятие 7. Игры. Симметрия

Во многих задачах применяется одна из основных идей нахождения выигрышных стратегий - идея осевой или центральной симметрии.

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

Задача 8. 

На столе лежат в один ряд а) 37 пирожных; б) 34 пирожных. Оля и Петя играют в игру: за один ход разрешается съесть одно пирожное или два, лежащих рядом. Выиграет тот, кто съест последнее пирожное. Кто выиграет при правильной игре в каждом из пунктов, если первой ходит Оля?

Решение.

а) Выигрывает Оля. Первым ходом она должна съесть центральное (19-е) пирожное, а после этого «ходить» - брать пирожные - центрально симметрично;

б) Выигрывает Оля. Первым ходом она должен взять два центральных пирожных (17-е и 18-е, если считать слева (или справа)), а затем ходить центрально-симметрично. Во всех случаях, согласно такой стратегии, после каждого хода Оли пирожные будут расположены симметрично, но в любой симметричной паре они не будут лежать рядом и их нельзя будет взять одним ходом. Значит, последнее пирожное достанется Оле.

Другие работы:

Семинар ДООМ 2008 "Формула текста"

Семинар ДООМ Кружок 5-8, Четность

Семинар ДООМ Кружок 5-8, Задачи на проценты

Семинар ДООМ Кружок 5-8, Игры (задачи на стратегию)

Семинар ДООМ Кружок 5-8, Принцип Дирихле

Семинар ДООМ Кружок 5-8, Текстовые задачи, решаемые с помощью теории графов

Семинар ДООМ 2007 "Графы"

Семинар ДООМ Задачи, решаемые с помощью деревьев

Элективный курс Графы 6-8 класс Программа курса 18 часов

Материалы для курса Графы - Материалы для оценивания усвоения содержания Элективного курса