Geum.ru

Игра в шашки Игра в 15 и рекомендации по использованию

Вид материалаДокументы

Содержание


Число расстановок мирных ферзей.
Число расстановок двух мирных ферзей.
8 и получим, что N = 1288 Число расстановок боевых слонов.
Число расстановок двух боевых коней.
Число расстановок двух боевых ладей.
Простая сила шахматных фигур.
Решим следующую задачу о шашках.
Подобный материал:
1   2   3
Глава 2 Применение комбинаторики в играх


Всю математику, в силу ее абстрактности,

можно считать игрой ума.

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

2.1 Магические квадраты


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

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

Расположить числа 1,2,3,4,5,6,7,8,9 в виде квадрата так, чтобы суммы чисел по каждому столбцу, строке и диагоналям были одинаковы.

Методом прямого перебора решить эту задачу без компьютера немыслимо – 9 чисел можно расположить в виде квадрата 362880 способами. Поэтому проведем математический анализ задачи. Выясним сначала, какой должна быть искомая сумма. Так как 1+2+3+4+5+6+7+8+9=45, то в каждой из 3 строк сумма чисел должна равняться 15. Это значительно уменьшает необходимый перебор – выбрать 3 слагаемых из данных чисел так, чтобы сумма равнялась 15, можно лишь 8 способами: 9+5+1, 9+4+2, 8+6+1, 8+5+2, 8+4+3, 7+6+2, 7+5+3, 6+5+4. А число строк, столбцов, и диагоналей в квадрате тоже ровно 8. Значит, каждая из написанных комбинаций должна ровно один раз войти в искомый квадрат. Далее замечаем, что только 5 в эти тройки 4 раза. Поэтому оно и должно стоять в центре таблицы – на пересечении центральных строки, столбца и диагонали. Оставшиеся числа 1,3,7 и 9 занимают места сверху, снизу, слева и справа от центра. Диагональные тройки (8,5,2) и (6,5,4) можно расположить 8 различными способами (у нас 2 диагонали, на каждой из которых можно еще переставлять крайние элементы). После выбора положения чисел 8,2,6,4 положение остальных чисел однозначно определено (рис. 70). Мы не только нашли один магический квадрат 3-го порядка, но и описали все квадраты из чисел 1,2,3,4,5,6,7,8,9.

4
9
2

3
5
7

8
1
6


Рис. 1. Магический квадрат 3 порядка.

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



1
2
3
4

5
6
7
8

9
10
11
12

13
14
15
16

.

Рис. 2. Магический квадрат 4 порядка.


если в нем на каждой его большой диагонали поменять местами числа, симметричные относительно центра квадрата, т.е. числа 1 и 16, 6 и 11, 4 и 13, 7 и 10 (рис. 72).

5
11
10
8

9
7
6
12

4
14
15
1

16
2
3
13



Рис.3.

Еще один магический квадрат 4 порядка. В том, что полученный квадрат 4-го порядка магический, можно легко убедиться. Если же в нем поменять местами второй и третий столбцы (рис. ), то снова получится магический квадрат, изображенный на гравюре Альбрехта Дюрера «Меланхолия». Средние цифры нижней строки обозначают год – 1514, в котором Дюрер создал свою знаменитую гравюру.



16
3
2
13

5
10
11
8

9
6
7
12

4
15
14
1


Рис.4 Магический квадрат, изображенный на гравюре «Меланхолия» А.Дюрера.

Еще более значительным является магический квадрат 4-го порядка, найденный в индийской надписи 11 или 12 в. н.э. (рис. 74).



7
12
1
14

2
13
8
11

16
3
8
11

9
6
15
4

Рис.5. Индийский магический квадрат.

Этот квадрат сохраняет свойство быть магическим и после того, как его строки одна за другой перемещаются сверху вниз (сначала первая под четвертой, затем вторая под бывшей первой и т.д.) или столбцы аналогично перемещаются слева направо. Иными словами, если сделать ковер из таких квадратов, то, вырезав любую его часть из 4 строк и 4 столбцов, получаем снова магический квадрат. Всего существует порядка 880 типов магических квадратов 4- го порядка. Такими построениями занимались один из основателей теории чисел П. Ферма, выдающийся английский математик А. Келли, известный математик О. Веблен. Удалось построить, например, магические квадраты, которые после удаления нескольких крайних полос снова дают магические квадраты; магические кубы, в которых все квадратные грани, параллельные паре боковых граней, представляют магические квадраты с одной и той же суммой и т.д.

Замечательные магические квадраты построил знаменитый американский ученый и политический деятель Бенджамин Франклин. Например, он построил магический квадрат восьмого порядка, в котором не только сумма чисел в каждой строке, каждом столбце и каждой диагонали равна 260, но еще сумма чисел как в левой, так и в правой половинах каждой строки равна 130, но и то же значение имеет сумма в верхних и нижних половинах каждого столбца. Несомненно, Франклин имел какие-то общие методы построения квадратов со столь замечательными свойствами, так как простым перебором их построить невозможно.

Ныне построению магических квадратов удалось научить ЭВМ – некоторые пакеты математических программ для персональных компьютеров содержат операцию построения магического квадрата заданного порядка.


2.2 Шахматная комбинаторика


