13 травня о 18:00Вебінар: Як навчати майбутніх програмістів: практичні кейси для уроків інформатики

МЕТОД ТРАЄКТОРІЙ У ЗАДАЧАХ КОМБІНАТОРИКИ

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

МЕТОД ТРАЄКТОРІЙ У ЗАДАЧАХ КОМБІНАТОРИКИ

Гульман Олександр Володимирович,

вчитель математики,

спеціаліст вищої категорії,

ДПТНЗ  Криворізький центр професійної

освіти робітничих кадрів торгівлі

 та ресторанного сервісу

 ВСТУП

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

Комбінаторні задачі розв’язуються за допомогою використання стандартних комбінаторних схем – комбінацій, перестановок, вибірок. Залежно від того, впорядкована структура є моделлю задачі, чи не впорядкована і допускає ця структура повторення чи ні, використовується та чи інша формула. Проте є досить складні задачі, що не розв’язуються лише застосуванням стандартних формул, і потребують більш глибокого дослідження, спеціальних методів. Найбільш поширеними методами розв’язування комбінаторних задач є методи рекурентних співвідношень, метод твірних (продуктивних) функцій, метод траєкторій. Якщо перші з двох названих методів оперують спеціальними поняттями, що не входять до шкільного курсу математики, то метод траєкторій виділяється простотою і можливістю розв’язувати широке коло задач не тільки комбінаторики, але й суміжних розділів математики – теорії ймовірностей, математичної статистики, теорії випадкових процесів.

Об’єктом дослідження роботи є метод траєкторій, а предметом дослідження – задачі комбінаторики і теорії ймовірностей.

Мета дослідження – застосувати метод траєкторій до розв’язування задач комбінаторики і теорії ймовірностей.

Відповідно до мети були поставленні такі завдання:

1) проаналізувати наукову, популярну літературу та джерела Інтернет з питання використання методу траєкторій;

2) навести задачі із комбінаторики і теорії ймовірностей, де застосовується метод траєкторій;

3) застосувати метод траєкторій до деяких задач теорії ймовірностей та проаналізувати можливості застосування методу в інших ситуаціях.

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

розділ 1

осНОВНІ ТЕОРЕТИЧНІ ПОНЯТТЯ

1.1. Геометрична ілюстрація біномних коефіцієнтів

Одним із ефективних методів розв’язування задач комбінаторики і теорії ймовірностей є так званий метод траєкторій. Вивченню цього методу передує геометрична ілюстрація біномних коефіцієнтів. Термін «метод траєкторій» увів академік Б. В. Гнєденко у 1951 році і використав зі своїми учнями для розв'язування задач математичної статистики. Розглянемо координатну сітку на площині і поставимо питання: скільки існує найкоротших шляхів, що з'єднують початок координат з точкою (n, k)?

                  

Рис. 1.1. Найкоротша ламана, що з'єднує початок координат з точкою (n, k).

Очевидно, що найкоротший шлях має проходити так, щоб містити ланки, що йдуть вправо або вгору. Для побудови кожного такого шляху необхідно вибрати місця для n горизонтальних ланок (а вертикальні ланки визначаться однозначно), або вказати місця k вертикальних ланок, а горизонтальними сполучити однозначно нанесені вертикальні. Оскільки довжина будь-якої найкоротшої ламаної складається із n + k ланок, то кількість таких ламаних дорівнює кількості варіантів вибору із n + k  елементної множини невпорядкованої n  елементної (або k  елементної). Як відомо з комбінаторики, це число дорівнює числу (або , звідки дістаємо комбінаторну тотожність ). Отже, маємо геометричну інтерпретацію біномних коефіцієнтів. Просте твердження, яке тепер можна сформулювати так: число найкоротших шляхів, що проходять координатною сіткою і сполучають точки (0, 0) і (n, k), дорівнює.

Оскільки кожна найкоротша траєкторія, що сполучає (0, 0) і (n, k), має обов’язково пройти або через точку A(n  1, k) (Рис. 1.1., правий), а таких траєкторій всього , або через точку B(n, k  1), а таких траєкторій , то маємо комбінаторну тотожність .

Отже, траєкторним способом доведено відому комбінаторну тотожність, про яку йтиметься в пункті 1.3.

