Хроматичні числа. Задачі розфарбування.

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

Хроматичне число графа G — мінімальна кількість кольорів, в які можна розфарбувати вершини графа G таким чином, щоб кінці будь-якого ребра мали різні кольори. Позначається χ(G).



Задача 1.  Пряму зафарбували у чорний та білий кольори.

Довести, що на цій прямій існують три однокольорові точки А1, А2, А3 для яких виконується умова: А1 А2 = А3 А2.

Доведення: На прямій візьмемо дві однокольорові точки С1 та С2 , це завжди можна зробити. Точка С1 розташована лівіше точки С2.

 На  однаковій відстані  С1С2 відкладемо від цих двох точок вліво та вправо  такі відповідні точки В1  та В2,

 а третю точку В3  відкладемо в середині відрізка  С1С2.  Можливі випадки:

    А) В3 одного кольору з однокольоровими точками  С1 та С2;

    Б)  В3  неоднакового кольору з однокольоровими точками  С1 та С2;

У випадку а) точки  В3, С1 та С2 достатньо перейменувати  ці точки на

А1, А2, А3.

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

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

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

Б3) В3  та  В2,  В1  однокольорові;

У випадку Б1 точки  В2, С1 та С2 достатньо перейменувати  ці точки на

А1, А2, А3.

У випадку Б2 точки  В2, С1 та С2 достатньо перейменувати  ці точки на

А1, А2, А3.

У випадку Б3 точки  В2, В3 та В1 достатньо перейменувати  ці точки на

А1, А2, А3.

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

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

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

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

       

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

Чи можна розфарбувати пряму у три кольори так, щоб на ній не існувало однокольорових відрізків однакової довжини?

Чи можна розфарбувати координатну пряму у три кольори так, щоб на ній не було однокольорових відрізків, що симетричні відносно початку координат?

Усі точки координатної прямої зафарбували у два кольори. Чи можна на цій прямій отримати лише 2006 симетричних відносно початку координат однокольорових точок?

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

Усі відрізки прямої зафарбували у два кольори. Чи можна на такій прямій взяти три однокольорових відрізки, з яких не складається трикутник?

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

Яка найменша кількість кольорів потрібна для розфарбування координатної прямої, аби на ній не виявилося різнокольорових рівних відрізків?

Чи можна розфарбувати у п’ять кольорів координатну пряму, аби  однокольорові відрізки знаходилися на одноковій відстані?

Чи можна координатну пряму розфарбувати кольорами веселки, аби на ній не було симетричних відносно початку координат однокольорових точок?

Яка найменша кількість кольорів потрібна для розфарбування   даного відрізка, аби усі відрізочки даного відрізка  мали однокольорові середини?

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

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

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

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

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

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

Задача 9. Чи можливо шахівницю розміру 8х8 обійти конем, почавши обхід з поля h8, закінчивши його на полі а1 так, щоб на кожному полі побувати рівно один раз.

 Розв’язання: За 63 ходи кінь опиниться в чорній клітинці а1, але непарні ходи коня  завжди закінчуються на білій клітинці. Протиріччя доводить неможливість.

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

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

Розв’язання: Весь квадрат 10х10 розділити на квадрати розміром 2х2 та в ньому  зафарбувати синім кольором верхню ліву клітинку. Будь-який квадрат розміром 2х2, що може бути зафарбований у чорний колір містить лише одну  зафарбовану синю клітинку. Отже, максимальна кількість зафарбованих квадратів гравцями рівна кількості синіх клітинок, а їх 25. У цій грі виграє починаючий, якщо скористається симетричною відносно центру квадрата стратегією, зафарбувавши пешим ходом  центр симетрії.

Відповідь: до 25 ходів.  

  

Задачі  для   самостійного опрацювання

Усі точки площини зафарбували в кольори веселки. Чи існує в такій площині замкнена крива лінія, що зафарбована в усі кольори веселки?

Усі одиничні квадрати координатної площини однотонно розфарбували в кольори веселки. Чи завжди існують на цій площині симетричні відносно початку координат: а)однокольорові точки; б)однокольорові відрізки; в) однокольорові одиничні квадрати?

Усі відрізки координатної площини однотонно зафарбували в два кольори. Чи завжди можна побудувати на такій площині: а)однокольоровий трикутник; б) однокольоровий чотирикутник?

Усі рівносторонні одиничні трикутники площини однотонно розфарбували в два кольори. Чи можна на такій площині отримати  правильний одиничний однокольоровий шестикутник?

Усі правильні одиничні шестикутники площини зафарбували кольорами веселки. Чи можна на такій площині побудувати правильний 12-кутник?

Усі точки координатної площини зафарбовані у два кольори. Чи можна на такій площині знайти різнокольорові вершини трикутників, що симетричні відносно початку координат?

Усі точки координатної площини зафарбовані у три кольори. Чи можна на такій площині знайти трикольорові вершини трикутників, що симетричні відносно початку координат?

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

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

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

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

Задача 2. Скількома способами можна пофарбувати в 6 кольорів грані куба.

