Задачі на розфарбування

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

Задача 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 не однакова кількість клітин різних кольорів