Методи розв'язування задач на розфарбовування

Методи розв’язування задач на розфарбування

1. У кожній клітинці дошки 5 Х5 сидить жук. У деякий момент всі жуки починають переповзати на інші сусідні клітинки по горизонталі чи по вертикалі. Чи може при цьому одна клітинка залишитися порожньою?Розфарбуємо дошку в шаховому порядку. Відповідь:одна клітинка залишиться порожньою. Шахові розфарбування

2. Чи можна квадрат розміром 10х10 замостити 25 прямокутниками розміром 1х4?Зафарбуємо дошку в чотири діагональні кольори, як на рисунку ( кольори можемо пронумерувати 1,2,3,4). Відповідь: неможливо. Застосування нешахових діагональних розфарбувань. Обчислимо кількість клітинок кожного кольору. Маємо: 1-25, 2-26, 3-25, 4-24. Якщо замощувати прямокутником 1х4, то в ньому повинні бути всі чотири кольори (або всі чотири числа 1,2,3 і 4). А ми отримали після підрахунку, що 4 - 24 клітинки. Робимо висновок, що замостити квадрат 10х10 25-ма прямокутниками 1х4 не можливо. І спосіб

2. Чи можна квадрат розміром 10х10 замостити 25 прямокутниками розміром 1х4?Зафарбуємо дошку в чотири діагональні кольори, як на рисунку ( кольори можемо пронумерувати 1,2,3,4). Відповідь: неможливо. Застосування нешахових діагональних розфарбувань. Обчислимо кількість клітинок кожного кольору. Маємо: 1-25, 2-26, 3-25, 4-24. Якщо підрахувати суму чисел записаних в таблиці, то матимемо 1х25+2 Х26+3 Х25+4 Х24=248. Якщо б було можливо замостити дану таблицю 25 прямокутниками 1х4, то сума чисел у всій таблиці дорівнювала б 25 Х(1+2+3+4)=250., що приводить до суперечності. Висновок: замостити квадрат 10х10 25 прямокутниками 1х4 не можливо. ІІ спосіб

2. Чи можна квадрат розміром 10х10 замостити 25 прямокутниками розміром 1х4?Зафарбуємо дошку в два кольори, як на рисунку. Відповідь: неможливо. Застосування нешахових діагональних розфарбуваньІІІ спосіб

2. Чи можна квадрат розміром 10х10 замостити 25 прямокутниками розміром 1х4?Зафарбуємо дошку в два кольори квадратами 2х2 в шаховому порядку, як на рисунку. Відповідь: неможливо. Шахове розфарбуванняІV спосіб. При такому розфарбуванні будь-який прямокутник розміром 1х4 розташовується на двох чорних та двох білих клітинках. Але при підрахунку кількості клітинок бачимо,що чорних клітинок -52, а білих – всього лише 48. Тому 25 прямокутників 1х4 у даному квадраті 10х10 помістити неможливо, оскільки інакше вони розташувалися б на 50 чорних та 50 білих клітинках.

2. Чи можна квадрат розміром 10х10 замостити 25 прямокутниками розміром 1х4?Зафарбуємо дошку в два кольори , як на рисунку. Відповідь: неможливо. Застосування нешахових розфарбувань. V спосіб

3. Яку мінімальну кількість «пострілів» треба зробити у морському бої, щоб гарантовано «поранити» на дощці розміром 10х10 корабель розміром 1х4?Зафарбуємо дошку в чотири діагональні кольори, як на рисунку ( кольори можемо пронумерувати 1,2,3,4). Відповідь: 24 постріли. Застосування нешахових діагональних розфарбувань. Обчислимо кількість клітинок кожного кольору. Маємо: 1-25, 2-26, 3-25, 4-24. Тоді найменша кількість однаково зафарбованих клітинок – це всі плитки 4 кольору, а їх є всього 24. Отже, варто стріляти по клітинках, зафарбованих 4-тим кольором та всього зробити як мінімум 24 постріли, щоб гарантовано «поранити» на дощці розміром 10х10 корабель розміром 1х4,.

4. Знайти, яку найбільшу кількість прямокутників розміром 1х4 можна розмістити на дошці розміром 6х6?Зафарбуємо дошку в різні кольори, як на рисунку. Відповідь: 8. Застосування нешахових діагональних розфарбувань. Бачимо, що всього прямокутників 1х4 може поміститися лише 8. Доведемо, що не можна більше. Для цього розфарбуємо дошку за номерами 1,2,3,4, як показано на рисунку. При такому розфарбуванні кольорів. Клітинок четвертого кольору є лише 8, тому і прямокутників можна розмістити не більше восьми.І спосіб

