КОМБІНАТОРНА ГЕОМЕТРІЯ

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

Розв'язання

Нехай на площині проведено n-1 прямих, серед яких жодні дві не па­ралельні і жодні три не проходять через одну точку. Ці прямі розділяють площину на деяку кількість областей. Проведемо п пряму так, щоб були виконані умови задачі. Ця пряма точками перетину з попередніми л-1 прямими розділиться на п прямолінійних частин (n-2 відрізки і два про­мені). Кожна з цих прямолінійних частин розділить одну з областей, яку вже маємо, а саме ту, в якій вона міститься, на дві. Тому число областей, на які розділиться площина після проведення п прямої, збільшиться на n. Отже, число областей, на які розділяють площину n прямих, що задоволь­няють умову задачі, дорівнює

1+1+2+3+...+n=1+ n(n+1).

2.     Яка найбільша кількість гострих кутів може бути в опуклому п-кут­нику?

Розв'язання

Як відомо, сума зовнішніх кутів довільного опуклого многокутника дорівнює 360°. Тому в опуклому многокутнику не може бути більше трьох гострих кутів, оскільки в протилежному випадку такий многокутник мав би не менше чотирьох тупих зовнішніх кутів і їх сума перевищувала б 360°. Легко довести, що для кожного цілого n≥3 існує опуклий n-кутник, що має 3 гострі внутрішні кути.

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

Розв'язання

Очевидно, що п кіл будуть ділити поверхню кулі на найбільшу кількість областей, якщо всі ці кола будуть перетинатися між собою (тобто будь-які два з них будуть мати по дві спільні точки) і жодні три з них не будуть пере­тинатися в одній точці. Припустимо, що на сфері уже є k таких кіл. Вони розділяють сферу на деяку кількість областей. Проведемо k+1 коло з дотриманням вказаних умов і порахуємо, на скільки збільшиться число таких областей. Проведене коло перетинається з k колами у 2k точках, які розділяють його на 2k частин. Кожна з них розділяє область, в якій вона знаходиться, на дві частини. Отже, після проведення n-1 кола число областей збільшиться на 2k і n кіл розділять поверхні кулі на 2+2+4+6+8+...+2(n-1)=2+2*n(n-1)/2 = n*n-n+2 областей.

4.     Тисяча точок є вершинами опуклого тисячокутника, всередині яко­го взято 500 точок так, що жодні три з 1500 не лежать на одній прямій.
Многокутник розрізаємо на трикутники, вершини яких є задані 1500 то­чок. Скільки дістанемо трикутників?

Розв'язання

Нехай n — число трикутників. Зауважимо, що

180°n = 180°(1000 – 2) + 360° ∙ 500,

де в правій частині рівності перший доданок дорівнює сумі внутрішніх кутів тисячокутника. Звідси n = 1998.

5.     Шахова дошка розміром 6x6 покрита 18 кісточками доміно (кожна
кісточка покриває дві клітини дошки). Доведіть, що незалежно від спосо­бу розміщення дошку завжди можна розрізати вздовж вертикальної чи горизонтальної прямої на дві частини, не пошкодивши жодної кісточки
доміно.

Розв'язання

Кожна кісточка доміно перекриває лише одну з 10 горизонтальних і вертикальних ліній, якими розкреслена дошка. З іншого боку, кожна така лінія перетинає парне число кісточок. Доведемо це від супротивного. Нехай, наприклад, деяка вертикальна лінія перетинає непарну кількість кісточок. Розріжемо дошку вздовж цієї лінії і розглянемо одну з двох утво­рених прямокутних дошок. Вона має парне число клітинок, а кількість клітинок, покритих розрізаними половинками кісточок, — непарна. Тоді нерозрізані кісточки покривають також непарне число клітинок (інакше загальне число клітинок дошки було б непарним). Це неможливо, оскільки кожна кісточка покриває дві клітинки. Припустимо тепер, що кожна із 10 ліній, що розглядаються, перетинає хоча б одну кісточку доміно. Тоді кількість кісточок, що кожна лінія перетинає, не менше ніж 2. Звідси випливає, що на дошці розміщено не менше ніж 20 кісточок доміно, що неможливо.

6.     На площині дано 100 точок A₁, А₂, ..., А₉₉, O. Жодні три з них не ле­жать на одній прямій. Через точку О проходить пряма так, що по один бік від неї лежать 48 точок. Чи існує пряма, що проходить через О, по один бік від якої лежать 49 точок?

Розв'язання

Така пряма завжди існує. Для доведення почнемо обертати дану в умові пряму, слідкуючи при цьому за різницею чисел точок, що лежать по один і по другий бік від цієї прямої. В початковий момент ця різниця дорівнювала          48 – (99 – 48) = –3. Зауважимо, що зазначена різниця за кожного досить малого повороту прямої або не змінюється, або змінюється тільки на 2. У першому випадку під час руху прямої на її шляху не зустрічаються точки, а в другому одна точка переходить з одного боку прямої на другий. Дві точки одночасно не можуть перейти на другий бік, оскільки жодні дві точки з даних не лежать на одній прямій з О. За повороту прямої на 180° введена різниця числа точок буде дорівнювати 3, оскільки півплощини, на які пряма ділить площину, поміняються місцями. Як зазначено раніше, зміна різниці може відбуватися приростами на 2 і на —2. Отже, в деякий момент часу ця різниця набувала значення +1, тобто по один бік прямої знаходилось 49 точок, а по другий — 50.

