Math    schooL

 

 

Игры, преследования, стратегии и алгоритмы

 

Игры, преследования, стратегии и алгоритмы

 

Немного теории

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

Такие задачи условно можно разделить на три группы:

1) задачи в которых выигрышная стратегия базируется на идее симметрии;

2) задачи, в которых рассуждения ведутся с конца, для отыскания начальных выигрышных позиций;

3) задачи, в которых результат игры не зависит от обоих игроков.

Следует отметить: в задачах с участием игроков, игроки ходят поочерёдно, пропускать ход запрещено.

 

Задачи с решениями

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

Шахматная доска симметрично относительно своего центра, поэтому, на первый взгляд, второй игрок на каждый ход первого имеет симметричный ход. Но это не так, потому что, если первый игрок поставит слона на клетку главной диагонали, то второй игрок симметричного хода не имеет.

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

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

 

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

Разобьём все квадраты на 32 пары так, чтобы квадраты в одной паре были соединены ходом коня, например так, как показано на рисунке.

Куда бы первый игрок не поставил коня своим ходом, второй игрок переставляет его на парную клетку. Поэтому у второго всегда будет ход, и он проиграть не может.

 

3. Двое школьников поочередно пишут цифры 2k-значного числа, используя только цифры 1, 2, 3, 4, 5. Первую цифру пишет первый школьник, вторую – второй школьник, третью – первый и так далее. Может ли второй школьник добиться того, чтобы полученное число делилось на 9, если первый школьник стремится ему помешать? Рассмотрите случаи k = 10 и k = 15.

Пусть a1, a2, … , ak – цифры, которые последовательно пишет первый, а b1, b2, … , bk – цифры, которые последовательно пишет второй. Для того чтобы число делилось на 9, необходимо и достаточно, чтобы сумма S цифр этого числа делилась на 9. Поэтому далее будем следить только за величиной

S = a1 + b1 + a2 + b2 + . . . + ak + bk.

Если k делится на 3 (k = 3m), то второй применив правило

bi = 6 – ai, где i = 1, 2, … , k,

добьется того, что число

S = (a1 + b1) + (a2 + b2) + . . . + (ak + bk) = 6k = 18m,

будет делиться на 9, какие бы цифры из числа разрешённых не писал первый.

Если же k не делится на 3 (k = 3m + 1 или k = 3m + 2), то первый, действуя по правилу

a1 = 6, аi = 6 – bi–1, где i = 2, … , k,

добьётся того, что сумма цифр написанного числа

S = a1 + (b1 + a2) + (b2 + a3) + . . . + (bk–1 + ak) + bk,

не будет делиться на 9. Действительно, если k = 3m + 1, то S = 18m + (3 + bk) не делится на 9, так как не делится на 9 число 3 + bk, заключённое между 4 и 8. Если k = 3m + 2, то S = 18m + 9 + bk не делится на 9, поскольку bk не делится на 9.

Итак, при k = 15 второй школьник всегда может добиться того, чтобы написанное число делилось на 9. При k = 10 первый школьник всегда может помешать этому.

 

4. В центре поля, имеющего форму квадрата, находится волк, а в вершинах квадрата – четыре собаки. Волк может бегать по всему полю, а собаки – только по сторонам квадрата. Известно, что волк задирает собаку, а две собаки задирают волка. Максимальная скорость каждой собаки в 1,5 раза больше максимальной скорости волка. Докажите, что собаки имеют возможность не выпустить волка из квадрата.

Пусть v – максимальная скорость волка. Проведем через точку B, в которой находится волк, две прямые, параллельные диагоналям квадрата. Эти прямые в точках С1, С2, С3, С4, пересекают контур квадрата. В ответ на перемещения точки В в пределах квадрата, точки С1, С2, С3, С4 так же будут некоторым образом менять своё положение или оставаться на месте (при движении точки В параллельно диагонали).

Время движения точек В и Сk одинаково, поэтому судить о скоростях этих точек можно по проходимым ими расстояниям. Рассмотрим следующую ситуацию. Пусть точка В проходит расстояние от центра квадрата к его вершине, то есть половину диагонали. За это время некоторые две точки Сi и Сj преодолеют расстояние, равное стороне квадрата. Так как сторона квадрата в корень из 2 раз больше половины его диагонали, то точки Сi и Сj двигались во столько же раз быстрее чем точка В. Большего превосходства в скорости точек С1, С2, С3, С4 над скоростью точки В быть не может.

Так как скорость перемещения каждой из точек С1, С2, С3, С4 не больше

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

 