1.2. Траєкторії комбінацій з повтореннями та вибірок

Як було описано в попередньому пункті, геометрична інтерпретація біномних коефіцієнтів полягає в тому, що кожній підмножині (комбінації) множини {a1, a2,…, an+k} ставиться у відповідність траєкторія – найкоротша ламана, що сполучає початок координат з точкою (n, k). Поставимо кожній комбінації (а отже і траєкторії) набір вигляду 100101…1 довжини n + k, де наявність елемента al позначається одиницею на l  му місці, а відсутність – нулем. Записаній послідовності відповідатиме підмножина {a1, a4, a6,…, an+k}. А кожній послідовності ставиться у відповідність ламана (траєкторія), що з’єднує точки (0, 0) і (n, k), ідучи вгору (1) або вправо (0). Ламана лінія має іти найкоротшим шляхом.

У самій геометричній інтерпретації проста заміна шкали по осі Ox із 0, 1, 2,…, n на a1, a2,…, an + 1 дає можливість отримати рівність , тобто подати також геометричну інтерпретацію комбінаціям з повтореннями. Так, на рисунку 1.2 зліва траєкторія відповідає підмножині a1, a2, a5, a6,…, ak  2. На рисунку 1.2. справа траєкторія відповідає комбінації з повтореннями a1, a1, ,…, a1. (Наявність елемента – вертикальна риска траєкторії, відсутність – горизонтальна).

            

Рис. 1.2. Траєкторії комбінацій без повторень і з повтореннями

Траєкторія, що ілюструє біномні коефіцієнти, має бути найкоротшою. Якщо відмовитись від вимоги, щоб ламана йшла найкоротшим шляхом, а «дозволити» також йти донизу (але вліво по Ox забороняється), не виходячи за межі прямокутника (розміру n(q-1)), то матимемо геометричну ілюстрацію для вибірок з повтореннями.

Рис. 1.3. Траєкторія вибірки з повтореннями.

Дійсно,кожній ламаній, що має вигляд стовпчикової діаграми (рис. 1.3), поставимо у відповідність n-значне число в системі числення з основою q так, що висота s-го стовпчика дорівнює цифрі, яка стоїть на s-му місці в запису числа. Ламаній на рис. 1.4 відповідає число (120…(q-1)0…01)q. Кількість таких чисел (кожне число є впорядкованою множиною, утвореною вибором n цифр із q, з повтореннями), а отже і ламаних, що з’єднують точку (0, 0) із точкою (n, q  1), дорівнює . Остання геометрична інтерпретація надає можливість розв’язати таку задачу.

Задача 1. [1, задача 30]. У деякій країні не було двох мешканців з однаковим набором зубів. Якою найбільшою може бути кількість мешканців цієї країни (найбільше може бути 32 зуби)?

Розв’язання. Перший спосіб. Можна побудувати впорядковану структуру – послідовність довжини 32 вигляду 111001…101, де наявність зуба відповідає одиниці, відсутність – нулю. Очевидно, що повторення мають місце (вибираємо k = 32 елементи із n = 2 елементів 0 і 1), і в знаходимо необхідну формулу , отримуючи відповідь .

Другий спосіб. Використаємо невпорядковану без повторень множину вигляду {1, 3,…, 32}, де наявність числа відповідає наявності зуба – порядок розташування номерів не має значення. Для побудови множини такого вигляду 33 рази вибираємо із n = 32 елементів k = 0, 1, 2,…, 32 елементи, підраховуючи кількість 0-зубих, 1-зубих,…, 32-зубих. Тому кількість мешканців дорівнює кількості всіх підмножин 32-елементної множини {1, 2,…, 32}. Маємо: .

Траєкторний спосіб розв’язання.

Поставимо у відповідність кожному мешканцю країни ламану, що з’єднує точки (0, 0) і (32, 1). На рисунку зображено ламані, що відповідають наборам зубів 0, 32 і 16 (через один).

Тут q = 2, n = 32, отже кількість траєкторій і кількість мешканців країни складає .

 

1.3. Доведення комбінаторних тотожностей методом траєкторій

Розглядаючи відомий трикутник Паскаля (Рис. 1.4.), нескладно помітити, що k-м елементом n-го рядка є коефіцієнт у розкладанні двочлена (a + b)n за відомою формулою бінома Ньютона: .

