Б. В. Бекламов
Застосування теореми Ейлера до деяких задач
У цій статті ми пропонуємо читачам кілька завдань, у вирішенні яких центральну роль грає теорема Ейлера. Приділяючи основну увагу завданням, ми не доводимо тут цю теорему, а наводимо лише її формулювання. Доказ теореми Ейлера, як і більш загальні формулювання цієї теореми, можна знайти в книгах «Що таке математика?» Куранта і Роббінса і «Наочна геометрія» Гільберта і Кон-Фосса.
Перш ніж формулювати теорему Ейлера, домовимося, що лінію з кінцями у двох даних точках ми будемо називати дугою, що з'єднує ці точки. в тому випадку, якщо цю лінію можна пройти, не побувавши в жодній з її точок двічі.
Теорема Ейлера. Нехай на площині задано m точок і n попарно непересічних дуг, кожна з яких з'єднує будь-які дві дані точки і не проходить через остальниеm # 150; 2 точки, і нехай ці дуги ділять площину на l областей. Якщо з кожної даної точки в будь-яку з інших можна потрапити, рухаючись по цим дуг, то
У разі, зображеному на малюнку 1, всі умови теореми Ейлера виконані, m = 1, 2, n = 1 8, l = 8 і m # 150; n + l = 2. На малюнках 2 і 3 зображені випадки, коли умови цієї теореми не виконуються. Так, на малюнку 2 з точки A1 можна потрапити в точку A5 і m # 150; n + l = 3 ≠ 2. а на малюнку 3 лінія, що з'єднує точки A1 і A2. є самопересекающиеся і знову m # 150; n + l = 3 ≠ 2.
У деяких завданнях сукупність, що складається з декількох точок і з'єднують їх попарно непересічних дуг, ми називаємо картою; при цьому точки з цієї сукупності ми називаємо вершинами. а області, на які дуги ділять площину, # 151; країнами.
Тепер ми можемо перейти до вирішення завдань.
Завдання 1. Чи можна десять міст з'єднати між собою не перетинаються дорогами так, щоб з кожного міста виходило п'ять доріг, що ведуть в п'ять інших міст.
Рішення. Припустимо, що міста можна з'єднати між собою дорогами так, як вказано в завданні. У такому випадку, якщо якісь два міста виявляться не з'єднаними дорогою безпосередньо, то знайдеться третє місто, який вже буде безпосередньо з'єднаний з кожним з них. Зобразивши на площині міста точками, а дороги # 151; дугами, отримаємо, що будь-які дві точки з'єднані ланцюжком дуг. Так як в кожній точці сходяться п'ять дуг, то загальне число дуг одно ½ · 5 · 10 = 25. Згідно з теоремою Ейлера ці дуги ділять площину на 2 + 25 # 150; 10 = 17 областей. Кожна з цих сімнадцяти областей обмежена принаймні трьома дугами, так як в противному випадку знайшлися б два міста, безпосередньо з'єднані принаймні двома шляхами, а це суперечить умові завдання. Отже, число дуг не менш ½ · 3 · 17 = 25,5. Таким чином, вихідне припущення приводить нас до протиріччя, і міста не можна з'єднати між собою так, як це потрібно в завданні.
Завдання 2. Три посварених сусіда мають три загальних колодязя. Чи можна провести непересічні доріжки від кожного будинку до кожного колодязя.
Рішення. Припустимо, що це зробити можна.
Зобразимо будинку синіми, а колодязі # 151; чорними точками і кожну синю точку з'єднаємо дугою з кожної чорною крапкою так, щоб дев'ять отриманих дуг попарно не перетиналися. Тоді всякі дві точки, що зображують будинку або колодязі, будуть з'єднані ланцюжком дуг, і в силу теореми Ейлера ці дев'ять дуг розділять площину на 9 # 150; 6 + 2 = 5 областей. Кожна з п'яти областей обмежена принаймні чотирма дугами, так як за умовою завдання жодна з доріжок не повинна безпосередньо з'єднувати два будинки або два колодязі. Тому число дуг повинно бути не менше ½ · 5 · 4 = 10, і, отже, наше припущення невірно.
Завдання 3. Доведіть, що на кожній карті знайдеться країна, що межує не більше ніж з п'ятьма країнами.
Рішення. Якщо число країн на карті не перевищує шести, то твердження задачі очевидно. Ми доведемо, що на карті, що має більш шести країн, знайдуться навіть чотири країни, кожна з яких межує не більше ніж з п'ятьма країнами. Забарвимо вершини і дуги вихідної карти в чорний колір, а червоною фарбою відзначимо в кожній країні по одній точці. Всякі дві відмічені точки, що лежать в сусідніх країнах (тобто країнах, що мають загальну граничну дугу), з'єднаємо всередині цих країн червоною дугою так, щоб червоні дуги попарно не перетиналися. Тоді всякі дві червоні точки будуть з'єднані ланцюжком дуг, і так як ніякі дві побудовані дуги НЕ будуть з'єднувати одні й ті ж точки, то кожна країна на карті, що складається з точок і дуг червоного кольору, буде обмежена не менше ніж трьома дугами. Якщо якась країна на цій картці обмежена більш ніж трьома дугами, то на її кордоні можна вибрати дві вершини, що не з'єднані дугою, і з'єднати їх червоною дугою всередині цієї країни. Повторюючи кілька разів цю операцію, ми отримаємо червону картку, на якій кожна країна обмежена рівно трьома дугами. Так як, крім того, на цій карті ніякі дві дуги не з'єднує одні і ті ж вершини і так як число вершин більше трьох, то з кожної вершини виходять не менше ніж три дуги. Позначимо через n число дуг, через l # 151; число країн, через m # 151; число всіх вершин червоною карти і через a # 151; число вершин, з яких виходять менш ніж шість дуг. тоді отримаємо
З формули (1) і теореми Ейлера, застосованої до системи точок і дуг червоного кольору, випливає, що
яке показує, що a ≥4. Залишається зауважити, що якщо деяка країна на чорній карті має більше п'яти сусідів, то із зазначеної в цій країні червоною точки виходить більше п'яти дуг, і тому, в силу нерівності a ≥4. на чорній мапі знайдуться чотири країни, кожна з яких має не більше п'яти сусідів.
Завдання 4. Чи можна семикутник розрізати на опуклі шестикутники.
Рішення. Припустимо, що якийсь семикутник вдалося розрізати на опуклі шестикутники. Позначимо число тих вершин шестикутників, які лежать всередині вихідного семикутника, через m. а число залишилися вершин (тобто лежать на кордоні семикутника) # 151; через m '. Як дуг, що з'єднують вершини, виберемо прямолінійні відрізки сторін багатокутників, що задовольняють наступній умові: відрізок повинен з'єднувати дві вершини і не проходити через інші вершини. Позначимо через n число таких дуг і через l # 151; число областей, на які ці дуги ділять площину (число l на одиницю більше числа шестикутників). Ясно, що будь-які дві вершини виявляться з'єднаними ланцюжком дуг. В силу теореми Ейлера
Так як зовнішня область обмежена m 'дугами, а кожна з інших # 151; принаймні шістьма дугами, то
З деяких вершин на кордоні семикутника виходять тільки дві дуги. Позначимо число таких вершин через a. З будь-якої іншої вершини виходять принаймні три дуги, так що
Звідси в силу рівності (3)
Порівнюючи це нерівність і нерівність (4), ми отримуємо
Так як на кордоні семикутника знайдуться принаймні дві вершини, з яких виходять дуги, провідні всередину семикутника, то m ' # 150; a ≥ 2. З цієї нерівності і нерівності (5) випливає, що a ≥ 8.
З іншого боку, так як семикутник розрізаний на опуклі багатокутники, то будь-яка вершина, з якої виходять дві дуги, є вершиною семикутника, і тому a ≤ 7. Таким чином, семикутник не можна розрізати на опуклі шестикутники.
Наступні завдання ми пропонуємо читачеві вирішити самостійно.
Чи можна п'ять міст з'єднати між собою не перетинаються дорогами так, щоб з кожного міста в будь-який інший місто вела дорога, що не проходить через інші міста?
Рішення
Припустимо, що міста з'єднані між собою так, як зазначено в умові завдання. Тоді з кожного міста виходять чотири дороги, і загальне число доріг дорівнює 5 · 4/2 = 10. З іншого боку, в силу теореми Ейлера, число областей, на які дороги ділять площину, дорівнює 2 + 10 # 150; 5 = 7; причому кожна з областей обмежена принаймні трьома шляхами; тому загальне число доріг повинно бути не менше 3 · 7/2 = 10,5. Значить, міста з'єднати так, як сказано в задачі, не можна.
Доведіть, що якщо на карті число країн більше дев'ятнадцяти, то на цій карті знайдуться три країни з однаковим числом сусідів.
Рішення
Побудуємо «подвійну карту»: відзначимо в кожній країні по точці і з'єднаємо точки, що лежать в сусідніх країнах, непересічними дугами. Позначимо через m. n і l відповідно число вершин, ребер і країн двоїстої карти. Ясно, що двоїста карта пов'язана (тобто кожні дві вершини з'єднані ланцюжком дуг) і кожна країна на двоїстої картці обмежена принаймні трьома дугами. Таким чином, 3l ≤ 2n.
Звідси, в силу теореми Ейлера, 6m ≥ 12 + 2n. Зіставляючи цю нерівність з очевидними співвідношеннями
де mi позначає число вершин, з яких виходять i ребер, ми отримуємо
П'ятикутник розрізаний на кілька багатокутників так, що всі сторони вихідного п'ятикутника залишилися нерозрізаними. Доведіть, що якщо число одержані багатокутників не менше п'яти, то в одному з них знайдеться кут, який більше або дорівнює 72 °.
Рішення
Як і в завданні про семикутник, розглянемо карту, яка визначається лініями розрізів, і позначимо число вершин, дуг і країн цієї карти відповідно через m. n і l. Назвемо вершину карти неправильною. якщо вона лежить на боці одного з багатокутників і не є його вершиною; позначимо число неправильних вершин через m '. Через r позначимо число дуг, що виходять з вершин вихідного п'ятикутника і відмінних від його сторін, причому кожну дугу, обидва кінці якої лежать в вершинах п'ятикутника, домовимося вважати двічі. Припустимо, що в кожному з багатокутників всі кути менше 72 °. Тоді: а) всі країни, крім необмеженої, є трикутниками; б) з кожної правильної вершини, що лежить всередині вихідного п'ятикутника, виходять не менш ніж шість дуг, а з кожної неправильної # 151; не менш ніж чотири. З а) слід, що 2n = 3 (l # 150; 1) + m '+ 5, а з б) # 151; що
З цих співвідношень отримуємо, що
Так як по теоремі Ейлера m # 150; n + l = 2, то отримане нерівність означає, що r ≤ 4. З іншого боку, неважко показати, що якщо п'ятикутник розрізаний більше ніж на чотири багатокутника, то r> 4. Отже, хоча б в одному з багатокутників буде кут, більший або рівний 72 °.
Трикутник, всі кути якого не більше 120 °, розрізаний на кілька трикутників. Доведіть, що в одному з вийшов трикутників всі кути не більш 120 °.
Рішення
Як і в попередній задачі, розглянемо карту, яка визначається лініями розрізів. Позначимо число вершин, дуг і країн вийшла карти відповідно через m. n і l. число неправильних вершин через m '. Ясно, що 3l + m '= 2n. і так як по теоремі Ейлера m # 150; n + l = 2, то
Дійсно, з кожної правильної вершини, що лежить всередині вихідного трикутника, виходять не більше ніж два кута, великих 120 °, а з кожної неправильної вершини # 151; не більше ніж один. Протиріччя між (*) і (**) показує, що серед трикутників, що вийшли після розрізання, знайдеться трикутник, всі кути якого не більше 120 °.
У грі беруть участь два гравці. Перед початком гри на площині зазначається m точок. Гравці по черзі розшукують дві точки, ще не з'єднані дугою, і з'єднують ці точки дугою, яка не перетинає раніше побудовані дуги. Виграє той, хто робить останній хід. За яких m виграє гравець, який зробив перший хід, а за яких # 151; його противник?
Рішення
Виявляється, що число ходів в цій грі визначається тільки числом m. Дійсно, випадок m = 2 очевидний. Нехай m> 2. тоді в кінці гри на площині вийде карта, на якій кожні дві вершини з'єднані ланцюжком дуг і кожна країна обмежена трьома дугами, тобто 2 n = 3 l. З теореми Ейлера випливає, що число дуг такої карти дорівнює 3 (m # 150; 2). Але число дуг на получающейся карті дорівнює числу ходів в нашій грі. Тому отримуємо: при непарному m. більшому двох, виграє гравець, який зробив перший хід, а при парному m. більшому двох # 151; його противник.