5. На шахматной доске 8 на 8 двое играют в игру «кошки-мышки». У первого одна фишка – мышка, у второго несколько фишек–кошек. Все фишки ходят одинаково: вправо, влево, вверх или вниз на одну клетку. Если мышка оказалась на краю доски, то очередным ходом она спрыгивает с доски. Если кошка и мышка попадают на одну и ту же клетку, то кошка съедает мышку. Играющие ходят по очереди, причем второй передвигает своим ходом всех своих кошек сразу (разных кошек можно при этом сдвигать в разных направлениях). Начинает мышка. Она старается спрыгнуть с доски, а кошки стараются до этого ее съесть.

 а) Пусть кошек всего две. Мышка уже поставлена на какую-то клетку не на краю. Можно ли так поставить кошек на краю доски, чтобы они сумели съесть мышку?

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

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

Ответ: можно.

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

 

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

Среди восьми чисел найдутся три, не превосходящие 1/6. Действительно, если таких чисел не больше двух, то чисел превосходящих 1/6, как минимум шесть. Но тогда сумма этих шести чисел больше 1, чего быть не должно. Как бы три числа, не превосходящие 1/6, не располагались в вершинах куба, два из них обязательно будут стоять на концах диагонали одной из граней. Эту грань и следует выбрать с самого начала первому игроку. Дальнейшие действия игроков не способны помешать достижению цели первого игрока.

 

7. Тридцать клеток расположены в ряд и занумерованы слева направо в порядке возрастания номеров. На самой левой клетке (с номером 1) стоит белая фишка, на самой правой клетке (с номером 30) – черная. Каждый из двух участников играет фишкой определенного цвета, по очереди передвигая свою фишку на одно или на два поля вперед или назад. Запрещается пропускать ход и перепрыгивать через фишку соперника. Проигравшим считается тот, у кого нет возможности сделать очередной ход. Кто выигрывает при правильной игре: начинающий игру или его партнер?

Покажем, что при правильной игре выигрывает начинающий. Пусть для определенности у него белая фишка. Его выигрыш означает, что у его партнера нет возможности сделать очередной ход, то есть черная фишка стоит в клетке с номером 30, а белая – с номером 29, причем ходить должна черная. Таким образом, задача начинающего – оттеснить черную фишку в клетку с номером 30.

Сначала покажем, что если после очередного хода начинающего его фишка отстоит от фишки партнера на три клетки (рисунок 1), то начинающий при правильной игре обязательно выиграет партию. Если в этой позиции черная фишка сдвинется влево на одну или две клетки, то белая фишка, сдвинувшись вправо соответственно на две или одну клетку, лишит черную фишку возможности двигаться влево при следующем ходе (рисунки 2 и 3). Значит, при следующем ходе черная фишка должна будет отступить на одну или две клетки вправо (пропускать ход и перепрыгивать через фишку соперника нельзя), а так как белая фишка за один ход может сдвинуться вправо на столько же клеток, на сколько при предыдущем ходе вправо сдвинулась черная фишка, то ясно, что белая фишка оттеснит черную фишку на клетку с номером 30, если будет повторять ходы черной фишки.

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

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

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

В начальный момент белую и черную фишки разделяют 28 клеток. Если, следовательно, на первом ходу белая фишка передвинется вправо на одну клетку, то ее будет отделять от черной фишки расстояние в 27 клеток. Как бы теперь ни переместилась черная фишка, белая всегда может переместиться так, что расстояние между ними станет равно 24 клеткам. Если черная фишка сдвинется влево на одну или две клетки, то белая сдвинется вправо соответственно на две или одну клетку. Если и далее черная фишка будет продолжать двигаться влево, то белая будет двигаться вправо так, чтобы расстояние, разделяющее их после очередного хода белой фишки, делилось бы на 3. При этом всякий раз после того, как черная и белая фишки сделают по одному ходу, расстояние между ними уменьшится на 3. Следовательно, если черная фишка будет двигаться только влево, то через несколько ходов ее будут отделять от белой 3 клетки, то есть, после некоторого хода белой фишки возникнет ситуация, изображенная на рисунке 1.

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

 

8. На прямой находятся паук и муха. Максимальная скорость паука вдвое больше максимальной скорости мухи, но он ничего не знает о месторасположении мухи до тех пор пока они не окажутся в одной точке. Сможет ли паук догнать муху?

Предположим, что в начальный момент времени паук находится в положении 0. Паук движется по маршруту

0,  40,  –41,  42,  –43,  44, . . .

Пусть скорость паука 2, а скорость мухи 1. Пусть начальное положение мухи х (х > 0).

Чтобы оказаться в точке 42n пауку следует преодолеть расстояние равное