7.     Діагоналями, які не перетинаються, опуклий n-кутник поділено на трикутники так, що кожна вершина n-кутника є вершиною непарного числа трикутників. Доведіть, що n ділиться на 3.

Розв'язання

Розфарбуємо трикутники у два кольори (чорний і білий) так, щоб будь-які два суміжні трикутники (які мають спільну сторону) були різних кольорів, можливість такого пофарбування можна довести методом мате­матичної індукції. Тоді всі трикутники, які мають з многокутником спільну сторону, пофарбовані в один колір, наприклад білий. Тоді, очевидно, сто­рони многокутника будуть білими, а діагоналі чорно-білими. Якщо р — кількість трикутників білого кольору, a q — кількість трикутників чорного, то                   п = 3р – 3q = 3(р – q), тобто ділиться на 3.

9.       Кожна з граней правильного тетраедра фарбується одним із даних чотирьох кольорів. Два фарбування вважаються однаковими, якщо одне з них можна перевести в інше поворотом тетраедра навколо якої-небудь його осі. Скількома способами можна пофарбувати тетраедр?

Розв'язання

Занумеруємо кольори числами 1, 2, 3, 4. Одну грань тетраедра назвемо «нижньою», а інші — «бічними». Оскільки будь-яку грань можна сумісти­ти з будь-якою іншою, повернувши тетраедр відносно осі, то можна вва­жати, що «нижня» грань пофарбована в колір 1. Поворотами осі, що про­ходить через центр «нижньої» грані, будь-яку з «бічних» граней можна зробити «передньою». Тому можна вважати, що передня грань пофарбова­на в колір 2. Тоді положення двох інших граней після нього визначається однозначно. Залежно від того, яку з цих граней пофарбовано кольором 3, матимемо два різні способи фарбування.

Задачі для самостійного розв'язування

10.       На площині позначили:

а) 6 точок;

б) п точок, п >3. Відомо, пряма, що проходить через будь-які дві з цих
точок, містить ще одну позначену точку. Доведіть, що всі позначені точки лежать на одній прямій.

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

12.       Знайдіть найбільшу кількість замкнутих парканів, що не перетина­ються, в місті з п будинками (паркан може відгороджувати один чи декілька
будинків, а також уже відгороджені ділянки; на території між будь-якими
двома парканами повинен знаходитись хоча б один будинок).

13.       Доведіть, що при n ≥ 5 довільний прямокутник можна розбити на п
прямокутників так, щоб жодні два сусідні не утворювали разом прямокутник.

14.       На площині дано 12 точок, відстані між якими не перевищують 3 см. Чи можна стверджувати, що серед цих 12 точок можна вибрати чоти­ри таких, що всі відстані між ними не перевищують 2 см?

15.       Розмістіть 6 точок на площині так, щоб кожні 3 із них утворювали рівнобедрений трикутник.

16.       Скільки існує квадратів, вершини яких знаходяться у вузлах квадратної сітки всередині прямокутника 9x10, а сторони паралельні сто­ронам сітки?

17. На яку найбільшу кількість частин розбивають площину три прямокутники?

18.       На площині дано п точок, жодні три з яких не лежать на одній
прямій. Дозволяється з'єднувати точки відрізками так, щоб ці відрізки не
перетинались. Доведіть, що найбільша кількість відрізків, які можна про­ вести, не залежить від вибору пар з'єднуваних точок.

19.       На площині проведено п прямих так, що жодні дві з них не паралельні,
а жодні три не мають спільної точки. Знайдіть кількість точок перетину цих прямих. Скільки трикутників утворюють ці прямі? На скільки частин розбива­ють площину ці прямі? Скільки серед них частин необмежених?

20.       Клітини двох таблиць розміру 1982x1983 зафарбовані в червоний
і синій кольори так, що в кожному рядку і в кожному стовпчику парне
число синіх клітин. Одну з цих таблиць наклали на другу. При цьому одна
із синіх клітин сумістилася з червоною клітиною. Доведіть, що знайдуться
ще принаймні три клітини, покриті клітинами протилежного кольору.

21.       Коридорами лабіринту є всі сторони і діагоналі опуклого л-кутника. Яку найменшу кількість ламп необхідно розмістити в лабіринті так, щоб повністю його освітити?

22.       На прямій знаходяться павук і муха. Максимальна швидкість паву­ка вдвічі більша від максимальної швидкості мухи, але він нічого не знає про місцезнаходження мухи до тих пір, поки вони не опиняються в одній точці. Чи зможе павук наздогнати муху?

23.       На кожній з двох паралельних прямих позначено п точок і прове­дено кілька відрізків, що сполучають позначені точки різних прямих. Яку найбільшу кількість цих відрізків можна провести так, щоб вони не перетиналися всередині смуги між даними прямими?