Размещено на http://www.allbest.ru/

Донецкий национальный университет

Математический факультет

РЕФЕРАТ

по дисциплине: «Дискретная математика»

на тему: Парадоксы комбинаторики

Выполнила :

студентка 1 курса гр.«Е»

Садовниченко Н.

Донецк

2011

Содержание

Введение

1. Комбинаторные задачи

2. Комбинаторный анализ

3. Парадокс дней рождения

Заключение

Приложения

Введение

«В таком огромном человеческом улье, -- заметил как-то Шерлок Холмс по поводу Лондона, -- возможны любые комбинации событий и фактов, возникает масса незначительных, но загадочных и странных происшествий...»*

Стоит заменить «человеческий улей» на «множество элементов произвольной природы», и высказывание великого сыщика станет неплохим описанием комбинаторной математики. (*А. Конан-Дойль, Голубой карбункул, Собр. соч. в 8 т., 1966, том 1, стр. 402.)

1. Парадоксы комбинаторики

1.1 Комбинаторные задачи

Числовые комбинаторные задачи так же стары, как сами числа. Еще в X веке до нашей эры китайские математики занимались изучением комбинаций и перестановок цифр. Древний китайский магический квадрат Ло Шу представляет собой одну из элементарных задач на составление комбинаций. Требуется в квадрате 3X3 так расставить девять цифр, чтобы суммы трех цифр в любом ряду по горизонтали, вертикали или диагонали были равны между собой. Квадрат Ло Шу (рис.1) является единственным решением этой задачи, не считая решений, получающихся из него при поворотах и отражениях.

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

Вплоть до прошлого века комбинаторные задачи, как и магические квадраты, воспринимались либо как нечто мистическое, либо как математическая забава не имеющая сколько-нибудь серьезного значения. Комбинаторные задачи и поныне служат источником различного рода головоломок, подчас довольно тривиальных. Рассмотрим, например, следующую задачу. В ящике лежат носки: два красных, два зеленых и два синих. Какое наименьшее число носков надо вынуть из ящика (ваши глаза при этом должны быть закрыты), чтобы среди них наверняка оказались два носка одного и того же цвета? Ответ к задаче о разноцветных носках: из четырех вынутых носков два наверняка будут одного цвета.

Встречаются среди комбинаторных задач и вопросы средней трудности. Например, сколькими разными способами можно разменять доллар, если у вас есть неограниченное число монет достоинством в полдоллара, четверть доллара, десять центов, пять центов и один цент? Ответ к задаче о том, как разменять один доллар: существуют 292 различных способа размена одного доллара (например: разменять один доллар двумя монетами по полдоллара) . Полное решение этой задачи приводится в книге Д. Пойа «Как решать задачу»* *Д. Пойа, Как решать задачу, М.,Учпедгиз, 1959.

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

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

Для полоски из шести, семи, восьми и девяти марок число разных способов складывания равно соответственно 38, 120, 353 и 1148. Общая формула для полоски из n марок пока не известна.

1.2 Комбинаторный анализ

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

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

Революция, происшедшая в биологии, была вызвана сенсационным открытием: выяснилось, что генетическая информация переносится молекулами нуклеиновой кислоты с помощью кода, состоящего из четырех букв. Каждое сообщение состоит лишь из трех букв, отбираемых теми же способами, которые вот уже более столетия изучаются в занимательной математике. Мириады комбинаторных задач возникают в теории информации с ее битами и «словами», записанными в абстрактных алфавитах, в теории вычислительных машин, работающих по принципу «да -- нет». В то же время именно вычислительные машины позволили решить немало комбинаторных задач, которые до их появления были недоступными из-за слишком большой сложности. Эти успехи также способствовали пробуждению интереса к комбинаторной математике.

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

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

На рис. 4 показан самый простой способ расположения чисел для этой задачи. Можно ли в изображенных на рисунке семи ячейках так разместить цифры от 1 до 7, чтобы сумма цифр в каждом из девяти рядов (трех горизонтальных и шести диагональных) была одной и той же. Эту сумму называют магической постоянной, и определить ее очень легко. Надо сложить все цифры от 1 до 7, а затем разделить результат на 3 -- число рядов, параллельных любому из допустимых направлений. Сумма цифр от 1 до 7 равна 28 и на 3 без остатка не делится. Поскольку магическая постоянная должна быть целым числом, мы доказали, что магического шестиугольника «второго порядка» (порядок равен числу ячеек, прилегающих к стороне шестиугольника) не существует.