Розв’язання: Довільну грань можна зафарбувати у перший колір. Нехай це верхня грань. Для нижньої грані маємо 5 варіантів. Довільну бічну грань можна розфарбувати  3! = 6 варіантів. І тоді перемножимо дані варіанти за правилом добутку, тримаємо 30.

Задача 3.  Як треба фарбувати кубики прямокутного паралелепіпеда розміром 3х4х3 кубики в два кольори, щоб по обидва боки кожної грані одиничного кубика були різні кольори.

Розв’язання: Фасадний прошарок  розміром 3х3х1 кубики зафарбуємо у шаховому порядку так, щоб нижній лівий кубик мав білий колір.  Наступний другий  прошарок розміром 3х3х1 кубики розфарбуємо у шаховому порядку так, щоб нижній лівий кубик мав чорний колір. Третій прошарок  розміром 3х3х1 кубики зафарбуємо у шаховому порядку так, щоб нижній лівий кубик мав білий колір.  Четвертий 

прошарок розміром 3х3х1 кубики розфарбуємо у шаховому порядку так, щоб нижній лівий кубик мав чорний колір.

    

Задачі для самостійного опрацювання

1. Усі точки простору  зафарбували в кольори веселки. Чи існує в такому  просторі замкнена крива лінія, що зафарбована в сім кольорів веселки?

2. Усі одиничні куби координатного простору однотонно розфарбували в кольори веселки. Чи завжди існують у цьому просторі симетричні відносно початку координат: а)однокольорові точки; б)однокольорові відрізки; в) однокольорові одиничні куби?

3. Усі відрізки координатного простору однотонно зафарбували в два кольори. Чи завжди можна побудувати у цьому просторі: а)однокольоровий трикутник; б) однокольоровий чотирикутник?

4. Усі правильні  одиничні тетраедри площини однотонно розфарбували в два кольори. Чи можна у цьому просторі отримати  правильний одиничний  куб?

Усі правильні одиничні куби площини зафарбували кольорами веселки. Чи можна у цьому просторі отримати правильний однокольоровий одиничний тетраедр?

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

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

   Задачі розфарбування з використанням

принципу Діріхле.

                                 

                                                      

Задача 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 вершини даної фігури.  Зрозуміло, що 24 фішки можуть утворити 24:6=4 правильних 6-кутників, тому (по одній синій фішці у кожного правильного 6-кутника) сині вершини будуть мати не більше три 6-кутника, отже. один 6-кутник буде мати червоні вершини.

                          

      

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

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

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

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

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

делегації з білої держави. Відповідь: не всі.

 Задачі на розрізання геометричних фігур.

Задача 1. Минулого року на ромбічній політичній карті зі сторонами 3 м та гострими кутами 600 було 18 однакових за площею та трикутних за формою держав, у яких усі ділянки кордонів рівні 1 м. Цього року держави утворили дві однакові за площею та шестикутні за формою федерації та декілька ромбічних за формою федерацій. Будь-які дві держави  федерації  мають суцільну ділянку кордону. Чи усі держави минулорічної політичної карти увійшли до федерацій? Яку найбільшу кількість  ромбічних та шестикутних федерацій можна утворити на минулорічній політичній карті?

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

Задача  2. Чи можна стоклітинкову  квадратну дошку розрізати на плитки розміром 1х4?

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

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

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

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

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

Задача  4. Як будь-який  трикутник  розфарбувати на найменшу кількість чотирикутників , у яких діагоналі перпендикулярні?.

Розв’язання: В середині трикутника візьмемо точку перетину бісектрис  та  проведемо від неї до кожної сторони трикутника перпендикуляри. Ці перпендикуляри рівні радіусу вписаного в трикутник кола.  Утворимо розбиття пофарбованого трикутника на три чотирикутника, тобто дельтоїда, у яких перпендикулярні

діагоналі. Менше чотирикутників  утворити не можна. Їх і необхідно перефарбувати.

Задача  5. Як будь-який  трикутник  розфарбувати на  чотири рівних між собою трикутників на найменшу кількість кольорів?

Розв’язання: В трикутнику провести три середні лінії. Отримаємо потрібне  розфарбування двома кольорами. Задача 6. Як будь-який рівнобедрений трикутник  розфарбувати на  найменшу кількість рівновеликих  між собою чотирикутників?

Розв’язання: В трикутнику з’єднати точку перетину медіан та середини сторін. Отримаємо  потрібне розфарбування трьох чотирикутників двома небілими кольорами.

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

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

Задача 8. Як розфарбувати квадрат у вісім кольорів так, щоб однокольорова ділянка була гострокутним трикутником.

Розв’язання. Проведемо вертикальну вісь симетрії УІ квадрата АВСК, яка паралельна стороні АВ. Візьмемо дві симетричні відносно цієї осі  точки М та М’  так, що трикутники АВМ та СКМ’ рівні гострокутні. З’єднаємо точки М та У , М та І, М та М’,  М’ та У,  М’ та І. Утвориться потрібних нам вісім гострокутних трикутників.

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

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

Задача 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 центр симетрії лежить всередині спільної сторони двох клітинок, і першим ходом дівчинці треба зафарбувати ці дві клітини. Далі вона повинна робити ходи, центрально – симетричні ходам хлопчика  відносно центра прямокутника.