Рис. 1.4. Трикутник Паскаля.

Коефіцієнти , які називають біномними коефіцієнтами мають багато цікавих і корисних властивостей. Деякі з них називають комбінаторними тотожностями. Запишемо дві з них: ; .

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

Доведемо таку тотожність:

.

Розглянемо всі траєкторії, що йдуть в точку A(k + 1, n-k). Таких траєкторій всього існує . Поділимо їх на декілька класів: траєкторії, що проходять через точку A1, що проходять через точку A2, …, траєкторії, що проходять через точку An-k. Оскільки траєкторія може йти лише вправо і вгору, то інших траєкторій, відмінних від перерахованих, немає. Підрахуємо кількість названих траєкторій. Траєкторій, що з’єднують точку O(0, 0) із точкою A1(k, 0) всього існує ; тих, що з’єднують точку O(0, 0) із точкою A2(k, 1) – , з’єднують точку O(0, 0) із точкою A3(k, 2) – , …, із точкою An-k(k, n-k) – . Вважатимемо також, що із точки A1 у точку A ламана може іти лише вправо і вгору, тобто одним єдиним шляхом. Ламана, що із точки A1 піде в точку A2, потрапляє до іншого класу. Таким чином підрахуємо всі можливі траєкторії, що входять до точки A. За правилом суми (кожен доданок відповідає своєму класу) та добутку маємо кількість можливих ламаних: , або, що й треба було довести.

РОЗДІЛ 2

РОЗВЯЗУВАННЯ ЗАДАЧ ІЗ ВИКОРИСТАННЯМ Методу
траєкторій

2. 1. Задачі з комбінаторики

Розглянемо задачі з комбінаторики, де можна використати метод траєкторій. У багатьох задачах розв’язання іншими методами або неможливе, або пов’язане з певними труднощами.

Задача 2. Біля театральної каси зібралась черга з m + n осіб, причому n із них мають лише по одній банкноті вартістю 50 грн, а інші m – по одній банкноті вартістю 100 грн, m  n. Скільки існує способів такого розташування покупців в черзі до каси, при яких жодному покупцеві не доведеться чекати решту, якщо на початку в касі грошей немає? Яка ймовірність того, що покупцеві не доведеться чекати решти біля каси?

Розв'язання. Нехай покупці розташувалися до каси певним чином. Розглянемо величини si = 1, якщо i –й покупець має 50 грн, і si = -1, якщо i –й покупець має 100 грн. Розглянемо суму Sk = s1 + s2 + s3 +  + sk. Очевидно, що Sk – це різниця між кількістю банкнот у 50 грн та кількістю банкнот у 100 грн серед перших k покупців у черзі. Для того, щоб жоден покупець не чекав здачу, записана сума має бути невід’ємною. Розглянемо систему координат на площині, і побудуємо точки Ak = (k, Sk), k = 1, 2, 3,…, m + n. Ламана (траєкторія), що з’єднує точки O(0, 0) Am + n = (n + m, n  m), проходячи через точки A1, A2, …, Am + n  1, містить m + n відрізків, n з яких піднімається вгору, а m опускається донизу.

Кількість таких траєкторій підрахуємо, вказавши номери тих n відрізків (із n + m), що піднімаються вгору. Це число дорівнює числу комбінацій .

Траєкторії, що відповідають тим способам розташування покупців у черзі, при якому жоден не буде очікувати решти, не має спільних точок із прямою y =  1; Sk  0, як зазначалося вище. Знайдемо число траєкторій, що мають спільну точку із прямою y =  1. Кожній такій траєкторії T поставимо у відповідність її відбиття T відносно названої прямої за таким правилом: до першої точки дотику з прямою

Рис. 2.1. Дзеркальне відображення траєкторії.

y =  1 траєкторія T збігається з T, а далі T є симетричним образом T відносно прямої y =  1 (Рис. 2.1.). Всі траєкторії T закінчуються в точці
Am + n = (n + m, n  m  2), яка є симетричним образом точки Am + n = (n + m, n  m) відносно розглядуваної прямої. Встановлена відповідність є взаємно однозначною. Тому шукане число траєкторій дорівнює числу ламаних, які сполучають O і Am + n. Підрахуємо це число. Нехай ламана складається із x відрізків, що йдуть вгору та y відрізків, що йдуть донизу. Тоді x + y = m + n, а y  x = n  m + 2 (траєкторія має закінчитися саме у точці Am + n). Число траєкторій з O в Am + n дорівнює , Число траєкторій, що не перетинають пряму y =  1, дорівнює . Отже, відповіддю до задачі є . Якщо ставити питання про ймовірність того, що покупцеві не доведеться чекати решти, то така ймовірність дорівнює .