Доказательство можно провести даже еще проще. Рассмотрим угловую ячейку А. Она принадлежит двум строкам: АВ и СА. Если бы суммы цифр в этих строках были равны, то в ячейках В и С должны были бы стоять одинаковые цифры, что противоречит условию задачи.

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

В 1910 году Клиффорд У. Адамс принялся за поиски магического шестиугольника третьего порядка. Он взял набор из шестиугольных керамических плиток, написал на них числа от 1 до 19 и начал составлять из них различные шестиугольники. Он отдавал этому занятию весь свой досуг в течение сорока семи лет, пока наконец в 1957 году, поправляясь после перенесенной операции, не нашел решения (рис. 5). Адамс перерисовал его на лист бумаги, но бумага куда-то затерялась, и в течение последующих пяти лет он тщетно пытался воспроизвести решение еще раз. В декабре 1962 года Адамс отыскал потерянную бумажку. Сумма чисел в каждом из пятнадцати рядов (пяти по вертикали и десяти диагональных) равна 38. Чтобы выявить двустороннюю симметрию фигуры, в группах, состоящих из двух и из трех ячеек, последовательные числа соединены линиями.

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

Адамс послал своё решение математику Чарлзу Триггу, признанному специалисту по комбинаторным задачам такого типа. Полученная от него открытка подтвердила, что решение Адамса было до сих пор не известно. А еще через месяц Тригг, прислал строгое доказательство того, что не существует более ни одного магического шестиугольника любого размера. Среди бесконечного числа способов размещения целых чисел от 1 до n в ячейках шестиугольной фигуры лишь один способ приводит к магическому шестиугольнику -- способ Адамса!

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

R=9(n4 -- 2n3 + 2n2 -- n) +2 / 2(2n-1)

Затем довольно сложным путем показал, что это выражение принимает целые значения лишь при n = 1 или n = 3. Магический шестиугольник из одной клетки тривиален. Один шестиугольник третьего порядка нашел Адамс. Возник вопрос, существуют ли другие комбинации девятнадцати целых чисел (не считая тех, которые получаются из решения Адамса с помощью поворотов и отражений), которые тоже образуют магический шестиугольник. Тригг показал, что ответ на этот вопрос отрицателен. Он решал задачу «в лоб» (исчертив груду бумаги разными схемами расположения чисел по шесть схем на каждом листе), комбинируя «грубую силу» с тонкими соображениями, позволяющими значительно сокращать число возможных вариантов. Некоторым читателям удалось проверить удивительный результат Адамса с помощью электронно-вычислительных машин. Один читатель сообщил, что шестиугольник Адамса был независимо открыт Томом Викерсом, который не знал, что этот шестиугольник единственный, и опубликовал его без всяких комментариев .

Предлагаю вам в качестве простого упражнения попробовать так переставить девятнадцать чисел в решении Адамса, чтобы получился шестиугольник, тоже магический, но в несколько ином смысле: сумма чисел в каждом ряду, состоящем из трех ячеек, равнялась бы 22, сумма четырехклеточного ряда была бы равна 42 и, наконец, сумма пятиклеточного ряда составляла бы 62. Такие магические шестиугольники уже исследовались, и их известно очень много. (Изложенная задача легко решается, если найти к ней правильный подход. Можно дать один наводящий совет: чтобы получить нужное расположение чисел, надо ко всем числам шестиугольника Адамса применить одно и то же простое преобразование) . Решение задачи, в которой нужно было переделать магический шестиугольник Адамса так, чтобы сумма чисел в любом трехклеточном ряду была равна 22, в четырехклеточном ряду --42 и в пятиклеточном ряду--62. Для этого надо написать в каждой ячейке разность между числом 20 и числом, стоящим в этой ячейке.

