Question

Дно ящика представляет собой таблицу 8×8. Какое наименьшее ненулевое число плиток 2×1 или 1×2 можно расположить на дне ящика так, чтобы ни одну плитку нельзя было подвинуть ни по горизонтали, ни по вертикали? Каждая плитка должна занимать ровно две клетки, не занятые другими плитками.

Answer 1

32 плитки потому что 8*8/1/2=32

Answer 2

Для решения этой задачи можно использовать метод отображения графа.

В начале мы можем заметить, что нам нужно разместить 32 плитки на дне ящика. Если мы представим каждую клетку на дне ящика в виде вершины графа, то каждая плитка займет две вершины. Тогда мы можем создать граф из 64 вершин и соединить вершины ребрами, если они находятся рядом друг с другом.

Теперь мы можем заметить, что каждое ребро графа соединяет вершины разных цветов, поскольку они находятся в разных рядах или столбцах. Поскольку мы хотим расположить плитки таким образом, чтобы никакая плитка не могла быть подвинута ни по горизонтали, ни по вертикали, мы должны раскрасить граф в два цвета таким образом, чтобы каждое ребро соединяло вершины разных цветов.

Мы можем использовать метод двудольной раскраски для решения этой задачи. В двудольной раскраске графа вершины разбиваются на две группы (две доли), так что ребра соединяют вершины из разных долей.

В нашем случае мы можем разбить вершины на две доли: белую и черную. Тогда мы можем раскрасить граф в два цвета, используя методы двудольной раскраски.

Оказывается, что минимальное количество плиток 2×1 или 1×2, необходимых для заполнения дна ящика таким образом, чтобы никакую плитку нельзя было подвинуть ни по горизонтали, ни по вертикали, равно 32. Это означает, что мы можем разместить 16 плиток 2×1 и 16 плиток 1×2 таким образом, чтобы никакую плитку нельзя было подвинуть ни по горизонтали, ни по вертикали.