Комбінаторні задачі математичних олімпіад

     Примітка. Твердження задачі неважко узагальнити. Припустимо, що в залі знаходяться n чоловік, кожний із яких знайомий покрайній мірі з присутніх. Тоді може бути випадок, коли двоє із будь яких 4 чоловік, які знаходяться в залі, не будуть знайомі один з одним. Доказ цього твердження проводиться так як  доказ твердження задачі.

         

     ЗАДАЧА 106

     Нехай Z – множина людей, які знаходяться в залі.

     Наші  роздуми дуже спрощуються, якщо ми домовимося вважати, що кожен з тих, хто знаходиться  залі, знайомий сам з собою. Така домовленість не змінює твердження задачі, яке необхідно довести. Прийнявши його, ми можемо вважати, що кожний X Z не знайомий не більш ніж з 32 членами множини Z.

       Нехай A – довільно вибраний член множини Z. Якщо всі, хто не знайомий з A, залишать зал,то множина , які залишилися в залі буде нараховувати не менше 100-32 = 68 чоловік. Нехай B – будь-який з тих, хто належить множині ,але не A. Якщо зараз зал залишить всі, хто не знайомий з B, то всі які залишилися в залі творять множину , в якій нараховується не менше 68-32=36 чоловік. Нехай C – хто-небудь з тих, хто входить  множину , але не A і не B. Після того як зал залишать ті, хто включений в множну , але не знайомий з C, всі які залишилися в залі утворюють множину , в якій нараховується не менше 36-32 чоловік. З цього слідує, що в входить хоч одна людина окрім A, B, C. Якщо ми позначимо його D, то A, B, C і D утворюють четвірку людей знайомих один з одним, так як B знайомий з A, C знайомий з A і B, а D знайомий з A, B і C. 

     Примітка. Справедливе також більш загальне твердження: якщо в залі знаходиться n людей, кожен з який знайомий хоча з []+1 із інших присутніх, то в залі знайдуться 4 таких людини, кожен із яких знає трьох інших.

     Доведення його аналогічне наведеному вище. 

     ЗАДАЧА 110

     Пронумеруємо сидячих за столом послідовними натуральними числами від 1 до n(n).  Припустимо, що номер 1 за столом сидить поруч з номером n і 2, номер 2 – пору з номером 1 і 3 і т.д., нарешті, номер n сидить поруч з номером n-1 і 1. Коротко про таке розподілення чисел 1, 2, …, n говорять, що вони утворюють цикл

     1, 2, …, n.                                                      (1)

     Нехай n – не парне число. Утворюємо із чисел від 1 до n цикл

     1, 3, …, n , 2, 4, …, n-1 ,                                                    (2)

в якому  за послідовними не парними числами  ідуть послідовні парні числа. Не важко побачити, що в циклі (2) кожне число має інших сусідів, ніж в циклі (1). Розрізнюючи в розподілу чисел, які утворюють цикли (1) і (2), зводяться до наступного:

1. Кожне непарне  число, окрім 1 і n, межує в циклі (1) з парними числами, а в циклі (2) – з не парними;
2. Кожне парне число, окрім чисел 2 і n-1, межує в циклі (1) з непарними числами, а в циклі (2) – з парними;
3. Число 1 в циклі (1)  межує з числами n і 2, в циклі (2) – з числами n-1 і 3, які відрізняються від чисел n і 2 при n.

     Числа 2, n-1, n в циклі (1) межують з числами 1 і 3, n-2 і n, n-1 і1 , а в циклі (2) – з числами n і 4, n-3 і 1, n-2 і 2.

     Припустимо  далі, що n – парне число; утворимо із чисел від 1 до n цикл

     1, 3, …, n-1, 2, …, n-2, n,

в якому  як і в циклі (2), за послідовними непарними числами йдуть послідовні парні числа, і переставити в ньому числа n-2 і n:

     1, 3, …, n-1, 2, 4, …, n-4, n, n-2.                         (3)

     Розподілення  чисел в циклі (3) має наступні особливості:

1. Кожне із непарних чисел 3, 5, …, n-3 межує з непарними числами;
2. Кожне із чотирьох чисел 4, 6, …, n-4 межує із парними числами;
3. Числа 1, 2, n-1, n-2 межують з числами 3 і n-2, n-1 і 4, n-3 і 2, n і 1.

     Неважко побачити, що у кожного числа в  циклі (3) сусіди інші, ніж в циклі (1). Тим самим твердження задачі доведено. 
 
 

     Придбання тістечок.

     В кондитерському магазині продавалося 4 види тістечок: наполеони, еклери, пісочні  і слойоні. Скількома способами  можна купити 7 тістечок?

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

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

     Щоб розв’язати нашу задачу будемо діяти  так. Зашифруємо кожне придбання  за допомогою  нулів та одиниць. Саме, на початку напишемо стільки одиниць, скільки придбано наполеонів. Потім, щоб відділити наполеонів від  еклерів, напишемо нуль, а потім –  стільки одиниць, скільки придбано еклерів. Далі знову напишемо нуль (якщо не було придбано жодного еклеру, то в записі з’являться два послідовних  нулі ). Надалі напишемо стільки одиниць, скільки куплено пісочних тістечок, знову напишемо нуль, і нарешті, напишемо стільки одиниць, скільки куплено  слойоних тістечок. Наприклад, якщо куплено  три наполеони, один еклер, два пісочних тістечка і одне слойоне, то отримаємо  такий запис: 1110101101. Якщо ж куплено  два наполеони і два пісочних, то отримаємо запис: 1100111110. зрозуміло, що різним покупкам відповідають при  цьому різні комбінації з 7 одиниць  і 3 нулів. І навпаки, кожній комбінації з 7 одиниць і 3 нулів відповідає якесь  придбання. Наприклад, комбінації 0111011110 відповідає придбання 3 еклерів і 4 пісочних тістечок.

     Таким чином, число різних покупок рівне  числу розміщень з повтореннями, які можна скласти з 7 одиниць  і 3 нулів. А це число рівне:

     P(7, 3) = = = 120.

     До  того ж самого результату можна було б прийти і іншим шляхом. А саме, розмістимо в кожному придбанні  тістечка в такому порядку:до  наполеони, еклери, пісочні і слойоні, а потім  перенумеруємо їх. Але при нумерації  будемо до номерів еклерів додавати 1, до номерів пісочних – 2 і до номерів  слойоних – 3 (а до номерів наполеонів нічого не будемо додавати). Наприклад, нехай куплено 2 наполеони, 3 еклери, 1 пісочне і 1 слойоне тістечко. Тоді ці тістечка нумеруються так: 1, 2, 4, 5, 6, 8, 10. Зрозуміло, що найбільший номер  при цьому дорівнює 10 (останнє  слойоне тістечко отримує номер 7+3=10), а найменший номер рівний 1 (цей номер отримує перший наполеон). При цьому жоден номер не повторюється. І навпаки, кожній зростаючій послідовності  з 7 чисел від 1 до 10 відповідає деяке  придбання. Наприклад, послідовність 2, 3, 4, 5, 7, 8, 9, відповідає придбанню з 4 еклерів і 3 пісочних тістечок. Щоб  впевнитись в цьому, потрібно відняти  від заданих номерів числа 1, 2, 3, 4, 5, 6, 7. Ми отримаємо числа 1, 1, 1, 1, 2, 2, 2, тобто 4 одиниці і 3 двійки. Але 1 ми додавали  до номерів еклерів, а 2 – до номерів пісочних тістечок; отже, у нас 4еклери і 3 пісочних тістечка.

     При цьому в нас виходять лише зростаючі  послідовності чисел, і, відповідно, кожна послідовність повністю визначається своїм складом. Тому число таких 7-послідовностей рівно числу 7-співвідношень  із 10 чисел (від 1 до 10). А число цих  співвідношень подається формулою: 

     Ми  отримали той самий результат. 

     Букет квітів.

     Двоє  хлопців зібрали 10 ромашок, 15 васильків  і 14 незабудок. Скількома способами  вони можуть розділити ці квіти?

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

     Зрозуміло, що ромашки можна розділити 11 способами  – перший може не взяти жодної ромашки, взяти 1 ромашку, 2 ромашки, …, всі 10 ромашок. Таким же способом і васильки можна розкласти 16 способами, а незабудки – 15 способами. Так як квіти кожного виду можна ділити незалежно від квітки іншого виду, то по правилу розміщення отримуємо 11×16×15=2640 способами розділення квітів.

     Зрозуміло, що серед цих способів є і дуже несправедливі, при яких, наприклад, один із хлопців зовсім не отримує  квітів. Тому введемо обмеження, що кожний із хлопців повинен отримати не менше 3 квітів кожного виду. Тоді ромашки можна розділити лише п’ятьма способами: перший може взяти  собі 3, 4, 5, 6 або 7 квітів. Так само і  васильки можна розкласти 10 способами, а незабудки – 9 способами. В цьому  випадку загальне число способів ділення рівне 5×10×9=450.

     Взагалі, якщо є предметів одного сорту, предметів другого   сорту, …, предметів k-го сорту, то їх можна розділити між двома людьм

                             (2)

     способами. В тому випадку, якщо всі предмети відрізняються один від одного і  їх число рівне k, то = =…==1 і тому є способів розділення.

     Якщо  ж накласти додаткове обмеження, що кожний із учасників розподілу  повинен отримати не менше  предметів першого сорту, предметів другого сорту, …, предметів k-го сорту, то число способів розподілу виражається формулою:

     (- 2+1)(-+1)…(-+1).      (3) 

     Два коня.

     Скількома способами можна розставити на m×n білого і чорного коней так, щоб вони не могли побити один одного?

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

     Розв’язок цієї задачі ускладнюється тим, що на різних полях дошки кінь має різне число хорд – якщо m ≥5 і n ≥ 5, то в кутку дошки всього два ходи, на одних крайніх полях – три хода, на інших – чотири хода, а в центрі – 8 ходів. Це зв’язано з тим, що кінь має холів різних типів: він може піти на одне поле вперед і на два вверх чи на два поля назад і на одне вниз і так далі. Всього у коней 8 видів ходів, які можна задати, вказавши скільки полів він проходить в горизонтальному напрямку і скільки у вертикальному. Ці ходи мають наступний вигляд: (2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1).

     Для того, щоб впоратися з ускладненнями, які виникли, будемо вважати, що кінь є об’єднанням 8 фігур, кожна із яких має ходи одного типу. Подивимося скількома  способами можна поставити на дошку (2,1)-коня так, щоб він тримав під обстрілом деяке поле обстрілу дошки. Зрозуміло, що він може стояти на будь-якій вертикалі, крім останніх двох, і будь-які горизонталі крім останньої. Отже, вертикаль можна  вибрати n-2способами, а горизонталь m-1 способами, а всього отримаємо (m-1)(n-2) способів поставити білого (2, 1)-коня. В силу симетрії зрозуміло, що стільки ж способів поставити будь-якого з білих (±2, ±1)-коней так, щоб він міг вбити чорного коня. А для білих (±1, ±2)-коней число способів рівне (m-2) (n-1). Звідси слідує, що загальне число способів розміщення двох коней, при яких вони б’ють один одного, виражається формулою:

     4=2.

     Якщо  б ставили коней одного й того ж кольору так, щоб вони могли  захищати один одного, то отримали б  в два рази менше способів (через  можливість переставить коней). А  число способів розставити різного  кольору так, щоб вони не могли  бити один одного, рівне 

     ×-9mn+12m+12n-16. (двох коней можна поставити на m×n дошку mn(mn-1)способами).

     Ті, що складають шах матні задачі іноді вводять «казкові» фігури, які ходять не так як звичайні. Введемо  і ми нову фігуру, яку назвемо (p, q) –конем,  p≥0, q≥0. Хід цієї фігури за клечається у переміщенні на p полей у горизонтальному напрямі і q полей у вертикальному напрямі. Наприклад, звичайний кінь є об’єднанням (1, 2)- і (2,1)-коней. Розмірковуємо так само як і раніше, виводимо, що якщо 0<p≤n, 0<q≤m, то на  m×n дошці-можна 4(n-p)(m-q) способами поставити двох (p, q)-коней різного кольору так, щоб вони били один одного. Якщо ж p чи q, то отримаємо в два рази менше способів. Число способів зменшується вдвічі і в випадку, коли коні однакового кольору.