Всякий раз, когда целые числа располагаются по какой-нибудь красивой единственно возможной схеме, у этой схемы оказывается масса самых неожиданных свойств. Даже древний квадрат Ло Шу таит в себе неожиданности. В пятидесятых годах нашего века Лео Мозер обнаружил удивительный парадокс, который возникает, если рассматривать квадрат Ло Шу как таблицу относительного мастерства (шахматисты говорят «силы») девяти шахматистов (рис. 6). Пусть ряд A представляет команду из трех игроков, сила которых оценивается в 4, 9 и 2 балла. Ряды В и С относятся к игрокам двух других команд, сила которых оценивается баллами, стоящими в соответствующих клетках. Если между командами А и В происходит круговой турнир, в котором каждый член одной из команд играет с каждым членом второй команды, то победа будет пять раз принадлежать команде В и четыре раза -- команде А. Очевидно, что команда В сильнее команды А. Если соревнуются команды В и С, то С выигрывает пять раз, а в четырех играх терпит поражение, то есть команда С явно сильнее команды В. Что произойдет, если самая сильная из трех команд --команда С -- начнет турнир с самой слабой командой А? Решите эту задачу сами. Скажу лишь, что команда А выигрывает со счетом р: 4! Естественно возникает вопрос, какая же из команд в действительности самая сильная. Этот парадокс выявляет все недостатки круговой игры, если цель турнира состоит в том, чтобы выяснить соотношение сил команд-участниц. Из многих парадоксов, которыми занимался Мозер, изложенный парадокс является одним из самых простых. Парадокс остается в силе и в том случае, если каждой команде поставить в соответствие не строку, а столбец квадрата Ло Шу.

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

Предположим, что у вас есть бесконечно много марок достоинством в один, два, три, четыре и пять центов (имеется в виду, что у вас есть бесконечно много марок каждого достоинства). Вы хотите так расположить в виде квадрата 4X4 шестнадцать марок, чтобы ни в одном ряду, ни в одной строчке и ни на одной диагонали (в том числе и на двух славных диагоналях) не было двух марок одного достоинства. Иными словами, если вы поставите на любую марку шахматного ферзя, то никакой его ход не соединит двух марок одного и того же достоинства. Задача предполагает еще одно, дополнительное условие: полная стоимость всех шестнадцати марок должна быть максимально возможной. Какова эта стоимость? Ответ к задаче о размещении в квадрате 4X4 шестнадцати марок (рис. 7) достоинством по одному, два, три, четыре и пять центов искомый максимум равен пятидесяти центам. Секрет в том, что среди использованных марок четырехцентовых должно быть только три. «Не исключено, что, увидев решение, читатель признает себя побежденным», -- писал Генри Дью-дени, впервые публикуя эту головоломку.

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

3. Парадокс дней рождения

Парадокс дней рождения -- утверждение, гласящее, что если дана группа из 23 или более человек, то вероятность того, что хотя бы у двух из них дни рождения (число и месяц) совпадут, превышает 50 %. Для группы из 60 или более человек вероятность совпадения дней рождения хотя бы у двух её членов составляет более 99 %, хотя 100 % она достигает, только когда в группе не менее 367 человек (с учётом високосных лет).

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

Расчёт вероятности

В данном примере для расчёта вероятности того, что в группе из n человек как минимум у двух дни рождения совпадут, примем, что дни рождения распределены равномерно, то есть нет високосных лет, близнецов, рождаемость не зависит от дня недели, времени года и других факторов. В действительности, это не совсем так -- обычно летом рождается больше детей; кроме того, в некоторых странах из-за особенностей работы больниц больше детей рождается в определённые дни недели. Однако неравномерность распределения может лишь увеличить вероятность совпадения дней рождения, но не уменьшить: если бы все люди рождались только в 3 дня из 365, то вероятность совпадения дней рождения была бы очень высокой.

