4.H.4 [ДОМИНО] На клетчатой доске 13×13 расположили N костяшек домино (по границам клеток). Оказалось, что каждая строка и каждый столбец покрывается хотя бы одной клеткой…
4.H.4 [ДОМИНО] На клетчатой доске 13×13 расположили N костяшек домино (по границам клеток). Оказалось, что каждая строка и каждый столбец покрывается хотя бы одной клеткой костяшки. При каком наименьшем N это возмож
Рассмотрим задачу подробнее.
Условие:
На клетчатой доске размером 13×13 разместили N костяшек домино (по границам клеток). Необходимо определить минимальное число N, при котором возможно, чтобы каждая строка и каждый столбец были покрыты хотя бы одной костяшкой.
Анализ задачи
Что означает "покрытие"?
Каждая костяшка домино занимает две соседние клетки и, соответственно, охватывает две строки и два столбца (в зависимости от того, как она расположена).Что значит "каждая строка и каждый столбец покрыты"?
Всяких строчек и столбцов — 13 штук каждое — должны содержать хотя бы одну клетку, занятых костяшками.
То есть, ни одна строка или столбец не должна остаться полностью пустой.Что требуется при минимальном N?
— Максимально эффективно разместить костяшки, чтобы минимизировать их число, но при этом гарантировать покрытие всех строк и столбцов.
Основные идеи
- Каждая костяшка занимает две соседние клетки.
- Чтобы покрыть все 13 строк, необходимо разместить достаточное количество костяшек так, чтобы в каждой строке была хотя бы одна занятая клетка.
- Аналогично — для столбцов.
Минимум костяшек для покрытия строк и столбцов
Давайте подумаем о нижней границе.
- Минимальное число чтобы покрыть все строки:
— без учета столбцов — 13 клеток, по одной в каждой строке. - Минимальное число чтобы покрыть все столбцы:
— также 13 клеток, по одной в каждом столбце.
Но при этом, каждая костяшка занимает две клетки, которые могут находиться в одной или в разных строках и столбцах.
Наибольшая эффективность размещения
Чтобы минимизировать N, нужно разместить костяшки так, чтобы они перекрывали как можно больше строк и столбцов одновременно.
Самый эффективный способ:
- Распределить костяшки так, чтобы каждое размещение покрывало сразу две разные строки и два разные столбца — то есть, чтобы костяшки были расположены по диагонали или по каким-то оптимальным схемам.
Анализ по верхней границе
Количество клеток, покрытых всеми N костяшками, равно 2N (каждая костяшка — 2 клетки).
- Общее число клеток доски: 13×13 = 169.
- Но для проверки минимальности нам нужно покрыть все 13 строк и 13 столбцов, то есть, минимум по 13 "занятых" клеток.
Нижняя граница по количеству клеток, необходимых для покрытия всех строк и столбцов, равна:
\[ \text{минимум} \geq 13 \]
Поскольку каждая костяшка покрывает две клетки, минимальное N (число костяшек):
\[ N_{\min} \geq \left\lceil \frac{13}{2} \right\rceil = 7 \]
Это — нижняя граница. То есть, даже при очень оптимальном размещении, не менее 7 костяшек потребуется, чтобы покрыть хотя бы все строки или все столбцы.
Проверка достижимости этого значения
Но вопрос — не только о покрытии строк или столбцов по отдельности, а о покрытии всех строк и всех столбцов одновременно.
Рассмотрим другой подход:
- Одних костяшек, размещённых так, чтобы каждая покрывала две строки и два столбца, недостаточно, чтобы покрыть все 13 строк и 13 столбцов одновременно, поскольку:
\[ \text{максимальное число строк} \text{ и покрываемых костяшками} = N \]
по одной костяшке на пару строк и столбцов, можно покрыть максимум 2N строк и 2N столбцов.
Для покрытия всех 13 строк и всех 13 столбцов необходимо:
\[ 2N \geq 13 \Rightarrow N \geq 7 \]
Т.к. 2×7=14, этого достаточно для покрытия 13 строк и 13 столбцов.
Но: нужно учитывать, что одна костяшка покрывает две клетки, которые могут быть в одной строке или в разных строках, а также в одном столбце или в разных столбцах.
Итог:
- Минимальное число костяшек N равно 7, так как:
\[ N \geq 7 \] и это позволяет теоретически покрывать все строки и все столбцы, если размещены оптимально.
Ответ:
\[ \boxed{ \text{Минимальное } N = 7 } \]
Это минимальное число костяшек, при котором существует возможность покрыть все 13 строк и 13 столбцов доски 13×13.
Если нужны дополнительные пояснения или более конкретное построение схемы размещения — обращайтесь!
