Мирон Маланюк, Василь Кравчук Метод математичної індукції та елементи комбінаторики

За редакцією Василя Тадеєва

Видання 2-е, виправлене

ТЕРНОПІЛЬ «ПІДРУЧНИКИ & ПОСІБНИКИ 2003

ББК 22.12

УДК 51.1

М 18

Рецензент:

кандидат фізико-математичних наук В. Д. Галан 

М 18	Маланюк Мирон, Кравчук Василь Метод математичної індукції та елементи комбінаторики. За редакцією В. Тадеєва. Видання 2-е, виправлене. — Тернопіль: Підручники і посібники, 2003. — 48 с. ISBN 966-07-0002-4

Посібник входить в систему дидактичних матеріалів для учнів Західноукраїнської заочної математичної школи. В ньому викладено один з основних методів доведення математичних тверджень — метод математичної індукції. На основі цього методу зроблено спробу компактно розглянути основні поняття комбінаторики. Наведено найпоширеніші методи розв’язування комбінаторних задач. Вміщено завдання для двох контрольних робіт за даною темою та добірку задач для самостійної підготовки до математичних олімпіад.

Посібник може бути корисним і для вчителів математики у гуртковій роботі.

ББК 22.12

ISBN 966-07-0002-4

© Маланюк М. П., Кравчук В. Р., 1995

Передмова редактора

«Нам такою мірою ненависний будь-який обман і шахрайство, що всім членам нашого товариства під загрозою штрафу та безчестя заборонено показувати яке б то не було природне явище прикрашеним або перебільшеним: а лише в чистому ви-гляді, без будь-якої таємничості.»

Френсіс Бекон (англійський філософ ХVП ст.), «Нова Атлантида»

Професор Отто Ліденброк — головний герой роману «Подорож до центра Землі» — належав до тієї ж когорти жульвернівських лицарів науки, істинних учених і справжніх колодязів знань, що й відоміші тепер Жак Паганель («Діти капітана Гранта»), Сайрес Сміт («Таємничий острів») та доктор Клоубоні («Подорож і пригоди капітана Гаттераса»). Найбільшою пристрастю професора після, звичайно ж, геології був пошук рідкісних книг. Одного разу йому особливо пощастило. В букіністичній крамниці він натрапив на манускрипт (рукописну книгу) ХІІІ ст., написану рунічним письмом (руни — письмові знаки (літери), що вживалися в середньовічній Ісландії і, за легендою, були винайдені самим Одіном — верховним богом в ісландській міфології). Та ще більшою несподіванкою стала записка, залишена у цій книзі її колишнім володарем — знаменитим алхіміком XVI ст. Арне Сакнуссемом. Сумніву не було, що у записці йдеться про велике відкриття. Адже запис здійснено тим самим добре відомим професору рунічним письмом, яким написана й книга. Проте прочитати записку було годі: повідомлення було зашифроване. «Я вважаю безсумнівним, — сказав професор своєму племінникуі помічнику Акселю, — що спочатку відповідна фраза була написана правильно, а потім за якимсь правилом, яке треба знайти, спотворена».

Допомогла випадковість. Обмахуючись спересердя після чергової невдалої спроби аркушем паперу з переведеними на латину записами букв шифрування, Аксель помітив, що читати його слід просто в зворотному напрямку. Арне Сакнуссем повідомляв про свою подорож … до центра Землі через кратер вулкану Снайфельдс в Ісландії, причому через ту з його шахт, до якої в кінці липня сягає тінь від піку Скартарис. Ця вказівка, за Жуль Верном, і дала змогу професору та його помічникам повторити незвичайну подорож великого алхіміка до земних глибин.

Прочитавши, завдячуючи такій випадковості, документ, Аксель з хвилюванням спостерігав за професором, який, охолонувши, знову взявся за роботу і за всяку ціну намагався прочитати шифрування. «Я добре знав, — згадував він потім, — що якби професору вдалося скласти з усіх цих букв усі можливі буквосполучення, то шукана фраза врешті-решт вийшла б. Але я знав також, що з двадцяти букв отримується два квінтильйони, чотириста тридцять два квадрильйони, дев’ятсот два трильйони, вісім мільярдів, сто сімдесят шість мільйонів, шістсот сорок тисяч буквосполучень. А в цьому записі було сто тридцять дві букви, і ці сто тридцять дві букви могли утворити такунеймовірну кількість словосполучень, що не тільки полічити їх було б неможливо, а й уявити собі. Я міг заспокоїтися щодо цього героїчного способу вирішити проблему».

