Задачі на розфарбування площини

Задачі на розфарбування площини

  Одною з цікавих математичних проблем є проблема чотирьох фарб.

Скільки фарб потрібно, щоб розфарбувати  географічну карту, так щоб ніякі дві пограничні держави не були зафарбовані в один колір.  Не важко накреслити карту, для якої досить чотирьох фарб. Математики цілком обґрунтували, що для будь-якої карти достатньо п’ять фарб. А от чи можна стверджувати необхідно й достатньо чотирьох фарб? Відповідь на це запитання залишається відкритою. Відсутність доведення для проблеми чотирьох фарб на площині дивує багатьох математиків, адже ця проблема вже розв’язана для складних поверхонь, для листка Мобіуса,  пляшки Клейна необхідно й достатньо шести фарб,  а для розфарбування тора(бублика) потрібно сім фарб.

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

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

Задача 2. Карта на площині утворена  всілякими прямими. Довести, що для правильного розфарбування такої карти треба два кольори.

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

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

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

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

Доведення: На зафарбованій у три кольори прямій всього можна задати шість відрізків, у яких при накладанні не можуть співпадати кольори кінців. Це відрізки: (ж; ж),  (с; с), (б;б),    (ж; б), (ж; с), (с;б). Таким чином, якщо на прямій задати 2005= 6× 333+1 одиничних відрізки, то за принципом Діріхле щонайменше у 334 відрізків при накладанні можуть співпдати  кольори кінців.

Задача 5.  Вершини трикутника зафарбували жовтими та синіми кольорами. В середині цього трикутника зафарбували ще три точки жовтими та синіми кольорами. Чи можна на цих вершинах утворити:  а) 3 трикутники з синіми вершинами; б) два трикутники з однокольоровими вершинами;  в) чотирикутник з однокольоровими вершинами; г) чотирикутник з вершинами одного кольору; вершинами.

Розв’язання: Складемо таблицю можливих варіантів.

                Кількість           кількість

          жовтих вершин    синіх вершин              а)            б)            в)               г)

                  2                            4                          так          так          так            так

                  3                             3                         ні             так         ні               так

                  4                             2                         ні              так        так             так

                                                                           ------         -----     ---------           --------

                                                                          не завжди    так     не завжди      так

Відповідь: а)  не завжди;  б)так;   в)не завжди;  г)так.

Задача 6. Точки площини зафарбували жовтими та синіми кольорами. На цій площині взяли три точки А, В, С, що не лежать на одній прямій. В середині трикутника з вершинами в точках А, В, С взяли ще три точки X, Y, Z, що не лежать на одній прямій. Чи можна утворити на цих шести точках:  а) 2 трикутники з жовтими вершинами; б) три трикутники з різнокольоровими вершинами;  в) чотирикутник з вершинами одного кольору.  Усі шість точок мають властивість, жодні три точки не лежать на одній прямій.

Розв’язання: Складемо таблицю можливих варіантів.

                Кількість           кількість

          жовтих вершин    синіх вершин              а)            б)                           в)           

                  0                            6                          ні              ні                        так           

                  1                             5                         ні             так                       так

                  2                             4                         ні              так                      так     

                  3                            3                          ні              так                      ні

                  4                             2                        так            так                       так

                  5                             1                         так            так                      так

                  6                            0                         так             ні                        так   

                

                                                                           ------         ------------           ---------        

                                                                          не завжди   не завжди     не завжди 

Відповідь:   а) не завжди;  б) не завжди;   в) не завжди. 

Задача 7. Площина пофарбована у два кольори. Довести, що знайдуться 2 точки на відстані 1 м  : а) одного кольору; б) різних кольорів.

Доведення:а)Якщо на зафарбованій у два кольори площині побудувати правильний трикутник зі стороною 1м, то із трьох його вершин у крайньому разі дві будуть одного кольору. За принципом Діріхле, адже вершин 3, а кольорів всього 2. Вершини одного кольору і утворюють шукані точки.

Б) На відстані не більше двох метрів візьмемо дві точки А та В. Нехай ці точки різного кольору. Їх завжди можна вибрати різного кольору. Побудуємо рівнобедрений трикутник АВС, АС=СВ=1 м. Колір точки С відмінний від кольору однієї із точок А,В.

Задача 8. Площина пофарбована у три кольори. Довести, що знайдуться 2 точки на відстані  1 м  одного кольору.

Доведення: Доведемо, способом від супротивного. Допустимо, що будь-які дві точки, що лежать на даній площині на відстані 1м різного кольору. Розглянемо правильний трикутник АВС зі стороною 1 м. Усі його вершини різного кольору. Нехай точка А1 симетрична А відносно прямої ВС. За припущенням вершини рівностороннього трикутника   А1 ВС різного кольору. А1В=А1С. Але точки А та А1 одного кольору.

Ці міркування  показують, що якщо АА1=, то точки А та А1 одного кольору. Тому всі точки кола радіуса з центром А одного кольору. Зрозуміло, що на цьому колі знайдуться дві точки одного кольору на відстані 1м.. Це протиріччя доводить існування двох точок , відстань між якими 1м.

Задача 9. Чи можливо шахівницю розміру 8х8 обійти конем, почавши обхід з поля h8, закінчивши його на полі а1 так, щоб на кожному полі побувати рівно один раз.

 Розв’язання: За 63 ходи кінь опиниться в чорній клітинці а1, але непарні ходи коня  завжди закінчуються на білій клітинці. Протиріччя доводить неможливість.