Существует древняя индийская легенда.

Брамин Сесса, сын, Драгера, придумал игру в шахматы, где король, хотя и самая важная фигура, не может ступить шагу без помощи и защиты своих подданных пешек и других фигур. Изобрел он эту игру в забаву своему монарху и повелителю Индии, Шерану. Царь Шеран, восхищенный выдумкой брамина, сказал, что даст ему все, что только брамин захочет.

- В таком случае, - сказал Сесса, - прикажи дать мне столько пшеничных зерен, сколько их получится, если на первую клетку шахматной доски положить 1 зерно, на вторую – 2 зерна, на третью – 4, а на четвертую – 8 и т.д., все удваивая, пока не дойдут до шестьдесят четвертой клетки.

Повелитель Индии не смог этого сделать. Количество требуемых зерен выражалось двадцатизначным числом. Чтобы удовлетворить «скромное» желание брамина, нужно было 8 раз засеять всю поверхность земного шара и 8 раз собрать урожай. Только тогда получилось бы нужное для Сессы количество зерен.

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

Рассмотрим несколько задач .

  1. Число расстановок мирных ферзей. Каково число разных способов расстановок восьми мирных ферзей?

Решение. Приведем 2 существенно разных решений, из которых можно вращением доски против часовой стрелки получать циклические решения и обращением номеров столбцов – обратные










●



























●



























●







●















●







































●















●











●




































































































































































































●






























●















●















●















●




































●









●



















Рис. 6 Расстановка ферзей.


Число расстановок двух мирных ферзей. Сколькими способами можно расставить на шахматной доске два мирных ферзя?

Решение. Пусть n- размерность квадратной шахматной доски n x n Nn - искомое количество способов размещения двух неатакующих ферзей. Применяя метод конечных разностей, находим Nn =(3n↑4 – 10n³ + 9n³ - 2n) :3

Подставим вместо n = 8 и получим, что N = 1288
  1. Число расстановок боевых слонов. Сколько способов расстановки слонов, угрожающих всем полям шахматной доски?

Решение. Для доски nxn искомое число способов расстановки 8 слонов-часовых находится по формуле: N = ( ( 2k – 1)!( 4k² + k)) при n =4k, N8 =256
  1. Число расстановок двух боевых коней. Сколькими способами можно расставить на шахматной доске два защищающихся (или атакующих друг друга) коня?

Решение. Пусть n – размерность шахматной доски. Число расстановок двух боевых слонов находим по формуле: Nn =4(n² - 3n + 2) . При n =8 имеем, что N8 =168

  1. Число расстановок двух боевых ладей. Сколькими способами можно расставить на шахматной доске две атакующих (или защищающихся друг от друга) разноцветные ладьи?

Решение. По формуле находим, что N =2(n³ - n²). N =896.
  1. Простая сила шахматных фигур. Абсолютную силу шахматной фигуры можно определить как число полей, которым она угрожает, или как вероятность дать этой фигурой простой шах королю на пустой доске.

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

fладья = 14/63=2/9

Это и будет абсолютной силой ладьи.

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

Решение.

Число полей, которым может угрожать конь, зависит от его положения на доске. Если он стоит в одном из четырех углов, то угрожает только двум полям. Рассмотрев все положения коня, находим абсолютную силу коня: fконь =(4x2 + 8x3 + 20x4 + 16x6 + 16x8 ); (64x64) =1/12.

Слон, стоящий на любой из 28 клеток четырех граничных горизонталей и вертикалей, угрожает 7 полям. Стоя на 20 полях следующей квадратной рамки, слон угрожает 9 полям т.д. Абсолютная сила слона равна: fслона = (28x2 + 20x9 + 12x11 + 4x13)/ (64x63) = 5/36.

Поскольку ферзь угрожает полям, как вместе взятые ладья и слон, то его абсолютная сила: fферзь =2/9 + 5/36 =13/36. Отнеся абсолютные силы фигур к общему знаменателю т36, находим относительные силы:

fконь = 3, fслон = 5, fладья = 8 b fферзь = 13.

2.3 Игра в шашки


С древних времен известно множество разновидностей шашечных игр. Известно, что в шашки (правда, отличающихся от наших) играли египетские фараоны. Затем игра проникла в Грецию и Древний Рим. Правила ее со временем изменялись. В гробнице египетского фараона Тутанхамона была найдена шашечная доска размером 3х10 клеток, отличающихся от принятых у нас. Однако с течением времени установились современные правила: шашки имеют два цвета, ходят они только вперед, взятие происходит перескакиванием через шашку соперника, на противоположном конце доски шашка превращается в дамку и т.д. Появление шашек на Руси связывают с именем киевского князя Владимира Мономаха.

Решим следующую задачу о шашках.

Сколькими способами можно поставить на доску две шашки – белую и черную так, чтобы белая шашка могла бить черную?

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

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



5



5



6

1



2



2



1






2



4



4



2

2



4



4



2






2



4



4



2

2



4



4



2






1



2



2



1

1



2



2



1




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

полям. Они изображены на рисунке.
0



0



0



0

0



2



2



1






2



4



4



0

0



4



4



2






2



4



4



0

0



4



4



2






1



2



2



0

0



0



0



0