2 · (40 + 41 + 42 + . . . + 42n–1) + 42n = (2/3) · (42n – 1) + 42n = (5/3) · 42n – 2/3.

При скорости 2 для преодоления этого расстояния пауку потребуется

(5/6) · 42n – 1/3

единиц времени. Муха за это время будет не далее чем в положении

1 · ((5/6) · 42n – 1/3) + х = (5/6) · 42n – 1/3 + х

При n > (1/2) · log4(6x) верно неравенство

42n > (5/6) · 42n – 1/3 + х.

Следовательно, паук догонит муху.

 

9. На доске написано уравнение

x3 + . . . + x2 + . . . + х + . . . = 0.

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

Если первый игрок поставит –1 перед x в первой степени, а при втором своем ходе он поставит на последнее оставшееся место число, противоположное тому, которое поставил второй, то получится многочлен вида

x3 – a·x2 – х + a = (x2 – 1)·(х – а).

Корни этого многочлена –1, 1, а – целые числа.

 

10. Двое играющих по очереди пишут – каждый на своей половине доски – по одному натуральному числу (повторения разрешаются) так, чтобы сумма всех чисел на доске не превосходила 10000. После того, как сумма всех чисел на доске становится равной 10000, игра заканчивается подсчетом суммы всех цифр на каждой половине. Выигрывает тот, на чьей половине сумма цифр меньше (при равных суммах – ничья). Может ли кто-нибудь из игроков выиграть, как бы ни играл противник?

Ясно, во-первых, что второй может гарантировать себе ничью: ему достаточно всё время писать числа с суммой цифр 1 (например, просто число 1 ) – действительно, он делает не больше ходов, чем первый, и на каждом ходе пишет число с не большей суммой цифр. Более того, по той же причине первый игрок проиграет, если хотя бы один раз напишет число с суммой цифр больше 1.

Пусть теперь оба игрока пишут только числа с суммой цифр 1 – 1, 10, 100, 1000 или 10000. Тогда проиграть второй не может, а чтобы выиграть, ему нужно вынудить противника сделать больше ходов, или, что то же самое, сделать последний ход.

Докажем, что отвечая на числа 10 и 1000 числом 1, а на числа 100 и 1 числом 10, второй игрок добьётся успеха. Действительно, после каждого его хода сумма чисел на доске делится на 11, а 10000 на 11 не делится. Поэтому остаётся лишь проверить, что такой ход всегда легален – то есть что после него сумма не станет больше 10000. Для этого заметим, что первое большее 10000 число, делящееся на 11, – это 10010, а его нельзя получить, прибавляя 1 или 10 к числу, меньшему 10000 .

Можно показать, что если заменить 10000 в условии на произвольное число N, то второй игрок может выиграть тогда и только тогда, когда N даёт нечётный остаток при делении на 11 .

Ответ: второй игрок может выиграть.

 

Задачи без решений

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

 

2. Границей леса является прямая k. На перпендикуляре АС к прямой k в точках А и В (АВ = ВС) находятся заяц и волк соответственно.

Оба они бегут с постоянными скоростями, причём скорость зайца вдвое больше скорости волка. Заяц будет схвачен волком в некоторой точке, если в эту точку волк сможет прибежать или раньше зайца, или одновременно с ним. Заяц выбирает на k точку D и бежит в лес по отрезку AD. Как выбрать точку D, чтобы заяц не мог быть схвачен волком на отрезке AD?

 

3. В ряд записаны 12 звёздочек. Двое игроков по очереди записывают вместо звёздочек цифры. Если полученное 12-значное число делится на 77, то выигрывает второй игрок, иначе первый. Кто выиграет при правильной игре: начинающий или его соперник?

 

4. Написано 20 чисел: 1, 2, ... , 20. Двое играющих по очереди ставят перед этими числами знаки «+» или «–» (знак можно ставить перед любым свободным числом). Первый стремится к тому, чтобы полученная после расстановки всех 20 знаков сумма была как можно меньше по модулю. Какую наибольшую по модулю сумму может обеспечить себе второй?

 

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

 

Нам 4 года!

14 марта 2016 года сайту Математика для школы|math4school.ru исполнилось 4 года. Поскольку число 4 для нашего сайта не чужое, мы решили подвести некоторые итоги.

Новый формат главного меню

Расширены функциональные возможности главного меню.

Галерея на сайте math4school.ru
Приглашаю посетить Галерею, – новый раздел на сайте.

444 года со дня рождения Иоганна Кеплера

27 декабря 2015 года исполнилось 444 года со дня рождения Иоганна Кеплера.

Новый раздел на сайте math4school.ru

Закончена работа над новым разделом сайта Работа над ошибками.

Союз образовательных сайтов