Презентація на тему "Розв'язування олімпіадних задач методом розфарбовування"

РОЗВ’ЯЗУВАННЯ ОЛІМПІАДНИХ ЗАДАЧ МЕТОДОМ РОЗФАРБОВУВАННЯ.

Задача 1. Яку найбільшу кількість прямокутників 4×1 можна розмістити у квадраті 6×6 (не порушуючи меж клітинок)? 

Задача 1. Яку найбільшу кількість прямокутників 4×1 можна розмістити у квадраті 6×6 (не порушуючи меж клітинок)?Розв’язання: Розфарбуємо даний квадрат у чотири різні кольори так як показано нижче. При будь-якому розміщенні прямокутника 4×1 у квадраті він буде покривати усі чотири кольори. Підрахуємо кількість клітинок кожного кольору. {5940675 A-B579-460 E-94 D1-54222 C63 F5 DA}123412234123341234412341123412234123

Задача 1. Яку найбільшу кількість прямокутників 4×1 можна розмістити у квадраті 6×6 (не порушуючи меж клітинок)?Розв’язання: Розфарбуємо даний квадрат у чотири різні кольори так як показано нижче. . При будь-якому розміщенні прямокутника 4×1 у квадраті він буде покривати усі чотири кольори. Підрахуємо кількість клітинок кожного кольору. Оскільки колір 4 зустрічається лише 8 разів, то максимально можна розмістити лише 8 прямокутників. {5940675 A-B579-460 E-94 D1-54222 C63 F5 DA}1 - 92 - 103 - 94 - 8

Задача 1. Яку найбільшу кількість прямокутників 4×1 можна розмістити у квадраті 6×6 (не порушуючи меж клітинок)?Розв’язання: Розфарбуємо даний квадрат у чотири різні кольори так як показано нижче. . При будь-якому розміщенні прямокутника 4×1 у квадраті він буде покривати усі чотири кольори. Підрахуємо кількість клітинок кожного кольору. Оскільки колір 4 зустрічається лише 8 разів, то максимально можна розмістити лише 8 прямокутників. {5940675 A-B579-460 E-94 D1-54222 C63 F5 DA}1 - 92 - 103 - 94 - 8

Задача 2. У кожній клітинці дошки 5×5 сидить жук. В деякий момент часу всі жуки переповзають у сусідні по горизонталі чи вертикалі клітинки. Доведіть, що при цьому принаймні одна клітинка залишиться порожньою. 

Задача 2. У кожній клітинці дошки 5×5 сидить жук. В деякий момент часу всі жуки переповзають у сусідні по горизонталі чи вертикалі клітинки. Доведіть, що при цьому принаймні одна клітинка залишиться порожньою. Розв’язання: Розфарбуємо дошку у шаховому порядку. Білих - 12 Чорних - 13 Переповзаючи в іншу клітинку так, як цього вимагає умова задачі, кожен жук опиниться на клітинці іншого кольору. Підрахуємо кількість клітинок кожного кольору. Жуки , які сиділи на 12 білих клітинках не зможуть зайняти 13 чорних клітинок, а тому принаймні одна клітинка залишиться вільною. {5940675 A-B579-460 E-94 D1-54222 C63 F5 DA}

Задача 3. Замок має форму рівностороннього трикутника зі стороною 36 м. Він розбитий на 16 трикутних залів зі сторонами 9 м. Між сусідніми залами є двері. Довести, що коли відвідувач захоче пройти по замку, побувавши в кожній залі не більше одного разу, то він зможе оглянути не більше 13 зал. .

Задача 4. Замок має форму рівностороннього трикутника зі стороною 36 м. Він розбитий на 16 трикутних залів зі сторонами 9 м. Між сусідніми залами є двері. Довести, що коли відвідувач захоче пройти по замку, побувавши в кожному залі не більше одного разу, то він зможе оглянути не більше 13 залів. Розв’язання: Розфарбуємо зали у два кольори. Чорних - 10, білих – 6. При переході від одного залу до іншого колір змінюється. Отже можна відвідати не більше 7 чорних і 6 білих. Всього – 13 залів. .

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

Задача 5 Задано таблицю, яка заповнена плюсами та одним мінусом. Дозволяється міняти знаки на протилежні у довільному рядку, у довільному стовпці та на довільних діагоналях або прямих, паралельних до діагоналей (зокрема, і в будь-якій кутовій клітинці). Доведіть, що в результаті таких операцій не вдається одержати таблицю, заповнену лише плюсами. Розв’язання: Розфарбуємо дану таблицю так, як показано на рисунку. Тоді кожне вищеописане перетворення або захоплює 2 клітинки чорного кольору, або жодної. Тому парність числа мінусів у зафарбованих клітинках не зміниться (це інваріант). Тобто, після будь-якого перетворення в усій таблиці лишатиметься непарна кількість мінусів., оскільки спочатку він був один. . {5940675 A-B579-460 E-94 D1-54222 C63 F5 DA}

ДЯКУЮ ЗА УВАГУ!