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

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

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

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

Вправи для самостійного розв’язання

1. Куб розбито на 27 однакових кубиків. В початковий момент    жук знаходиться в центральному кубику. З кожного кубика жук    може переходити до сусіднього, що має з ним спільну грань. Чи    зможе жук обійти всі кубики, побувавши в кожному по одному    разу?

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

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

Вказівка:Пофарбуємо дно коробки у білій та чорний кольори. Тоді кожна плитка 2*2 покриває одну чорну клітину, а плитка 1*4 – 2 або 0. Парність кількості плиток 2*2 повинна співпадати з парністю кількості чорних клітин.

3. Король обійшов дошку 9*9, побувавши точно один раз на  кожному полі. Маршрут короля не замкнений і, можливо, самоперетинається. Яка найбільша можлива довжина такого маршруту,    якщо довжина ходу по діагоналі дорівнює корінь 2, по вертикалі     або горизонталі – 1?

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

клітинок на кольорові і назад не менше 16. Кожен такий перехід   має довжину 1, тому загальна довжина маршрута  не перевищує   16 + 64 корінь 2. А маршрут з такою довжиною існує. Король має   почати шлях з лівого нижнього кута, пройти по краю одну клітину,   знов повернути на 135 градусів і пройти по діагоналі до краю, ще  пройти по краю одну клітину, знов повернути на 135 градусів і пройти по краю і т.д.

4. Правильний трикутник із стороною n розбито прямими, паралельними сторонами трикутника, на n квадратних правильних трикутників із стороною 1. По сторонах отриманих трикутників проведена незамкнена ламана, що проходить через всі вершини трикутників точно по одному разу. Доведіть, що не менше n пар сусідніх ланок ламаної утворюють між собою гострий кут.

Вказівка:

Розфарбуємо трикутники у чорний    та білий кольори.    Кожна ланка ламаної проходить по стороні чорного трикутника. У нас n квадратних   ……вершин, тому ламана  має……ланок.

Всього чорних трикутників…., тому не     менше n з них містять по парі ланок утворюють гострий кут.

Задача 11.1. Хлопчик та дівчинка по черзі зафарбовують клітини  прямокутної таблиці. За один хід треба зафарбувати

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

а) 1990*1992;

б)1991*1992?

Вказівка: а)Переможе хлопчик. Після кожного ходу дівчинки йому

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

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