4.H.4 [ДОМИНО] На клетчатой доске 13×13 расположили N костяшек домино (по границам клеток). Оказалось, что каждая строка и каждый столбец покрывается хотя бы одной клеткой костяшки. При каком наименьшем N это возмож

Рассмотрим задачу подробнее. **Условие:** На клетчатой доске размером 13×13 разместили N костяшек домино (по границам клеток). Необходимо определить минимальное число N, при котором возможно, чтобы каждая строка и каждый столбец были покрыты хотя бы одной костяшкой. --- ### Анализ задачи 1. **Что означает "покрытие"?** Каждая костяшка домино занимает две соседние клетки и, соответственно, охватывает две строки и два столбца (в зависимости от того, как она расположена). 2. **Что значит "каждая строка и каждый столбец покрыты"?** Всяких строчек и столбцов — 13 штук каждое — должны содержать хотя бы одну клетку, занятых костяшками. То есть, ни одна строка или столбец не должна остаться полностью пустой. 3. **Что требуется при минимальном 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. --- Если нужны дополнительные пояснения или более конкретное построение схемы размещения — обращайтесь!