Question

У квадраті 7×7 вставляють прямокутники розмірами 1×6 і 6×1, причому усі сторони фігур лежать на сторонах клітинок, розмір яких 1×1. Яку найменшу кількість клітинок потрібно розфарбувати у квадраті, щоб у будь-якому прямокутнику була хоча б одна зафарбована клітинка? Прямокутники можуть накладатись один на одний, прямокутники розташовуються в клітинках вертикально або горизонтально.

Answer 1

В квадрате 7x7 можно разместить только один прямоугольник размером 6x1 и только один прямоугольник размером 1x6. Для того чтобы в любом прямоугольнике была хотя бы одна закрашенная ячейка, нужно закрасить все ячейки в строках и столбцах, где находятся эти прямоугольники. Всего таких строк и столбцов 12. Ответ: 12*2=24.

Answer 2

Давайте розглянемо це завдання. Ми маємо квадрат розміром 7x7, і ми можемо вставляти прямокутники розмірами 1x6 і 6x1, так що всі сторони фігур лежать на сторонах клітинок розміром 1x1. Наша задача - знайти найменшу кількість клітинок, які потрібно розфарбувати, щоб у будь-якому прямокутнику була хоча б одна зафарбована клітинка.

Позначимо квадрати 1x6 як "A" і квадрати 6x1 як "B". Перш за все, спробуймо заповнити квадрати таким чином, щоб у них були забарвлені всі клітинки:

cssCopy code
A A A A A A A
B B B B B B B
A A A A A A A
B B B B B B B
A A A A A A A
B B B B B B B
A A A A A A A

Загальна кількість клітинок, які потрібно розфарбувати в цьому випадку, дорівнює 28 (14 клітинок типу "A" і 14 клітинок типу "B").

Тепер розглянемо ситуацію, коли ми не можемо забарвити всі клітинки. Ми маємо вставляти "A" і "B" відповідно так, щоб у будь-якому прямокутнику була хоча б одна зафарбована клітинка.

Подивімося на таку ситуацію:

cssCopy code
A A A A A A A
B B B B B B B
A A A A A A A
B B B B B B B
A A A A A A A
B B B B B B B
A A A A A A A

У цьому випадку ми можемо побачити, що ми можемо вставити ще два квадрати 1x6 типу "B" горизонтально знизу. Таким чином, всього ми маємо 16 клітинок типу "A" і 16 клітинок типу "B".

Отже, найменша кількість клітинок, які потрібно розфарбувати, щоб у будь-якому прямокутнику була хоча б одна зафарбована клітинка, - це 16 + 16 = 32 клітинки.