Реферат: Історія розвитку комбінаторики та деякі її застосування
Другого провожает весь народ…
Не дивлячись на давнину ігор, в яких застосовувались кості (археологічні розкопки показали, що гральні кості були знайомі ще етрускам і жителям Мохенджо-Даро), вони довго не піддавались математичному дослідженню. Але гравці, що без перестану тренувались і киданні костей, помітили, що деякі суми очок випадають часто, а інші – рідко. Намагаючись зрозуміти у чому справа, склали таблиці, що показували, скількома способами можна отримати те чи інше число очок. Спочатку допускалась помилка – підраховували лиш кількість різних суміщень костей, що давали дану суму. Наприклад, при киданні двох костей сума 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 р.
Гравець і вчення
Одним з найазартніших гравців в кості у XVII ст. був шевальє де Маре, котрий без перестану знаходив нові види змагань. Наприклад, він запропонував, що буде кидати чотири кості і буде брати виграш лише у випадку, коли хоча б одна з них відкриється на шести. Проте скоро його партнери відмовились від такої гри – шевальє частіше вигравав, ніж програвав. Тоді де Маре придумав інший варіант – він кидав декілька раз пару костей і забирав виграш в тому випадку, якщо хоча б раз випадали дві шестірки. Треба було лише визначити, скільки потрібно зробити кидків, щоб гра була йому така ж вигідна, як і перша. Шевальє вирішив, що треба кидати 24 рази. Адже при чотирьох кидках однієї кості шестірка випадала більш ніж у половині випадків, а так як друга кость дає шість варіантів випадання, то й треба помножити 4 на 6.
Роздуми здавалися незаперечними, але досвід не підтвердив надій де Маре – тепер він став частіше програвати, ніж вигравати. В повному нерозумінні він звернувся до двох великих математиків Франції XVII ст. – Блезу Паскалю та П’єру Ферма. Розбираючись в цій та інших задачах, поставлених перед ними де Маре, вони сформулювали і довели перші теореми комбінаторики та теорії ймовірностей.
Нова гілка математика
Роботи Паскаля і Ферма дали поштовх для народження двох нових гілок математичної науки – комбінаторики і теорії ймовірностей. Якщо до них комбінаторні проблеми лише торкалися в загальних роботах по астрології, логіці і математиці, а більшою частиною відносились до області математичних розваг, то вже у 1666 р. Готтфрід Вільгельм Лейбніц публікує „Дисертацію про комбінаторне мистецтво”, в котрій вперше з’являється сам термін „комбінаторика”. Титульний лист книги двадцятирічного автора, котрий мав учений степінь бакалавра... юриспруденції, обіцяв додатки до всіх областей науки і новий підхід до логіки винаходження, а тематика введення могла суперничати по своїй широті з програмою, яку, як свідчить Льюіс Керрол, намітив Плотникдля бесід з устрицями. Проте, про королів та капусту там не йшлося, але проголошувалось відношення теорії до замків, органів, силогізмів, змішанню кольорів та віршобудуванні, логіки, геометрії, воєнного мистецтва, юриспруденції, граматики, медицини та теології.
Але про цю дисертацію можна сказати те ж, що Еммануїл Кант сказав про роботи Лейбніца: „Знаменитий Лейбніц володів багатьма дійсними знаннями, котрими він збагатив науки, але ще більш грандіозними були його замисли, виконання котрих весь світ з захопленням чекав від нього”. Дисертація Лейбніца мала стати лише початком великої роботи, про яку він часто згадував у своїх листах і друкованих працях та для котрої робив у своїх записних книжках спеціальні помітки. З них видно, що Лейбніц планував для комбінаторики все нові й нові додатки: до кодування і декодування, ігор, статистики, теорії спостережень. Він вважав, що комбінаторика повинна займатись однаковим і різним, схожим і несхожим, абсолютним і відносним розміщенням, в той час як звичайна математика займається великим і малим, одниною і множиною, цілим і частиною. Іншими словами, під поняттям комбінаторики Лейбніц розумів приблизно те, що ми тепер називаємо дискретною математикою. До області комбінаторики Лейбніц відносив і „універсальну характеристику” – математику суджень, тобто прообраз теперішньої математичної логіки.
Проекти Лейбніца здавалися нездійсненними тогочасним математикам, але тепер, після створення ЕВМ, багато планів Лейбніца почали втілюватися у життя, а дискретна математика виросла у своєму значенні настільки, що почала суперничати з класичним математичним аналізом.
В 1713 р. була опублікована книга „Мистецтво припущень” Якоба Бернуллі, в якій вказувались формули для числа розміщень з n елементів по k, виводились вираження для степеневих сум та ін. Чудові досягнення в області комбінаторики належать одному з найбільших математиків XVIII ст., Леонарду Ейлеру, швейцарцю, що прожив майже все життя в Росії, де він був членом Петербурзької академії наук. Основна частина наукової роботи Ейлера присвячена математичному аналізу, в якому він проклав нові шляхи, створив цілий ряд нових областей і закінчив досліди інших областей. Але у Ейлера вистачало часу думати і про задачі, які, здавалося б, не заслуговували його уваги, - про те, чи можна обійти мости в Кенігсберзі (нині Калінінграді) так, щоб не побувати двічі на одному і тому самому мості, чи можна поставити 36 офіцерів з 6 різних полків так, щоб у кожній шерензі і у кожній колоні було по одному офіцеру кожного військового звання з полку, скількома способами можна розбити число на частини і т.д. Але, дивна справа, робота про мости виявилась так званим зерном, з якого потім виросли топологія і теорія графів, задача про офіцерів виявилась зараз пов’язаною з плануванням експериментів, а методи, що використовувалися при розв’язуванні задачі про розбиття чисел, після довгого та важкого шляху розвитку перетворилась в науку про інтегральні перетворення, що використовується для розв’язання рівнянь математичної фізики.
Після робіт Паскаля і Ферма, Лейбніца і Ейлера можна було вже говорити про комбінаторику, як про окрему, самостійну гілку математики, тісно пов’язану з іншими областями науки, такими, як теорія ймовірностей., вчення про ряди та ін. В кінці XVIII ст. німецький учений Гінденбург та його учні зробили спробу побудувати загальну теорію комбінаторного аналізу. Проте вона не отримала успіху – в той час ще не було накопичено достатньої кількості важливих і цікавих задач, які могли б дати необхідний фундамент для такої теорії.
В ХІХ ст. в ході досліджень по комбінаториці стали помічатися зв’язки цієї теорії з визначеннями кінцевими геометріями, групами, математичної логіки і т.д.
Шифри та анаграми
Не тільки азартні ігри спонукали математиків до комбінаторних роздумів. Ще з давніх давен дипломати, що прагнули до таємних переписів, винаходили все більш складні шифри, а секретні служби інших держав намагалися ці шифри розгадати. Одним з найпростіших шифрів була „тарабарська грамота”, в якій літери замінювались іншими за певними правилами. Проте такі шифри легко розгадувалися за характерними поєднаннями літер. Тому почали застосовувати шифри, які були основані на комбінаторних методах, наприклад, на різних перестановках літер, заміна літер з використанням ключових слів та ін.
Для кодування та розшифровки залучались математики. Ще в кінці XVI ст. розшифровкою переписів між ворогами французького короля Генріха ІІІ та іспанцями займався один із творців сучасної алгебри Франсуа Вієт. А в Англії XVIIст. монархічні заколотники дивувались швидкості, з якою Кромвель проникав у їх замисли. Монархісти вважали шифри, якими вони користувались при переписі, нерозшифрованими, і вважали, що ключі до них були видані кимсь з учасників заколоту. І лише після падіння республіки та царювання Карла ІІ вони дізналися, що всі їх шифри розгадував один з найкращих англійських математиків того часу, професор Оксфордського університету Уолліс, котрий володів винятковими комбінаторними можливостями. Він назвав себе засновником нової науки „криптографії”.
Шифрами користувались не тільки дипломати і заколотники, але й самі вчені. До XVII ст. майже не існувало наукових журналів. Вчені дізнавалися про досягнення своїх колег з книг або приватних листів. Це створювало великі труднощі при опублікуванні нових результатів – адже друкування книг займало роки, а написати про свої відкриття приватним листом було ризиковано – хтось міг присвоїти досягнення, і потім довелося б доводити, що це він не сам вигадав, а дізнався з отриманого листа. Тому часто виникали суперечки на тему переваг. Ще в кінці XVII ст. йшли довгі суперечки на тему пріоритетів між Ньютоном та Лейбніцом (про те, хто першим відкрив диференціальне та інтегральне числення), Ньютоном та Гуком (хто першим сформулював закон всесвітнього тяжіння) та ін.
А давнину Архімеду доводилося застосовувати хитрощі. Коли деякі олександрійські вчені присвоювали собі його результати, про які дізнавались з отриманих від нього листів, він писав їм ще одного листа. Лист складався з формул для обчислень об’ємів та площ різних фігур і тіл. Олександрійці знову казали, що ці формули вони давно знають і нічого нового Архімед їм не повідомив. Але тут виявлялось, що усі ці формули були невірними!
Для того, щоб забезпечити пріоритет і не допустити передчасного розголосу отриманих результатів, вчені в короткій формі формулювали суть відкриття, а потім переставляли в ній літери і відправляли листа з переставленими літерами своїм колегам. Такі тексти з переставленими літерами називаються анаграми. Наприклад слово „Москва” та „смоква” – анаграми. Коли ж друкувалась книга з детальним викладенням результатів, в ній давалася і розшифровка анаграми.
Проте не завжди анаграми дозволяли зберегти все у таємниці. Коли Гюйгенс відкрив перший супутник Сатурна та визначив його порядок обертання навколо планети, він виклав своє відкриття в анаграмі і відправив її своїм колегам. Проте вже згадуваний вище Уолліс, отримав цю анаграму, розгадав її, після чого склав свою анаграму та відправив її Гюйгенсу. Коли вчені обмінювалися розгадками анаграми, то вийшло так, немов Уолліс ще до Гюйгенса зробив те ж саме відкриття. Потім Уолліс зізнався, що пожартував із Гейгенсом, щоб довести безкорисність анаграм у справі таємності. Проте, хоча Гейгенс і сам був великим любителем і знавцем комбінаторики, він не оцінив жарту і розізлився.
Ієрогліфи та клинопис
Навички в розгадці складних шифрів допомогли ученим, коли археологи почали відкопувати камені та черепи з таємними знаками – письменністю, що замовкла декілька тисячоліть тому. Одним з найкращих успіхів у розшифровці було читання французьким філологом Жаном Франсуа Шампольним ієрогліфів, якими писали єгиптяни ще до того, як виникла наука у древніх греків.
У Шампольна були попередники – шведський археолог Д. Окерблад та англійський фізик т. Юнг, які розшифровували єгипетські тексти за допомогою комбінаторного аналізу. В їхніх руках були „білінгви” – написи, які були зроблені одночасно на єгипетській та грецькій мовах. Порівнюючи обидва тексти та помічаючи повторність груп знаків, Окерблад упізнав деякі знаки так званого демотичного письма – пізньої стадії розвитку єгипетського письма. А творець хвильової оптики Томас Юнг полюбляв відпочити від роздумів на фізичні теми і займався то каліграфією, то складанням алфавітів іноземних мов, то... танцями на слабо натягнутому канаті, - на думку Юнга все, що могла зробити одна людина, могла повторити інша. У 1814 р. він взяв з собою на канікули древньоєгипетський папірус і спробував прочитати його. Не маючи потрібної філологічної підготовки, шляхом комбінаторного він отримав цікаві результати, а потім спробував прочитати ієрогліфи. Деяких успіхів він досяг і тут, але далося в знаки недостатнє знання мов – він шукав ієрогліфи не тільки для приголосних, але й для голосних літер, а в єгипетській мові голосні опускаються. Лише Шампольну, котрий поєднав незаурядний комбінаторний дар з глибокими знаннями філології, вдалося прочитати ієрогліфи.
Складність задачі, що постала перед Шампольном, доповнювалась незнанням мови написів та змісту знаків. Проте, виділивши знаки, які на грецькій мові означали імена царів, Шампольна помітив, що деякі знаки в іменах фараонів Птоломея та Клеопатри співпадають. Так були знайдені звучання ієрогліфів, що означали літери „л” та „п” (до цього місця дійшов і Юнг). А потім Шампольн прочитав імена римських імператорів Тиберія та Трояна, давніх фараонів Рамсеса та Тутмеса – ключ до читання ієрогліфів, втрачений декілька тисячоліть тому, був знову отриманий.
Це було торжеством комбінаторного методу у читанні забутих писемностей, заснованого на спостереженні за тек