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

Вид материала

Документы

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

Подобный материал:

• Игра «Пятнадцать» Игра «Реверси» Игра «Пять в ряд» Игра «Поддавки», 184.89kb.
• Творческая работа по теме: «Игра как средство активизации познавательных процессов, 168.93kb.
• Игра в бисер Издательство "Художественная литература", Москва, 1969, 8794.91kb.
• Парная игра с произвольной суммой, 137.48kb.
• Уроки с измененными способами организации, 139.22kb.
• Тема игры : «Лесные чудеса», 73.19kb.
• Игра с реальностью всвоем рассказе ╙Игра в бисер√ Герман Гессе гово- рил об особом, 2844.37kb.
• Игра служит эмоциональным фоном. Если постоянно использовать Элементы учебно-познавательных, 138.98kb.
• А. Г. Групповая дискуссия и ролевая игра в социально-психологическом тренинге с подростками, 122.39kb.
• Игра как средство творческой реабилитации ребёнка с ограниченными возможностями здоровья, 157.82kb.

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

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


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

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


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

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

математики.


Москва

2008 год


Оглавление


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

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

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

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

2. Общие правила комбинаторики……………………………12
   
3. Проблемы комбинаторики…………………………………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 веках исчерпывали все содержание этой науки:

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

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

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

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