4. Знайти, яку найбільшу кількість прямокутників розміром 1х4 можна розмістити на дошці розміром 6х6?Зафарбуємо квадрат у шаховому порядку квадратами 2х2 в два кольори, як на рисунку. Відповідь: 8. Застосування нешахових діагональних розфарбувань. При такому розфарбуванні будь-який прямокутник 1х4 розташовується на двох чорних та двох білих клітинках. Але при цьому, чорних клітинок – 20, а білих клітинок – тільки 16, тому більше восьми прямокутників 1х4 у даному квадраті 6х6 помістити неможливо. ІІ спосіб

5. Із шахової дошки вирізали кутову клітинку. Чи вдасться залишок дошки замостити 21-єю плиткою розміром 1х3?Повернемо дошку так, щоб вирізана клітинка опинилася у лівому верхньому і починаючи з неї розфарбуємо дошку у три кольори, як на рисунку. Відповідь: неможливо. Застосування нешахових діагональних розфарбувань. При такому розфарбуванні отримали клітинок першого кольору – 20, а другого – 22, третього -21. Тому на 21-ій плитці повинно бути всіх кольорів однаково, а в нас виходить суперечність, що неможливо.

6. Чи можна шахову дошку розміром 8х8 замостити 11 прямокутниками розміром 1х4 та 5 квадратами 2х2?Зафарбуємо дошку в три діагональні кольори, як на рисунку ( кольори можемо пронумерувати 1,2,3). Відповідь: неможна. Застосування нешахових діагональних розфарбувань. Сума всіх чисел у таблиці дорівнює 96. Кожний квадрат покриває суму, яка дорівнює 4 або 8. Кожний прямокутник покриває суму, яка дорівнює 6. Таких прямокутників повинно бути 11 та вони повинні покрити суму 66. Оскільки сума всіх чисел у таблиці дорівнює 96, 11 прямокутників розміром 1х4 покривають суму 66, то 5 квадратів 2х2 повинно покрити суму 96-66=30. Сума 30 повинна ділитися на 4 або на 8, але 30 не ділиться ні на 4, ні на 8. Отже, шахову дошку розміром 8х8 замостити 11 прямокутниками розміром 1х4 та 5 квадратами 2х2 неможна.

7. Доведіть, що дошку розміром 10х10 не можна покрити 25-ма плитками виду . Заповнимо дану дошку у шаховому порядку числами 1 та -1 так як показано на рисунку. Відповідь: неможна. Застосування розфарбування числами. Помічаємо, що на таблиці 1 і -1 однаково, по 50. Тоді добуток всіх чисел таблиці дорівнює 150·(-1)50=1. Розфарбування фігури виду можливе одне із двох способів або або протилежних способів. Добуток чисел на кожній з таких фігурок дорівнює -1 і на 25-ти таких фігурках, також буде -1, а в нас добуток всіх чисел таблиці дорівнює 1. Ми прийшли до суперечності. Отже, шахову дошку розміром 10х10 покрити 25-ма фігурками неможна. І спосіб

7. Доведіть, що дошку розміром 10х10 не можна покрити 25-ма плитками виду . Зафарбуємо дану дошку у шаховому порядку чорним та червоним кольором, як показано на рисунку. Відповідь: неможна. Застосування розфарбування числами. Помічаємо, що на таблиці 50 чорних і 50 червоних клітинок. Кожна фігурка містить або 1 або 3 чорні клітинки, тобто непарне число. Самих же фігурок повинно поміститися 100:4=25 штук. Тому вони містять непарне число чорних клітинок (добуток двох непарних чисел є число непарне), але всього на таблиці чорних клітинок 50, тобто парна кількість. Ми прийшли до суперечності. Отже, шахову дошку розміром 10х10 покрити 25-ма фігурками неможна. ІІ спосіб

8. Чи можна шахову дошку замостити п’ятнадцятьма плитками виду А і однією плиткою виду Б ? (Якщо одна клітинка плитки покриває одну клітинку шахової дошки.)Застосуємо таке розфарбування шахової дошки: червона смуга, біла смуга. Отримаємо:32 білі клітинки і 32 червоні клітинки. Відповідь: неможна. Застосування розфарбування числами. Тоді плитка виду Б покриває на будь-якій ділянці 2 білі й 2 червоні клітинки. Фігура виду А на будь-якій ділянці покриває непарне число червоних клітинок і непарне число білих клітинок. Додавання однієї фігури виду Б нічого не змінить, тобто в підсумку на шаховій дошці має бути покрите непарне число червоних клітинок. Але на шаховій дошці 32 білі й 32 червоні клітинки. Таким чином, покрити шахову дошку даними плитками неможливо. Отже, шахову дошку розміром 8х8 покрити 15-ма фігурками виду та однією фігуркою неможливо. БА

Дякую за увагу.