Відповідь: не можна.

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

Розв’язання: Весь квадрат 10х10 розділити на квадрати розміром 2х2 та в ньому  зафарбувати синім кольором верхню ліву клітинку. Будь-який квадрат розміром 2х2, що може бути зафарбований у чорний колір містить лише одну  зафарбовану синю клітинку. Отже, максимальна кількість зафарбованих квадратів гравцями рівна кількості синіх клітинок, а їх 25. У цій грі виграє починаючий, якщо скористається симетричною відносно центру квадрата стратегією, зафарбувавши пешим ходом  центр симетрії.

Відповідь: до 25 ходів.  

   Задачі на  розфарбування у шаховому порядку

Задача 1. Чи можна викласти квадрат  розміром 6х6 клітинок фігурками виду Т, які містять тільки чотири клітинки?

Розв’язання: Доведемо , що не можна. Скористаємося методом від супротивного. Допустимо, що можна викласти даними фігурками квадрат. Розфарбуємо всі клітини квадрата 6х6 у шаховому порядку. Кожна фігурка виду Т містить або 1, або 3 однокольорові клітинки. Для визначеності візьмемо чорні клітинки. У 9 фігурках їх непарна кількість. Отже, маємо протиріччя з тим, що загальна кількість чорних клітинок квадрату 6х6 рівна 18.Відповідь: не можна.

Задача 2. На трикутній політичній карті розміром 7 см, 7 см, 7 см є 49 однакових за площею трикутних держав, кордони яких є рівними правильними трикутниками. За домовленістю будь-яка держава цієї політичної карти кожного року направляє  делегацію  тільки в одну з держав, з якою має суцільну  ділянку кордону. Чи усі держави такої політичної карти приймають цього року делегацію з сусідньої держави?

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

Задачі на розфарбування олімпіадного типу

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

Задача 1.На кожній клітині дошки розміром 2005х2005 сидить жук. За    свистком кожний жук переповзе в одну із сусідніх по  діагоналі клітин. При цьому в деяких клітинах можуть    виявитися по кілька жуків, а деякі клітини стануть    незайнятими. Знайдіть найменше число незайнятих    клітин.

Розв’язання. Пофарбуємо вертикалі дошки у білий та чорний кольори так, щоб сусідні вертикалі мали різний колір. Якщо перша зліва вертикаль – чорна, то у нас непарне число  к чорних та парне число n  білих клітин. Переповзаючи, кожний жук  змінює колір клітини, на якій він сидить. На чорні клітини можуть переповзти лише жуки з білих клітин. Тому не менше

k-n чорних клітин стануть вільними.     Відповідь: k-n клітин.

Запитання. В кожній клітині дошки 3*3 сидить жук. В деякий момент всі жуки переповзають на сусідні (по горизонталі або вертикалі) клітини. Чи обов’язково при цьому залишиться хоча   б вільна клітинка?

Вказівка.    Нехай клітини дошки пофарбовано у білий та чорний кольори    у шаховому порядку так, що чорних клітин 13 а білих 12. Оскільки   при переповзанні жук змінює колір клітини, на якій він розташований, одна чорна клітина обов’язково буде вільною.

Задача 2. Є квадратний лист паперу в клітину 100*100. Проведено кілька ламаних без самоперетинів, що йдуть по сторонах     клітинок та не мають спільних точок. Ці ламані лежать всередині     квадрата, лише їх кінці лежать на межі. Довести, що крім вершин     квадрата, знайдеться вузол (всередині або на межі ), який не належить жодній ламаній.

Розв’язання. Пофарбуємо всі вузли в шаховому порядку в чорний та білий кольори. Тоді кожна ламана проходить через чорний та білий вузол по черзі. Нехай всі некутові вузли межі (серед них по    рівну чорних та білих) – кінці ламаних. Тоді ми     маємо однакову кількість ламаних з двома білими     та з двома чорними кінцями. Тому загальні кількості чорних та білих вузлів на ламаних всередині  квадрата рівні ( на ламаних з білими кінцями на один чорний вузол більше, на ламаних з чорними кінцями – на один білий). Але у    нас всередині квадрату 99 і дві десятих вузлів – непарна кількість.

Запитання. Чи можна дві ламані перетнути в  трьох  точках одного кольору?

Запитання. В турнірі грають 2m команд. В першому турнірі  зустрілися між собою m пар команд і в другому турнірі зіграли  між собою m пар ( не обов’язково інші). Як довести, що тепер можна вибрати m команд, серед яких жодні дві не грали між собою?

Вказівка:

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

Запитання. Опуклий n – кутник розбитий на трикутники своїми  діагоналями, що не перетинаються, причому в кожній його вершині сходиться  непарна кількість трикутників. Чому n      кратне 3?

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

Запитання 5. Площина розбита на однакові шестикутні кімнати. В деяких стінах зроблені двері так, що для будь-якої вершини, в  якій сходяться три стіни( сторони шестикутників) двері є точно в двох. Чому будь-який замкнений шлях цим лабіринтом завжди   проходить через парну кількість дверей.

Вказівка:

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

Тепер наведемо завдання, розв’язанню  якого допомагає розфарбування не в два кольори, а в чотири кольори.

Запитання 6. Чому не можна шашкову дошку10*10 закласти плитками   1*4?

Вказівка:

Використаємо діагональне розфарбування в 4 кольори,  плитка 1*4 покриває по одній клітинці кожного кольору.

Але на дошці 10*10 не однакова кількість клітин різних кольорів