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

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

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

Задача  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 симетрична А відносно прямої ВС. За припущенням вершини рівностороннього трикутника   А₁ВС різного кольору. А₁В=А₁С. Але точки А та А₁ одного кольору.

Ці міркування  показують, що якщо АА₁=3^0,5, то точки А та А₁ одного кольору. Тому всі точки кола радіуса 3^0,5з центром А одного кольору. Зрозуміло, що на цьому колі знайдуться дві точки одного кольору на відстані 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. З шахівниці вирізували дві протилежні кутові клітки. Доведіть, що фігуру, що залишилася, не можна розрізати на «доміно» з двох кліток.

Розв’язання. Кожна фігура «доміно» містить одну білу і одну чорну клітку. Але в наший фігурі 32 чорних і 30 білих кліток (або навпаки).

Приклад 2. Чи можна всі клітини дошки 9x9 обійти конем по одному разу і повернутися в початкову клітку?

Розв’язання. Кожним ходом кінь міняє колір клітки, тому, якщо існує обхід, то число чорних кліток рівне числу білих, що невірно.

Приклад 3. Даний куб 6x6x6. Знайдіть максимально можливе число паралелепіпедів 4x1x1 (із сторонами паралельними сторонам куба), які можна помістити в цей куб без перетинів.

Ідея розв’язання.. Легко помістити 52 паралелепіпеди всередину куба. Доведемо, що не можна більше. Розіб'ємо куб на 27 кубиків 2x2x2. Розфарбуємо їх в шаховому порядку. При цьому утворюється 104 клітки одного кольору (білого) і 112 іншого (чорного). Залишилося відмітити, що кожен паралелепіпед містить дві чорних і дві білі клітки.

Відповідь: 52.

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

Розв’язання. Розглянемо рівносторонній трикутник із стороною 1. За принципом Дирихле принаймні дві з його трьох вершин повинні бути пофарбовані в один колір.

Завдання

У кожній клітині дошки 5x5 сидів жук. Потім кожен жук переповз на сусідню (по стороні) клітку. Доведіть, що залишилася хоч би одна порожня клітка.

3. Пряма розфарбована в два кольори. Доведіть, що знайдуться 3 крапки А, В, З одного кольору такі, що АВ = ВС.

Розфарбуйте пряму в три кольори так, щоб не можна було знайти трьох крапок А, В, З різного кольору таких, що АВ = ВС.

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

Розфарбуйте площину а) у 9, б) у 7 кольорів  так, щоб не знайшлося двох точок одного кольору на відстані 1.

Чи можна замостити дошку 6x6 кліток смужками з трьох кліток і одним куточком з трьох кліток?

Чи можна замостити дошку 10 х 10 прямокутниками 4x1?

Чи можна дошку 5x7 покрити куточками з трьох кліток в декілька шарів  (щоб кожна клітка була покрита однаковим числом куточків)?

Вказівка. Розставити числа, щоб загальна сума була позитивна, а сума в кожному куточку негативна.