Отправляет email-рассылки с помощью сервиса Sendsay

Математический кружок

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Работа и обучение за рубежом для студентов и не только!" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Ноябрь 2001   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Автор
Роман Александрович Семизаров

Статистика

2.740 подписчиков
0 за неделю
←   Все выпуски   →

Математический кружок Занятие 16. Анализ с конца в играх


Служба Рассылок Subscribe.Ru

Здравствуйте, друзья.

Прошу прощения за большую задержку выпуска.

Решение задачи 141. (Король-турист)

Двое играют в следующую игру: первый выбирает любое поле на доске 8 x 8, ставит туда короля и делает ход (король может ходить в соседние и соседние по диагонали клетки). После этого ходит второй игрок, затем первый и так далее. Запрещается ходить на клетку, на которой король уже был. Проигрывает тот, кто не может сделать ход.
Разобьём клетки на 32 пары так, чтобы клетки в каждой паре были соседними. Первым ходом первый игрок ставит фишку на любую клетку, и ходит на вторую клетку той же пары. Затем он ходит в клетку парную к той, на которую походил второй.

Решение задачи 146. (Игра Баше -- 1, 3 или 4)

Имеется полоска клетчатой бумаги длиной а) 10; б) 15 клеток. В крайней правой ее клетке стоит шашка. Двое играющих по очереди передвигают ее влево на одну, три, или четыре клетки. Проигрывает тот, кому некуда ходить.
Будем искать клетки, на которые выгодно ходить, то есть те, любой ход из которых ведёт к проигрышу (если бы игра начиналась с такой позиции, то выигрывал бы второй). Такие клетки будем называть "выигрышными" и помечать плюсами. Остальные позиции (то есть те, ход на которые ведёт к проигрышу) будем называть "проигрышными". Искать будем уже знакомым нам методом "анализа с конца".

Самая правая клетка (клетка 1), конечно выигрышная. Значит те клетки, из которых можно в неё пойти (2, 4 и 5) -- проигрышные (ведь если в них походить, то соперник сразу пойдёт на выигрышную позицию 1). 

 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| + | - |   | - | - |   |   |   |   |   |
|_1_|_2_|_3_|_4_|_5_|_6_|_7_|_8_|_9_|10_|
Клетка 3 выигрышная (из неё соперник должен пойти в проигрышную клетку 2). Клетки 6 и 7 поэтому проигрышные (из них соперник сможет походить в выигрышную позицию 3). 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| + | - | + | - | - | - | - |   |   |   |
|_1_|_2_|_3_|_4_|_5_|_6_|_7_|_8_|_9_|10_|
Из позиции 8 можно пойти только в проигрышные позиции 4, 5 и 7, значит сама позиция 8 выигрышная. Позиция 9 проигрышная, так как соперник из неё может пойти в выигрышную позицию 8. И, наконец, позиция 10 выигрышная, так как из неё можно пойти только в проигрышные позиции 6, 7 и 9. Как уже было замечено, это означает, что выигрывает второй игрок. 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| + | - | + | - | - | - | - |   |   |   |
|_1_|_2_|_3_|_4_|_5_|_6_|_7_|_8_|_9_|10_|

Как видно из решения, выигрышные и проигрышные клетки обладают такими свойствами:

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

Этим способом можно проанализировать очень многие игры.

Задача

На шахматной доске на поле f8 стоит хромой ферзь, который может ходить только по горизонтали влево, по вертикали вниз и по диагонали влево-вниз. Проигрывает тот, кто не может сделать хода.
Решение. Будем расставлять плюсы и минусы. На клетку a1 выигрышная. Все остальные клетки на вертикали a, на горизонтали 1 и на диагонали a1-h8 проигрышные, так как с них можно походить на выигрышную клетку a1. Клетки b3 и c2 выигрышные, так как с них можно походить только на проигрышные клетки. 
   _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 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
Мы видим, что первый игрок выигрывает, для этого он может походить на поле e8, на поле d6 или на поле f4.

Задачи

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

Шашка ходит на:

а) 1 или 2 хода влево;

б) 2 или 3 хода влево;

в) 1, 2 или 3 хода влево;

г) 1, 2 или 4 хода влево;

д) На любую степень двойки (то есть на 1, 2, 4 или 8);

е) Не более, чем на половину номера клетки влево. 

 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |
|_1_|_2_|_3_|_4_|_5_|_6_|_7_|_8_|_9_|11_|12_|13_|14_|15_|

Задача 150. В этих заданиях мы будем иметь дело с разновидностями следующей игры. Есть клетчатая доска некоторой формы и размера, на ней стоит шахматная фигура. Игроки ходят фигурой по очереди, проигрывает тот, кто не может сделать хода. Отметьте положения фигуры, при которых выигрывает тот игрок, у которого очередь хода плюсами, а положения, при которых выигрывает тот, кто ходит вторым~-- минусами.

а) Однобокий король, который может ходить только вверх, вправо и вправо-вверх по диагонали на шахматной доске с вырезанной серединкой 2 x 2.

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

   _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 8|   |   |   |   |   |   |   |   |
  |_ _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|
 7|   |   |   |   |   |   |   |   |
  |_ _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|
 6|   |   |   |   |   |   |   |   |
  |_ _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|
 5|   |   |   |       |   |   |   |
  |_ _|_ _|_ _|       |_ _|_ _|_ _|
 4|   |   |   |       |   |   |   |
  |_ _|_ _|_ _|_ _ _ _|_ _|_ _|_ _|
 3|   |   |   |   |   |   |   |   |
  |_ _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|
 2|   |   |   |   |   |   |   |   |
  |_ _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|
 1|   |   |   |   |   |   |   |   |
  |_ _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|
    a   b   c   d   e   f   g   h

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

Например, в игре, в которой разрешается взять произвольное количество спичек из любой (но только одной) кучки, ответом будет

(0,0); (1,1); (2,2); (3,3); (4,4); (5,5)

а) Разрешается брать одну или две спички из любой кучки.

б) Разрешается брать любое количество спичек из любой кучки, а также перекладывать спичку из первой кучки во вторую

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

Роман Семизаров
roma7@zaba.ru
http://zaba.ru
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное