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

Фонд развития Международного университета

НОУ СОШ «Росинка»


Информационный проект

Применение комбинаторики в играх


Авторы проекта: Гусев Яша, Мельник Никита 5 класс.

Руководитель проекта: Ибряйчева Н.А. учитель

математики.


Москва

2008 год


Оглавление


Введение………………………………………………………………..3

Основная часть

Глава 1. Что такое комбинаторика. Ее история и горизонты……….5

1.1. Из истории комбинаторики и ее приложений………………..5

Общие правила комбинаторики……………………………12

Проблемы комбинаторики…………………………………14

Глава 2. Применение комбинаторики в играх………………………16

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

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

2.3. Игра в шашки………………………………………………….23

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

комбинаторики в играх………………………………………26

2.5. Рекомендации по использованию комбинаторики в играх…29

Заключение…………………………………………………………….31

Список источников информации……………………………………33

Приложения……………………………………………………………34

Приложение 1. Рекомендации по использованию

комбинаторики в играх………………………………35


Введение


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

Данная работа называется «Применение комбинаторики в играх».

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

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

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

Проект реализуется в предметных рамках математики.

Проект может быть квалифицирован как межпредметный, информационный и долгосрочный.

Объектом исследования являются комбинаторные задачи, а предметом исследования – использование комбинаторики в играх.

Гипотезой исследования стало следующее предположение: знание комбинаторного подхода к играм позволяет получить всегда 100% выигрыш.

Цель исследования: познакомиться с теоретическими основами комбинаторики, научиться применять их при решении задач – головоломок и в различных игровых ситуациях.

В соответствии с поставленной целью нами были сформулированы следующие задачи:

Изучить литературу по комбинаторике и занимательной математике.

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

Разработать рекомендации по применению комбинаторных правил в играх.

При работе над проектом применялись следующие методы:

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

2) эмпирические: исследование различных игровых ситуаций и результатов игр в шашки, шахматы.

Работа «Применение комбинаторики в играх» имеет практическое значение. Оно заключается в следующем: знание основных правил комбинаторики и умение их применять позволяет играть с умом и выигрывать.

Продуктом работы является рекомендации по применению комбинаторных правил.


Глава 1

Что такое комбинаторика. Ее история и горизонты

1. 1. Из истории комбинаторики и ее приложений


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

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

С аналогичными задачами, получившими название комбинаторных, люди столкнулись в глубокой древности. Уже несколько тысячелетий назад в Древнем Китае увлекались составлением магических квадратов, в которых заданные числа располагали так, что их сумма по всем горизонталям, по вертикалям и главным диагоналям была одной и той же. В Древней Греции подсчитывали число различных комбинаций длинных и коротких слогов в стихотворных размерах, занимались теорией чисел, изучали фигуры, которые можно составить из частей особым образом разрезанного квадрата и т.д. Говорить об уровне знаний древних греков в области комбинаторики затруднительно, поскольку до нас дошло далеко не все из их научного наследия, так как в 391 году до нашей эры толпа монахов разрушила центр языческой науки - александрийский мусейон ( храм муз) – и сожгла большую часть в нем библиотеки. Большинство книг безвозвратно погибло, и мы можем лишь догадываться об их содержании по кратким пересказам и намекам в сохранившихся рукописях. Конкретные комбинаторные задачи, касавшиеся перечислению небольших групп предметов, греки решали без ошибок. Аристотель описал без пропусков все виды правильных трехчленных силлогизмов, а его ученик Аристоксен из Тарента перечислил различные комбинации длинных и коротких слогов в стихотворных размерах. Большое внимание греческие ученые уделяли вопросам , пограничным между комбинаторикой и теорией чисел. Еще в vi веке до н.э. в школе философа и математика Пифагора возникло убеждение. Что миром правят числа, а вещи только отражение чисел. Поэтому, чтобы познать мир, пифагорейцы начали изучать свойства натуральных чисел. Их исследования о четных и нечетных числах заложили основу теории чисел. Наряду с комбинаторикой чисел греческие ученые занимались и отдельными вопросами геометрической комбинаторики – правильными и неправильными многогранниками, составлением фигур из 14 частей особым образом разрезанного квадрата и т.д. В VIII веке до н.э. начался расцвет арабской науки. Арабы перевели многие творения греческих ученых, изучили их, а затем продвинулись вперед в областях, мало привлекавших греков, - в науке о решении уравнений, теории и практике вычислений и т.д.. Арабские ученые знали и основное свойство биноминальных коэффициентов. Одновременно с арабами вычислением биноминальных коэффициентов занимались китайские математики. Они составили к VIII веку н.э. таблицу таких чисел вплоть до n =8, приведенную в книге алгебраиста Чжу Ши-дзе « Яшмовое зеркало». Имеются сведения, что астроном И Синь в VIII веке н.э. вычислил количество различных расположения фигур в игре, напоминавшей шахматы.

В начале XII века Западная Европа начала пробуждаться после многовековой духовной спячки. Развитие торговли с Востоком привело к проникновению в Европу арабской науки. В арабских учебных заведениях получил Леонардо, получивший прозвище Фибоначчи, который в дальнейшем привел в систему всю арифметику арабов и некоторые сведения Евклида и добавил к ним результаты своих изысканий. Труд Фибоначчи содержал и новые комбинаторные задачи, например, об отыскании наименьшего количества гирь, с помощью которых можно получить любой целый вес от 1 до 40 фунтов. Но главной заслугой Леонардо перед комбинаторикой было то, что он сформулировал и решил задачу о кроликах. Со времен греческих математиков были известны две последовательности, каждый член которых получался по определенным правилам из предыдущих – арифметическая и геометрическая прогрессии. В задаче Леонардо появилась новая последовательность, члены которой были связаны друг с другом соотношением Un = Un-1 + Un-2. Это была первая в истории науки формула, в которой следующий член выражался через два предыдущих. Подобные формулы получили название реккурентных. Метод реккурентных формул оказался впоследствии одним из самых мощных для решения комбинаторных задач.

Комбинаторика возникла как наука в XIII веке. В жизни тогдашнего общества большое место занимали азартные игры. В карты и кости выигрывались и проигрывались золото и бриллианты, дворцы и имения, породистые кони и дорогие украшения. Значительный толчок к развитию комбинаторики дали азартные игры, существовавшие еще в глубокой древности, но получившие особенное распространение после крестовых походов. Наибольшее распространение получила игра в кости – два или три кубика с нанесенными на них очками выбрасывали на стол, и ставку брал выбросивший большую сумму очков. Несмотря на древность игр, в которых применялись кости, они долго не подвергались математическому исследованию. Но игроки, неустанно упражнявшиеся в бросании костей, -6- заметили, что некоторые суммы очков выпадают часто, а другие – редко. Само слово «азартный» происходит от арабского «азар» - трудный, так называли редко выпадавшие комбинации костей.

Пытаясь понять, в чем тут дело, составляли таблицы, показывающие, сколькими способами можно получить то или иное число очков. На первых порах иногда допускалась ошибка – подсчитывали лишь число различных сочетаний костей, дававших данную сумму. Например, при бросании двух костей сумма 6 получается как 1+5, 2+4 и 3+3, сумма 7 - из сочетаний 1+6, 2+5 и 3+4, а сумма 8 – из сочетаний 2+6, 3+5 и 4+4. Так как каждый раз получается три различных сочетания с данной суммой, то делается ошибочный вывод, что суммы очков 6, 7 и 8 должны выпадать одинаково часто. Но это противоречило опыту – 7 очков выпадали чаще. Дело в том, что при бросании двух костей сочетание 3+3 может быть получено единственным образом, а сочетание 3+4 - двумя способами (3+4 и 4+3). Этим объясняется большая частота выпадения суммы 7.

Таким образом, оказалось, что надо учитывать не только сочетания очков, но и их порядок. Этими вопросами занимались такие известные итальянские математики XVI века, как Д. Кардано, Н. Тарталья и Другие. Наиболее полно их исследовал в XVII веке Галилео Галилей.

Одним из самых азартных игроков в кости в XVII веке был шевалье де Мере, непрерывно изобретавший новые виды состязаний. Например, он предложил, что будет бросать четыре кости и брать выигрыш в случае, когда хотя бы одна из них одна из них откроется на шести. Однако вскоре его партнеры отказались от участия в такой игре – шевалье чаще выигрывал, чем проигрывал. Тогда де Мере придумал новый вариант – он бросал несколько раз пару костей и брал выигрыш, если хотя бы раз выпадали две шестерки. Надо было определить, сколько следует сделать бросков, чтобы игра была столь же выгодна, как и первая. Шевалье решил, что надо бросать кости 24 раза. Ведь при четырех бросках одной кости шестерка выпадала более чем в половине случаев, а так как вторая кость дает шесть вариантов выпадения, то и надо умножить 4 на 6. Рассуждения казались безукоризненным, но опыт не подтвердил надежд де Мере – теперь он стал чаще проигрывать, чем выигрывать.

Другой проблемой для де Мере была задача о разделе ставки. Проблема состояла в следующем: «матч» ведется до шести выигранных партий; он был прерван, когда один игрок выиграл 5 партий, а другой 4; как разделить ставку? Было ясно, что раздел в отношении 5:4 несправедлив.

Де Мере обратился за разъяснениями к двум крупнейшим математикам Франции XVII века – Блезу Паскалю и Пьеру Ферма. Разбираясь в этих и других задачах, поставленных перед ними де Мере, они сформулировали и доказали первые теории комбинаторики и теории вероятностей. А задачу о разделе ставки Паскаль решил в общем случае, когда одному игроку остается r партий, а второму s партий. Другое решение задачи дал Ферма.

-7- Работы Паскаля и Ферма ознаменовали рождение двух ветвей математики – комбинаторики и теории вероятностей. Если до них комбинаторные проблемы лишь затрагивались в общих трудах по астрологии, логике и математике, а большей частью относились к области математических развлечений, то уже в 1966году Готфрид Вильгельм Лейбниц публикует «Диссертацию о комбинаторном искусстве». Про эту диссертацию и о творчестве Лейбница Иммануил Кант сказал: « Знаменитый Лейбниц обладал многими действительными знаниями, которыми обогатил науки, но еще более грандиозны были его замыслы, выполнения которых мир от него тщетно ждал». Диссертация Лейбница должна была стать началом большой работы, о которой он часто упоминал в своих письмах и печатных трудах и для которой делал в своих записных книжках многочисленные заметки. Из них видно, что Лейбниц планировал для комбинаторики все новые и новые приложения: к кодированию и декодированию, играм, статистике, теории наблюдений. Он считал, что комбинаторика должна заниматься одинаковым и различным, похожим и непохожим, абсолютным и относительным расположением, в то время как обычная математика занимается большим и малым, единицей и многим, целым и частью. Иными словами, под комбинаторикой Лейбниц понимал примерно то, что мы теперь называем дискретной математикой. Проекты Лейбница казались несбыточными здравомыслящим математикам того времени, но сейчас после создания компьютеров, многие планы Лейбница стали претворяться в жизнь.

В 1713 году племянник Якоба Бернулли (скончавшегося в 1705 году) Николай опубликовал часть II книги Якоба Бернулли « Искусство предположений», в которой указывались формулы для числа размещений из n элементов по k. Выводились выражения для степенных сумм и т.д.

Замечательные достижения в области комбинаторики принадлежат одному из величайших математиков XVIII века Леонарду Эйлеру, швейцарцу, прожившему почти всю жизнь в России, где он был членом Петербургской академии наук. Основные работы Эйлера в области науки были посвящены математическому анализу, в котором он предложил новые пути , создал целый ряд новых областей и подвел итоги исследованиям в других областях. Но у Эйлера хватало времени размышлять о задачах, которые, казалось бы, не заслуживали его внимания, - о том, можно ли обойти мосты в Кенигсберге (ныне Калининграде) так, чтобы не побывать дважды на одном и том же мосту; можно ли поставить 36 офицеров из 6разных полков так, чтобы в каждой шеренге и каждой колонне было по одному офицеру каждого воинского звания из каждого полка; сколькими способами можно разбить данное число на слагаемые и т.д. Но, странное дело, работа о мостах явилась зерном, из которого впоследствии выросли топология и теория графов, задача об офицерах оказалась сейчас связанной с планированием экспериментов, а методы, использованные при решении задач о разбиении чисел, после длительного и сложного и сложного пути развития превратились в науку об интегральных преобразованиях, применяемую для решения уравнений математической физики.

После работ Паскаля и Ферма, Лейбница и Эйлера можно было уже говорить о комбинаторике как самостоятельной ветви математики, тесно связанной с такими областями науки, как теория вероятностей, учение о рядах и многими другими. В конце XVIII века немецкий ученый Гинденбург и его ученики сделали попытку построить общую теорию комбинаторного анализа. Однако она не увенчалась успехом – в то время еще не было накоплено достаточного количества важных и интересных задач, которые могли бы дать необходимый фундамент для такой теории.

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


1.2.Общие правила комбинаторики


По мере развития комбинаторики выяснилось, что, несмотря на внешнее различие изучаемых ею вопросов, многие из них имеют одно и тоже математическое содержание и сводятся к задачам о конечных множествах и подмножествах. Постепенно выявилось несколько основных типов задач, к которым сводится большинство комбинаторных проблем. В основе теории комбинаторики лежат два правила: правило суммы и правило произведения. Рассмотрим следующий пример. Если на одной полке книжного шкафа стоит 30 различных книг, а на другой – 40 различных книг (и не таких, как на первой полке), то выбрать одну книгу, стоящую на этих полках, можно 30+40=70 способами. Обобщением этого примера является правило суммы: если элемент a можно выбрать m способами, а элемент b – n способами, причем любой выбор элемента а отличен от любого выбора элемента b, то выбор «а» или «b» можно сделать m+n способам На языке теории множеств это правило формулируется следующим образом:

Если пересечение конечных множеств А и В пусто, то число элементов в их объединении равно сумме чисел элементов множества А и В: n( AU B) = n(A) + n(B)

При использовании правила суммы надо следить, чтобы ни один из способов выбора объекта А не совпадал с каким-нибудь способом выбора объекта В. Если такие совпадения есть, правило суммы утрачивает силу, и мы получаем лишь m+n-k способов выбора, где k – число совпадений.

Пример №1. При формировании экипажа космического корабля имеется 10 претендентов на пост командира экипажа, 20 – на пост бортинженера и 25 – на пост космонавта-исследователя. Ни один кандидат не претендует одновременно на два поста. Сколькими способами можно выбрать одну из кандидатур или командира, или бортинженера, или космонавта-исследователя? Решение. Обозначим множество кандидатов на пост командира корабля через А, множество на пост борт-инженера через В и множество кандидатов на пост инженера-исследователя через С. Тогда по условию n(A)=10, n(B)=20, n(C)=25.

Кроме того, А∩В=Ǿ, А∩С=Ǿ, В∩С=Ǿ. Используя формулу, имеем: n(AUBUC)=n(A) + n(B) + n(C) =55 способов. Правило произведения несколько сложнее, чем правило суммы. Часто при составлении комбинации из двух элементов известно, сколькими способами можно выбрать первый элемент, и сколькими способами второй, причем число способов выбора второго элемента не зависит от того, как именно выбран первый элемент.

Правило произведения заключается в следующем утверждении: Пусть множество А состоит из элементов (а1, а2,…, аٕm) и множество В – из элементов (b1,b2,…, bk). Пусть из множества А выбирается любой из его m элементов и независимо от него из множества В выбирается любой из его k элементов. Тогда общее число N всевозможных пар равно m·k, т.е. N=n(A)·n(B).

Пример №2 . Сколько слов, содержащих 6 букв, можно составить из 33 букв русского алфавита при условии, что любые две стоящие рядом буквы различны? При этом учитываются не только слова, имеющие смысл, но и такие бессмысленные, как «трнаук» и т.п.

Решение. На первое место у нас 33 кандидата. Но после того как первая буква выбрана, вторую можно выбрать 32 способами – ведь повторять первую букву нельзя. На третье место тоже 32 кандидата – первую букву уже можно употребить, а вторую нельзя. Также убеждаемся, что на все места, кроме первого, имеется 32 кандидата. А так число равно 5, то получаем ответ 33·32·32·32·32·32 = 1 107 296 256. Ответ: 1 107 296 256 слов.

С помощью общих правил комбинаторики можно решать задачи различных типов. Однако как в геометрии неудобно всегда сводить решение задачи к аксиомам, а удобнее пользоваться теоремами, так и в комбинаторике вместо решения задачи по общим правилам часто удобнее пользоваться готовыми формулами. Дело в том, что некоторые типы задач встречаются значительно чаще других. Комбинациям, которые встречаются в этих задачах, присвоены особые названия – размещения, перестановки и сочетания.


1.3. Проблемы комбинаторики


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

Задачи комбинаторики

Найти конфигурацию элементов, обладающую заранее заданными свойствами.

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

Доказать существование или отсутствие конфигурации с заданными свойствами.

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

Итак, мы пришли еще к двум проблемам комбинаторики, которые в XVIII и XIX веках исчерпывали все содержание этой науки:

Найти общее число конфигураций с заданными свойствами.

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

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

Из всех решений данной комбинаторной задачи выбрать оптимальное по тем или иным параметрам.

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


Глава 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 раз собрать урожай. Только тогда получилось бы нужное для Сессы количество зерен.

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

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


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

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










●




























●




























●







●
















●








































●
















●












●





































































































































































































●































●
















●
















●
















●





































●










●




















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


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

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

Подставим вместо n =^ 8 и получим, что N = 1288

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

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

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

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


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

Решение. По формуле находим, что N =2(n³ - n²). N =896.

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

Пусть ладья стоит на произвольной клетке. Тогда вражеский король может занимать любую из оставшихся 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 клеток, отличающихся от принятых у нас. Однако с течением времени установились современные правила: шашки имеют два цвета, ходят они только вперед, взятие происходит перескакиванием через шашку соперника, на противоположном конце доски шашка превращается в дамку и т.д. Появление шашек на Руси связывают с именем киевского князя Владимира Мономаха.

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

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

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