По-справжньому оцінити цей епізод з жюльвернівського роману в змозі лише той, хто знайомий з комбінаторикою — математичною наукою про способи підрахунку числа різноманітних комбінацій з елементів деякої скінченної множини (назва походить від латинського слова «соmbinа», що означає «сполучати», «зв’язувати»). Їй i присвячена більша частина цієї брошури.

Шифрування і дешифрування текстів — одне з першоджерел комбінаторики, а також і сфера її застосувань. Найбільш вражаючі результати від цих застосувань пов’язані з розшифровуванням прадавніх історичних писемних пам’яток, зокрема — ієрогліфічних єгипетських папірусів та клинописних вавилонських табличок. Унаслідок філологічного та комбінаторного аналізу так званих «білінгвів» — паралельних записів різними давніми мовами, наприклад, давньогрецькою і давньоєгипетською — у ХІХ–ХХ ст. «заговорили» прадавні письмена, яких не могли прочитати вже навіть давні греки в епоху розквіту їхньої культури.

З комбінаторикою пов’язані і теперішні задачі цифрованого кодування інформації, наприклад, при створені державних номерних знаків для транспортних засобів, шифрованих товарних знаків тощо. До здійснення цілеспрямованого перебору різних можливих варіантів призводять численні задачі виробничої діяльності, наприклад, прокладання маршрутів, проектування комунікацій, складання розкладу руху транспорту, графіків подачі ресурсів, розкладів занять у навчальних закладах тощо.

Нарешті, джерелом комбінаторики та чи не найширшою тепер сферою її застосувань є теорія ймовірностей.

Усім добре відомо, що різні випадкові події випадкові, образно кажучи, по-різному. Наявність кожного конкретного звука у слові випадкова. Проте одні звуки у мові трапляються частіше, інші — рідше (зокрема, це мають на увазі, коли кажуть про ритмічність мови, про її благозвучність, мелодійність тощо). Отже, ймовірність одних звуків більша, ймовірність інших — менша. Інший приклад. Виграш у кожній лотереї — випадковий. Але в одній лотереї (наприклад, у книжковій) він трапляється значно частіше, отже, ймовірніший, ніж в іншій (наприклад, у спортлото). Щоправда довший час такими речами цікавилися здебільшого тільки запеклі гравці в азартні ігри. І тільки в XX ст., коли було відкрито імовірнісний характер багатьох фундаментальних явищ природи (зокрема, на рівні елементарних частинок), необхідність вивчення міри випадковості, тобто ймовірності різних випадкових подій, стала очевидною.

Початки теорії ймовірностей були закладені у XVII ст., коли декількох найвидатніших математиків того часу спровокували до аналізу азартних ігор, зокрема — гри у кості. Як відомо, ця гра полягає в тому, що декілька однакових кубиків з нанесеними на їхніх гранях очками від 1 до 6 по черзі кидаються на стіл кількома гравцями. У найпростішому варіанті гри ставку бере той, кому випала найбільша сумарна кількість очок. Однак при цьому ймовірність виграшу в кожного учасника однакова. Через те найверткіші пройдисвіти, «удосконалюючи» гру, запроваджували такі правила, які на перший погляд були гіршими для них, проте насправді забезпечували їм більшу вірогідність виграшу. Славою великого вигадника таких правил ко-ристувався свого часу якийсь Мере. Одне з його «удосконалень», погоджене із самим Блезом Паскалем, було таким: щоразу кидаються чотири кісточки, а виграш бере Мерелише в тому разі, коли хоча б на одній з кісточок випаде шістка. Таке «невинне» удосконалення призвело до того, що Мере частіше вигравав, ніж програвав. Прочитавши цю брошуру, читач зрозуміє, в чому причина. А вона полягає в тому, що при киданні чотирьох кісточок усього можливо 6 · 6 · 6 · 6  1296 різних варіантів випадання очок. Шістка жодного разу не з’явиться у 5 · 5 · 5 · 5625 випадках, а отже, з’явиться хоча б один раз у 6⁴– 5⁴671 випадку. Таким чином, ймовірністьтого, що шістка з’явиться хоча б один раз, більша за ймовірністьтого, що вона не з’явиться жодного разу. Різниця незначна. Але при багаторазових сеансах гри вона може забезпечити значний виграш.

В загальному випадку якщо стан якогось об’єкта чи системи може характеризуватися одним зп однаково можливих характерних станів визначальних елементів, а деякій випадковій подіїА, пов’язаній з цим об'єктом, сприяєт () із цих станів, то кажуть, що ймовірність подіїА дорівнює.

