Історія розвитку комбінаторики та деякі її застосування, Детальна інформація

То проигравший снова их берет,

И мечет их один в унылой злости;

Другого провожает весь народ…

Не дивлячись на давнину ігор, в яких застосовувались кості (археологічні розкопки показали, що гральні кості були знайомі ще етрускам і жителям Мохенджо-Даро), вони довго не піддавались математичному дослідженню. Але гравці, що без перестану тренувались і киданні костей, помітили, що деякі суми очок випадають часто, а інші – рідко. Намагаючись зрозуміти у чому справа, склали таблиці, що показували, скількома способами можна отримати те чи інше число очок. Спочатку допускалась помилка – підраховували лиш кількість різних суміщень костей, що давали дану суму. Наприклад, при киданні двох костей сума 6 отримувалася з поєднань (1, 5) , (2, 4), (3, 3), а сума 7 – з поєднань (1, 6), (2, 5), (3, 4). Так як в обох випадках отримується три різних поєднання з даною сумою, то можна зробити помилкове твердження, що сума очок 6, 7 і 8 (що також отримується з трьох поєднань костей) повинні випадати однаково часто. Але це суперечить досвіду – 7 очок випадає частіше. Справа в тому, що при киданні двох костей поєднання (3, 3) може бути отримане єдиним шляхом, а поєднання (3, 4) – двома шляхами. Цим пояснюється часте випадання суми 7.

Таким чином, виявилось, що потрібно враховувати не тільки поєднання очок, але і їх порядок.

Більш складними виявились відповідні досліди для трьох костей. Тут при врахуванні порядку костей виявляється 216 різних комбінацій, а без порядку – 56.

Цими питаннями займались такі видатні італьянські математики XVI ст., як Д. Кардано, Н. Тарталья та ін. Більш повніше дослідив його в XVII ст. Галілео Галілей, але його рукопис залишався неопублікованим до 1718 р.

Гравець і вчення

$

$

$

$

$

.

6

Ffoe

AE

a

AE

\x151C\x6668\x9127\x1600\x6768\xEF44\x4300\x204A\x6100\x204A\x6D00\x2248\x7304\x2248\x1D04Одним з найазартніших гравців в кості у XVII ст. був шевальє де Маре, котрий без перестану знаходив нові види змагань. Наприклад, він запропонував, що буде кидати чотири кості і буде брати виграш лише у випадку, коли хоча б одна з них відкриється на шести. Проте скоро його партнери відмовились від такої гри – шевальє частіше вигравав, ніж програвав. Тоді де Маре придумав інший варіант – він кидав декілька раз пару костей і забирав виграш в тому випадку, якщо хоча б раз випадали дві шестірки. Треба було лише визначити, скільки потрібно зробити кидків, щоб гра була йому така ж вигідна, як і перша. Шевальє вирішив, що треба кидати 24 рази. Адже при чотирьох кидках однієї кості шестірка випадала більш ніж у половині випадків, а так як друга кость дає шість варіантів випадання, то й треба помножити 4 на 6.

Роздуми здавалися незаперечними, але досвід не підтвердив надій де Маре – тепер він став частіше програвати, ніж вигравати. В повному нерозумінні він звернувся до двох великих математиків Франції XVII ст. – Блезу Паскалю та П’єру Ферма. Розбираючись в цій та інших задачах, поставлених перед ними де Маре, вони сформулювали і довели перші теореми комбінаторики та теорії ймовірностей.

Нова гілка математика

Роботи Паскаля і Ферма дали поштовх для народження двох нових гілок математичної науки – комбінаторики і теорії ймовірностей. Якщо до них комбінаторні проблеми лише торкалися в загальних роботах по астрології, логіці і математиці, а більшою частиною відносились до області математичних розваг, то вже у 1666 р. Готтфрід Вільгельм Лейбніц публікує „Дисертацію про комбінаторне мистецтво”, в котрій вперше з’являється сам термін „комбінаторика”. Титульний лист книги двадцятирічного автора, котрий мав учений степінь бакалавра... юриспруденції, обіцяв додатки до всіх областей науки і новий підхід до логіки винаходження, а тематика введення могла суперничати по своїй широті з програмою, яку, як свідчить Льюіс Керрол, намітив Плотник для бесід з устрицями. Проте, про королів та капусту там не йшлося, але проголошувалось відношення теорії до замків, органів, силогізмів, змішанню кольорів та віршобудуванні, логіки, геометрії, воєнного мистецтва, юриспруденції, граматики, медицини та теології.