Рассчитаем сначала, какова вероятность p (n) того, что в группе из n человек дни рождения всех людей будут различными. Если n > 365, то в силу принципа Дирихле вероятность равна нулю. Если же n ? 365, то будем рассуждать следующим образом. Возьмём наугад одного человека из группы и запомним его день рождения. Затем возьмём наугад второго человека, при этом вероятность того, что у него день рождения не совпадёт с днем рождения первого человека, равна 1 -- 1/365. Затем возьмём третьего человека, при этом вероятность того, что его день рождения не совпадёт с днями рождения первых двух, равна 1 -- 2/365. Рассуждая по аналогии, мы дойдём до последнего человека, для которого вероятность несовпадения его дня рождения со всеми предыдущими будет равна 1 -- (n -- 1)/365. Перемножая все эти вероятности, получаем вероятность того, что все дни рождения в группе будут различными:

Тогда вероятность того, что хотя бы у двух человек из n дни рождения совпадут, равна

Значение этой функции превосходит 1/2 при n = 23 (при этом вероятность совпадения равна примерно 50.7 %). Вероятности для некоторых значений n иллюстрируются следующей таблицей:

Данную задачу можно переформулировать в терминах классической «задачи о совпадениях». Пусть урна содержит M(в данном случае 365) шаров, занумерованных числами 1,2,…M. Производится выборка с возвращением объёма n(в данном случае количество человек в группе), при этом рассматриваемые выборки считаются упорядоченными (то есть выборка 1,2,4,6 и 4,2,6,1 считаются различными).

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

Заключение

То, чем занимается комбинаторный анализ, можно назвать распределением элементов (отдельных предметов) по группам в соответствии с некоторыми заранее поставленными условиями. Играя, например, в шахматы, вы решаете комбинаторную задачу о том, как, следуя правилам игры, наилучшим образом разместить некоторое число элементов (шахматных фигур) на доске размером 8X8 клеток, чтобы один выделенный элемент (король противника) не мог избежать мата. Композитор, создавая новую мелодию, также решает комбинаторную задачу: он должен распределить элементы некоторого множества (в данном случае множества нот); так, чтобы мелодия доставляла слушателям эстетическое удовольствие. Комбинаторными задачами в самом широком смысле этого слова наполнена вся наша повседневная жизнь: рассаживая гостей за столом, решая кроссворды, играя в карты, составляя какие-либо расписания, открывая сейф с наборным замком, набирая номер на телефонном диске, мы решаем комбинаторную задачу. Вставляя ключ в отверстие замка, мы с помощью механического устройства (ключа) решаем комбинаторную задачу о нахождении того соотношения длин маленьких стерженьков, при котором цилиндр замка начнет вращаться.

Ещё несколько удивительных парадоксов:

Ш Парадокс Эпименида: Критянин говорит: «Все критяне -- лжецы»

Ш Парадокс исключений (англ.): «Если у каждого правила есть исключения, то каждое правило должно иметь хотя бы одно исключение, кроме этого» …а это не исключение к правилу, которое утверждает, что у каждого правила есть исключения?

Ш Прикажите слуге не слушаться Вас. Не слушаясь Вас, он ослушается приказа, так как он исполняет его, слушаясь Вас.

Ш Запрещено запрещать.

Ш Быть убеждённым в том, чтобы не иметь никаких убеждений.

Ш Советую Вам не слушать моих советов.

Ш Закон Бенфорда: Во многих списках чисел из произвольных реальных источников, большинство чисел начинаются с цифры 1.

Ш Парадокс лифта (англ.): Лифты чаще всего ходят в одном направлении -- от середины здания вниз к подвалу и вверх к чердаку

Ш Задача спящей красавицы: Вероятностная задача, которая может иметь в качестве ответа 1/2 или 1/3 в зависимости от того, с какой стороны рассматривать вопрос.

Ш Парадокс ценности: Почему вода стоит дешевле алмазов, хотя потребность человека в ней гораздо больше, чем в алмазах?

Приложения

Рис.1. Древний китайский магический квадрат Ло Шу.

Размещено на http://www.allbest.ru/

Рис.2. Две вертушки Рамона Луллия.

Рис.3. Как сложить полоску из двух, трёх и четырёх марок.

Рис. 4. Почему не существует магического шестиугольника второго порядка?

Рис.5. Единственный магический шестиугольник.

Рис.6. Ответ к задаче о складывании полоски из пяти марок.

Рис.7. Ответ к задаче о 16 марках.

Размещено на Allbest.ru