Як бачимо, підрахунок імовірностей безпосередньо пов’язаний з підрахунком кількості комбінацій, а отже, з відповідною комбінаторною проблематикою. У цій брошурі, однак, глибше ці зв’язки не простежуються. Але читач, який ґрунтовно ознайомиться з наведеним тут матеріалом, без особливих зусиль зможе розв’язувати і ймовірнісні задачі, наприклад, визначати шанси виграшу у лотерею Спортлото (і після цього перестати грати в такі ігри).

Своїй назві комбінаторика завдячує видатному вченому, математику та філософу Ґотфріду Вільгельму Лейбніцу. У 1646 р. у двадцятирічному віці він опублікував твір під назвою «Dissertatio de art combinatoria» (що в перекладі з латини означає «Міркування про комбінаторне мистецтво»), в якому заклав основи цієї теорії.

Чи не найсуттєвішою проблемою при ознайомленні з комбінаторикою є чітке розмежування основних понять і символів для їх позначення. Звикнутись із символами буде простіше, якщо зважити, що вони безпосередньо пов’язані з англійськими назвами відповідних термінів: С— від «Combination» («комбінація»),Р— від «Permutation» («перестановка»),А — від «Arrangement» («розміщення»).

Основні факти комбінаторики виражаються у вигляді формул для обчислення кількості певним чином утворених підмножин з елементів деякої скінченної множини — перестановок, комбінацій, розміщень тощо. Універсальним методом для доведення цих формул, який застосовують і в інших розділах математики — всюди, де тільки виникає потреба доведення тверджень, що залежать від натурального параметра, — є так званий метод математичної індукції. У неявній формі цей метод застосовувався ще античними математиками, зокрема Евклідом. Проте систематичне і явне застосування даного методу розпочалося у XVII ст. Зокрема, ним широко користувався Блез Паскаль у своїй праці з комбінаторики. Сам термін «математична індукція» вперше з’явився у 1838 р. в Британській Енциклопедії (відповідну статтю про цей метод написав відомий шотландський математик, перший президент Лондонського математичного товариства Августус де Морган (1806 – 1871).

Зрозуміти глибинну суть методу математичної індукції читачу допоможе наступне порівняння (математики кажуть, — аналогія). Вам відомий спосіб задання числових послідовностей за допомогою так званих рекурентних формул («recurro» в перекладі з латини означає «біжу назад», «повертаюсь»), за якими n-йчлен послідовності виражається через попередні, а в найпростішому випадку — лише через один (п – 1)-й член. Такими є, наприклад, наступні формули для членів арифметичної та геометричної прогресій, що безпосередньо випливають з означень цих послідовностей:;(туті— відповідно, різниця арифметичної та знаменник геометричної прогресій). Отже, знаючи перший член а₁прогресії, наприклад арифметичної, ми за рекурентною формулою можемо спочатку обчислити другий її членпотім третійa₃a₂+ d, і так далі, нарешті, обчисливши (п – 1)-йчлен, знайтиn-йчлен прогресії.

Методом математичної індукції по суті встановлюється рекурентна фор­ма для доведення (induktio — дослівно «наведення», — також вказує на це). Адже при доведенні цим методом твердження, залежного від натурального параметраn, по-перше, встановлюється істинність цього твердження прип1 (аналог першого членау рекурентній формулі для задання послідовності). Це так званабаза індукції. Потім, припустивши, що твердження доведене при(аналог членау рекурентній формулі —припу-щення індукції), показують, що воно буде істинним і при(цекрокіндукції і, власне, аналог самої рекурентної формули для послідовності). Тоді твердження буде доведеним для всіхп. Справді, розпочинаючи з твердження придоведеного як базового для індукції, ми, як при обчисленні на-ступних членів прогресії за рекурентною формулою, матимемо, згідно з проведеним кроком індукції, істинність даного твердження прип1 + 12,потім — прип2 + 13, і так далі, тобто — при всіхn.

На завершення зазначимо, що свого часу елементи комбінаторики та метод математичної індукції входили до програми з математики для середньої школи. І лише у зв’язку із скороченням часу на вивчення математики ці теми були перенесені на факультативи та на самостійне опрацювання. Але тепер вони знову вводяться до шкільного викладання. Отже, цей матеріал цілком доступний для учнів. Тим більше для тих, хто додатково цікавиться математикою.

У посібнику використовуються такі умовні позначення:

початок і кінець розв’язання задачі та доведення теореми відзнача-ється значком ■;

запис означає, що ціле числоа ділиться на ціле числоb(без остачі);

при символомпозначається добутокусіх натуральних чисел від 1 доn. Вважається, також, що

В. О. Тадеєв