Але про цю дисертацію можна сказати те ж, що Еммануїл Кант сказав про роботи Лейбніца: „Знаменитий Лейбніц володів багатьма дійсними знаннями, котрими він збагатив науки, але ще більш грандіозними були його замисли, виконання котрих весь світ з захопленням чекав від нього”. Дисертація Лейбніца мала стати лише початком великої роботи, про яку він часто згадував у своїх листах і друкованих працях та для котрої робив у своїх записних книжках спеціальні помітки. З них видно, що Лейбніц планував для комбінаторики все нові й нові додатки: до кодування і декодування, ігор, статистики, теорії спостережень. Він вважав, що комбінаторика повинна займатись однаковим і різним, схожим і несхожим, абсолютним і відносним розміщенням, в той час як звичайна математика займається великим і малим, одниною і множиною, цілим і частиною. Іншими словами, під поняттям комбінаторики Лейбніц розумів приблизно те, що ми тепер називаємо дискретною математикою. До області комбінаторики Лейбніц відносив і „універсальну характеристику” – математику суджень, тобто прообраз теперішньої математичної логіки.

Проекти Лейбніца здавалися нездійсненними тогочасним математикам, але тепер, після створення ЕВМ, багато планів Лейбніца почали втілюватися у життя, а дискретна математика виросла у своєму значенні настільки, що почала суперничати з класичним математичним аналізом.

В 1713 р. була опублікована книга „Мистецтво припущень” Якоба Бернуллі, в якій вказувались формули для числа розміщень з n елементів по k, виводились вираження для степеневих сум та ін. Чудові досягнення в області комбінаторики належать одному з найбільших математиків XVIII ст., Леонарду Ейлеру, швейцарцю, що прожив майже все життя в Росії, де він був членом Петербурзької академії наук. Основна частина наукової роботи Ейлера присвячена математичному аналізу, в якому він проклав нові шляхи, створив цілий ряд нових областей і закінчив досліди інших областей. Але у Ейлера вистачало часу думати і про задачі, які, здавалося б, не заслуговували його уваги, - про те, чи можна обійти мости в Кенігсберзі (нині Калінінграді) так, щоб не побувати двічі на одному і тому самому мості, чи можна поставити 36 офіцерів з 6 різних полків так, щоб у кожній шерензі і у кожній колоні було по одному офіцеру кожного військового звання з полку, скількома способами можна розбити число на частини і т.д. Але, дивна справа, робота про мости виявилась так званим зерном, з якого потім виросли топологія і теорія графів, задача про офіцерів виявилась зараз пов’язаною з плануванням експериментів, а методи, що використовувалися при розв’язуванні задачі про розбиття чисел, після довгого та важкого шляху розвитку перетворилась в науку про інтегральні перетворення, що використовується для розв’язання рівнянь математичної фізики.

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

В ХІХ ст. в ході досліджень по комбінаториці стали помічатися зв’язки цієї теорії з визначеннями кінцевими геометріями, групами, математичної логіки і т.д.

Шифри та анаграми

Не тільки азартні ігри спонукали математиків до комбінаторних роздумів. Ще з давніх давен дипломати, що прагнули до таємних переписів, винаходили все більш складні шифри, а секретні служби інших держав намагалися ці шифри розгадати. Одним з найпростіших шифрів була „тарабарська грамота”, в якій літери замінювались іншими за певними правилами. Проте такі шифри легко розгадувалися за характерними поєднаннями літер. Тому почали застосовувати шифри, які були основані на комбінаторних методах, наприклад, на різних перестановках літер, заміна літер з використанням ключових слів та ін.