При розв’язуванні задач із використанням дзеркального відображення траєкторії корисними є такі твердження.

Теорема 1. Нехай Nx,y – число траєкторій, що сполучають точку O із точкою (x, y). Тоді,

,

якщо x і y мають однакову парність, і Nx,y = 0, то парність чисел x і y різна.

Теорема 2. (Принцип дзеркального відображення). Нехай A = (a, ) і B = (b, ) – точки з цілочисловими координатами, і виконуються нерівності b > a  0,  > 0,  > 0. а A1 = (a   ) – точка, симетрична до точки A відносно осі Ox. Тоді число тих траєкторій з A до B, що дотикаються до осі Ox або перетинають її, дорівнює числу траєкторій з A1 до B. 

,

Теорема 3. Нехай x > 0 і y > 0. Тоді число траєкторій від точки O до точки (x, y), які не мають вершин на осі Ox (за винятком початку координат), дорівнює.

Теорема 4. Серед траєкторій, які сполучають точку O з точкою (2n, 0), існує:

a) рівно L2n  2 траєкторій, які лежать вище осі Ox і не мають спільних точок з Ox крім (0, 0) і (2n, 0);

b) рівно L2n траєкторій, які не мають вершин нижче осі Ox.

Тут використано позначення .

Задача 3. Довести комбінаторні тотожності

1) ;

2) .

Розв'язання.

1) Кожна із траєкторій, що з’єднують точки O(0, 0) і A(n, m), а таких траєкторій згідно з пунктом 1.1. існує , обов’язково пройде через одну із точок A1(k, 0), A2(k, 1),…, An + 1(k, n) (Рис. 2.2., зліва). Траєкторій, зо з’єднують O(0, 0) і As(k, s) всього існує(s = 1, 2, 3,…, n + 1), а траєкторій, що сполучають As(k, s) із точкою A(n, m) всього . Отже, застосувавши правила суми та добутку, дістанемо таку комбінаторну тотожність: , саме її і треба було довести. Зауважимо, що будь-якими іншими методами ця тотожність доводиться дещо складніше.

Рис. 2.2. Доведення комбінаторних тотожностей.

2) Число траєкторій із точки O(0, 0) в точку A(n, n) дорівнює . Будь-яка із траєкторій має пройти через одну і тільки одну із точок (Рис. 2.2., справа) A1(n, 0), A2(n  1, 1), A3(n  2, 2), …, An(1, n  1), An + 1(0, n), що належать діагоналі квадрата. Число траєкторій із точки O(0, 0) в точку Ak(n  k + 1, k  1), k = 0, 1, …, n + 1, дорівнює , а траєкторій із Ak(n  k + 1, k  1) в A(n, n) – , отже, за правилом добутку число траєкторій із точки O(0, 0) в точку A(n, n), що проходять через точку Ak, складає . За правилом суми матимемо: .

2. 2. Задачі з теорії ймовірностей

Задача 4. (Бертрана про балотування, [4, № 4.29]). Кандидат A набрав на виборах a голосів, а кандидат Bb голосів (a > b). Виборці голосували послідовно. Яка ймовірність того, що при голосуванні кандидат A був завжди попереду від B за кількістю поданих за нього голосів?

Розв’язання.  Нехай si = 1, якщо i –й голос подано за A, si = -1, якщо i –й голос подано за B. Розглянемо суму Sk = s1 + s2 + s3 +  + sk. Очевидно, що Sk – це різниця між кількістю голосів, поданих за кандидатів, і за умовою задачі Sa + b = a  b. Побудуємо в системі координат Oxy ламану, що сполучає точки O(0, 0), (1, S1), …, (a + b, Sa + b). Кожному способу розподілу голосів між кандидатами відповідає своя ламана (траєкторія), яка сполучає точки O(0, 0) і (a + b, a  b). Загальне число траєкторій складає . Траєкторія складається із a + b відрізків, причому a з них ідуть вгору. Кандидат А буде завжди попереду від В, якщо відповідна траєкторія проходить через точку (1, 1) (перший виборець проголосував за А) і не перетинає вісь Ox. Число таких траєкторій дорівнює .

 

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

