Задачі на розфарбування
Задача: розфарбувати площину в n кольорів так, щоб будь-які точки на відстані 1 були різного кольору.
Легко показати, що n повинно бути більше 3. Але наразі не відомо, чи достатньо n=4; найкращий відомий розв'язок - при n=7, ось такий:
Діаметр (найбільша діагональ) кожного шестикутника - 1-ε, де ε - нескінченно мале.
Напевно, розв'язок для 4-х кольорів, якщо він існує, вже не буде простим паркетом, але якби хтось знайшов паркет, який фарбується в 6 кольорів - це теж було б значним досягненням. На одній цій задачі можна зробити собі ім'я.
Ти, як дослідник, зможеш аналізувати цю задачу , спочатку спробуй знайти 7-кольорове розфарбування шестикутного паркета, а тоді, якщо вийде - пошукай інші варіанти. Квадратний паркет фарбується у 8 кольорів багатьма способами (при різних розмірах квадрата). Можна влаштувати конкурс: хто знайде більше таких розфарбувань?
Про класичну задачу 4-х фарб ти, мабуть, знаєш не гірше за мене. Її було розв'язано перебором на комп'ютері, але цей розв'язок не всіх математиків влаштовує, тому що під ним нема ніякої теорії, і його дуже важко перевірити вручну.
********************
Так ти стверджуєш, що задачу на розфарбування плоскої карти із багатокутників чотирма кольорами ще ніхто не проілюстрував?
Ти ж бачив карту України в чотири кольори 
Стівен Барр запропонував логічну гру на папері для двох гравців, під назвою «Чотири фарби». За словами Мартіна Гарднера — «Я не знаю кращого способу зрозуміти труднощі, що зустрічаються під час вирішення проблеми чотирьох фарб, ніж просто зіграти в цю цікаву гру»[8].
Для цієї гри потрібно чотири кольорових олівці. Перший гравець починає гру, малюючи довільну порожню область. Другий гравець зафарбовує її будь-яким з чотирьох кольорів і в свою чергу малює свою порожню область. Перший гравець зафарбовує область другого гравця та додає нову область, і так далі — кожен гравець зафарбовує область суперника та додає свою. При цьому області, що мають спільну межу, повинні бути зафарбовані різними кольорами. Програє той, хто під час свого ходу змушений взяти пʼятий колір.
Варто зауважити, що у цій грі програш одного з гравців зовсім не є доказом хибності теореми (чотирьох фарб недостатньо!), а лише ілюстрацією того, що умови гри та теореми відрізняються. Щоб перевірити правильність теореми для отриманої у грі карти, потрібно перевірити зв'язність зображених областей та, видаливши з неї кольори, з'ясувати, чи можна обійтися лише чотирма кольорами для того, щоб зафарбувати отриману карту (теорема стверджує, що можна).
Існують також такі варіації гри:
- Карта заздалегідь розбивається випадковим чином на області різного розміру, і кожен хід гри змінюється гравець, що зафарбовує область, а також змінюється колір (за чіткою послідовністю). Таким чином кожен гравець зафарбовує карту тільки двома кольорами, а у випадку, якщо не може зафарбувати так, щоб області, що мають спільну межу, були зафарбовані у різні кольори — пропускає хід. Гра припиняється тоді, коли жоден з гравців більше не зможе зробити жодного ходу. Виграє той, у кого площа зафарбованих ним областей більша.
- Квадрат розбито на декілька квадратів (в основному 4x4), та його сторони зафарбовані одним з чотирьох кольорів (кожна в інший колір). Першим ходом зафарбовується квадрат, що прилягає до сторони, кожним наступним ходом можна зафарбовувати той квадрат, що прилягає до одного із зафарбованих квадратів. Не можна зафарбовувати квадрат тими самими кольорами, котрими зафарбовано один з квадратів, що прилягають до нього (в том числі й по діагоналі) або сторона, що прилягає до нього. Виграє гравець, що робіть останній хід.
- **********************************
Стівен Барр запропонував логічну гру на папері для двох гравців, під назвою «Чотири фарби». За словами Мартіна Гарднера — «Я не знаю кращого способу зрозуміти труднощі, що зустрічаються під час вирішення проблеми чотирьох фарб, ніж просто зіграти в цю цікаву гру»[8].
Для цієї гри потрібно чотири кольорових олівці. Перший гравець починає гру, малюючи довільну порожню область. Другий гравець зафарбовує її будь-яким з чотирьох кольорів і в свою чергу малює свою порожню область. Перший гравець зафарбовує область другого гравця та додає нову область, і так далі — кожен гравець зафарбовує область суперника та додає свою. При цьому області, що мають спільну межу, повинні бути зафарбовані різними кольорами. Програє той, хто під час свого ходу змушений взяти пʼятий колір.
Варто зауважити, що у цій грі програш одного з гравців зовсім не є доказом хибності теореми (чотирьох фарб недостатньо!), а лише ілюстрацією того, що умови гри та теореми відрізняються. Щоб перевірити правильність теореми для отриманої у грі карти, потрібно перевірити зв'язність зображених областей та, видаливши з неї кольори, з'ясувати, чи можна обійтися лише чотирма кольорами для того, щоб зафарбувати отриману карту (теорема стверджує, що можна).
Існують також такі варіації гри:
- Карта заздалегідь розбивається випадковим чином на області різного розміру, і кожен хід гри змінюється гравець, що зафарбовує область, а також змінюється колір (за чіткою послідовністю). Таким чином кожен гравець зафарбовує карту тільки двома кольорами, а у випадку, якщо не може зафарбувати так, щоб області, що мають спільну межу, були зафарбовані у різні кольори — пропускає хід. Гра припиняється тоді, коли жоден з гравців більше не зможе зробити жодного ходу. Виграє той, у кого площа зафарбованих ним областей більша.
- Квадрат розбито на декілька квадратів (в основному 4x4), та його сторони зафарбовані одним з чотирьох кольорів (кожна в інший колір). Першим ходом зафарбовується квадрат, що прилягає до сторони, кожним наступним ходом можна зафарбовувати той квадрат, що прилягає до одного із зафарбованих квадратів. Не можна зафарбовувати квадрат тими самими кольорами, котрими зафарбовано один з квадратів, що прилягають до нього (в том числі й по діагоналі) або сторона, що прилягає до нього. Виграє гравець, що робіть останній хід.
- **********************************
При розв’язанні олімпіадних задач інколи клітинки, точки або інші фігури вважають розфарбованими в різні кольори в деякому порядку. Фактично це означає розбиття множини всіх даних фігур на підмножини. Розфарбування робить розв’язання більш наочним, та й міркувати за таким малюнком легше. В попередньому параграфі ми частково познайомилися з тим як розфарбування дозволяє знаходити важливі для нас закономірності. Розглянемо ще декілька прикладів.
Задача 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 не однакова кількість клітин різних кольорів
