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

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

Не той розумний, хто вміє відрізнити добро від зла, а той, хто вміє із двох напастей вибирати найменшу.                                                      Арабська мудрість

Приклади розв’язання задач

                                               

    Серія    А

 Задача 1. У кожній вершині правильного 100-кутника розташовані фішки: 76 червоних та 24 синіх. Довести, що знайдуться 4 червоні фішки, що утворюють квадрат.

Розв’язання: Зрозуміло, що 100 фішок можуть утворити 100:4=25 квадратів, тому (по одній синій фішці у кожного квадрата) сині вершини будуть мати не більше 24 квадратів, отже, один квадрат буде мати червоні вершини.

Задача 2. У кожній вершині правильного 2005-кутника розташовані фішки:1605 червоних та 400 синіх. Довести, що знайдуться 5 червоні фішки, що утворюють правильний п’ятикутник.

Розв’язання: В правильному 2005-кутнику можна утворювати правильні п’ятикутники так: між будь-якими двома вершинами п’ятикутника повинна знаходиться рівно 400 вершин даної фігури.  Зрозуміло, що 2005 фішок можуть утворити 2005:5=401 правильних п’ятикутників, тому (по одній синій фішці у кожного правильного п’ятикутника) сині вершини будуть мати не більше 400 п’ятикутника, отже, один п’ятикутник буде мати червоні вершини.

Задача 3. У кожній вершині правильного 2004-кутника розташовані фішки:1838 червоних та 166 синіх. Довести, що знайдуться 12 червоних  фішки, що утворюють правильний 12-кутник.

Розв’язання: В правильному 2004-кутнику можна утворювати правильні 12-кутники так: між будь-якими двома вершинами 12-кутника повинна знаходиться рівно 166 вершин даної фігури.  Зрозуміло, що 2004 фішки можуть утворити 2004:12=167 правильних 12-кутників, тому (по одній синій фішці у кожного правильного 12-кутника) сині вершини будуть мати не більше 400 п’ятикутника, отже, один п’ятикутник буде мати червоні вершини.

Задача 4. У кожній вершині правильного 24-кутника розташовані фішки:21 червоних та 3 синіх. Довести, що знайдуться 6 червоних  фішки, що утворюють правильний 6-кутник.

Розв’язання: В правильному 24-кутнику можна утворювати правильні 6-кутники так: між будь-якими двома вершинами 6-кутника повинна знаходиться рівно 3 вершини даної фігури.  Зрозуміло, що 2004 фішки можуть утворити 24:6=4 правильних 6-кутників, тому (по одній синій фішці у кожного правильного 6-кутника) сині вершини будуть мати не більше три 6-кутника, отже. один 6-кутник буде мати червоні вершини.

                           

 Серія Б

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

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

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

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

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

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

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

   

Серія В

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

чотири клітинки?

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

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

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

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

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

Відповідь : не всі.

Колективне осмислення розв’язування задач

Група 1. Задачі на розфарбування прямої

Задача 1.  Пряму зафарбували у чорний та білий кольори.  Довести, що на цій прямій існують три однокольорові точки А₁, А₂, А₃ для яких виконується умова: А₁А₂ = А₃А₂.

Доведення: На прямій візьмемо дві однокольорові точки С₁ та С₂ , це завжди можна зробити. Точка С₁ розташована лівіше точки С₂. На  однаковій відстані  С₁С₂ відкладемо від цих двох точок вліво та вправо  такі відповідні точки В₁  та В₂, а третю точку В₃  відкладемо в середині відрізка  С₁С₂.  Можливі випадки:

    А) В₃ одного кольору з однокольоровими точками  С₁ та С₂;

    Б)  В₃  неоднакового кольору з однокольоровими точками  С₁ та С₂;

У випадку а) точки  В₃, С₁ та С₂ достатньо перейменувати  ці точки на А₁, А₂, А₃.

У випадку б) точки  В₃, С₁ та С₂ достатньо розглянути такі випадки:

Б1) В₃  та    В₁  однокольорові, але відмінні від кольору точки    В₂;

Б2) В₁  та    В₂  однокольорові, але відмінні від кольору точки    В₃;

Б3) В₃  та  В₂,  В₁  однокольорові;

У випадку Б1) точки  В₂, С₁ та С₂ достатньо перейменувати  ці точки на А₁, А₂, А₃.

У випадку Б2) точки  В₂, С₁ та С₂ достатньо перейменувати  ці точки на  А₁, А₂, А₃.

У випадку Б3) точки  В₂, В₃ та В₁ достатньо перейменувати  ці точки на  А₁, А₂, А₃.

Задача 2.  Пряму зафарбували у чорний та білий кольори. На прямій існують три однокольорові точки А1, А2, А3 для яких виконується умова: А1 А2 = А3 А2.  Чи можна на цій прямій взяти ще три точки X,Y, Z  одного кольору, для  яких виконується умова: XY=XZ. 

Розв’язання:  Так, адже доведення задачі 1, не використовує масштабу та точку відліку. Тому місце положення  трьох точок X,Y, Z  одного кольору, для  яких виконується умова: XY=XZ,  можна вибирати довільно. 

Задача 3.  Пряму зафарбували у чорний, білий  та жовтий кольори. На прямій існують три точки А₁, А₂, А₃, які відрізняються одна від одної трьома кольорами, для яких виконується умова: А₁А₂ = А₃А₂.  Чи можна на цій прямій взяти ще таких три точки X,Y, Z , які відрізняються одна від одної трьома кольорами, для  яких виконується умова: XY=XZ? 

Розв’язання:  Не завжди. Адже пряму можна пофарбувати дискретно. Лише одну точку у чорний колір, а всі інші в білий та жовтий.

       

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

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

Задача 5. Усі точки прямої зафарбовані у чотири кольори. Чи можна серед 11 одиничних відрізків знайти два відрізки, у яких при накладанні співпадають  кольори кінців.

 Розв’язання:   На зафарбованій у чотири кольори  прямій можна задати щонайбільше десять одиничних відрізків, у яких кольори кінців не співпадають. Наприклад, якщо кольори кінців позначити числами 1,2,3,4, можливі такі кольори кінців одиничних відрізків: (1;1), (2;2 ), (3;3), (4;4 ), (1;2), (1;3 ), (1;4 ), (2;3 ), (2;4 ), (3;4 ). За принципом Діріхле серед 11 одиничних відрізків знайдуться щонайменше 2 одиничних відрізки, у яких при накладанні співпадають кольори кінців.

 Задача 6. Яку найбільшу кількість різних відрізків з різнокольоровими кінцями  у довільних чотирьох точках можна задати на  прямій, усі точки якої зафарбовані у два кольори.

Розв’язання:   У випадку, коли усі чотири точки одного кольору не має таких відрізків. У випадку, коли одна точка відрізняється від трьох інших, маємо три таких відрізки. У випадку, коли дві точки одного, а дві інші різного,  то ….

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

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

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

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

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

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

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

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

Задача 8. Площина пофарбована у три кольори. Довести, що знайдуться 2 точки на відстані  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 ходів.