1. Виленкин Н. Я. Комбинаторика / Н. Я. Виленкин. – М. : Наука, 1969. – 328 с.

2. Ерусалимский Я. М. 2- и 3-пути на графе-решетке и комбинаторные тождества / Я. М. Ерусалимский // Известия вузов. Северо-Кавказский регион. Естественные науки. –2017. – № 1. – С. 25-30.

3. Капітонова Ю. В. Основи дискретної математики / Ю. В. Капiтонова, С. Л. Кривий, О. А. Летичевський, Г. М. Луцький, М. К. Печурiн. – К. : Наукова думка. – 2002. – 579с.

4. Теорія ймовірностей. Збірник задач / А. Я. Дороговцев, Д. С. Сильвестров, А. В. Скороход, М. Й. Ядренко. – К. : “Вища школа”, 1976. – 384 с.

5. Элементы комбинаторики / И. И. Ежов, А. В. Скороход, М. И. Ядренко.  М. : Наука, 1977. – 80 с.

6. Яглом А. М. Неэлементарные задачи в элементарном изложении / А. М. Яглом, И. М. Яглом. – М. : Гостехиздат, 1954. – 544 с.

7. http://moodle.ipo.kpi.ua/moodle/file.php/646/discretka_L_08.pdf

 

Задача [Бондаренко,  61, стор. 462]. Дві команди А і В грають серію матчів у баскетбол доти, поки одна з них не одержить чотири перемоги (нічиїх немає). Скільки різних серій таких матчів може бути.

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

Рис. 1. Траєкторія до задачі про гру команд.

Очевидно, що довжина будь-якої траекторії не перевищить 7. Жодна з них не досягне точки А (4; 4) – гра закінчиться, коли траєкторія вперше досягне або прямої x = 4, або прямої y = 4, тобто у будь-якій із точок Ai або Bi, i = 1, 2, 3, 4 (рис. 13 a). Враховуючи те, що кожну із траєкторій можна єдиним способом продовжити у точку А (4; 4), робимо висновок, що можливих траєкторій стільки ж, скільки тих, що входять у згадану точку, тобто .

Розглянемо геометричну ілюстрацію до комбінаторної тотожності також доведеної теоретико-множинними міркуваннями [Виленкин, стор.58]. Підрахуємо кількість траєкторій, зображених на рисунку 5.

        

Рис. 5.

Згідно із геометричною інтерпретацією біномних коефіцієнтів, через точки Ak  1 і Ak пройде траєкторій (Рис. 1). Тут , k = 1, 2, …, q; q  1 – ціле число; A0 = O(0; 0), Aq(m; n  m). За правилом добутку траєкторій, що проходять через точки A0, A1, …, Aq, існує . Якщо підрахувати кількість траєкторій за всіма можливими точками, координати яких задовольняють рівнянню m1 + m2 +  + mq = m, то за правилом добутку їх виявиться . З іншого боку, траєкторій, що сполучають O(0; 0) і A(m; n  m), існує . Прирівнявши отримані результати, дістанемо комбінаторну тотожність

.

1. Бондаренко М.Ф. Комп’ютерна дискретна математика / М. Ф. Бондаренко, Н. В. Білоус, А. Г Руткас. – Х. : «Компанія СМІТ», 2004. – 480 с.

2. Виленкин Н. Я. Комбинаторика / Н. Я. Виленкин. – М.: Наука. Гл. ред. физ.-мат. лит., 1969. – 328 с.

 

 

 

doc
Пов’язані теми
Алгебра, 11 клас, Інші матеріали
Інкл
До підручника
Алгебра (академічний, профільний рівень) 11 клас (Нелін Є.П., Долгова О.Є.)
До уроку
22.4. Геометричне означення ймовірності
Додано
20 січня
Переглядів
111
Оцінка розробки
Відгуки відсутні
Безкоштовний сертифікат
про публікацію авторської розробки
Щоб отримати, додайте розробку

Додати розробку