|
|
 |
Условие
Дан клетчатый квадрат $n\times n$, где $n$ > 1. Кроссвордом будем называть любое непустое множество его клеток, а словом – любую горизонтальную и любую вертикальную полоску (клетчатый прямоугольник шириной в одну клетку), целиком состоящую из клеток кроссворда и не содержащуюся ни в какой большей полоске из клеток кроссворда (ни горизонтальной, ни вертикальной). Пусть $x$ – количество слов в кроссворде, $y$ – наименьшее количество слов, которыми можно покрыть кроссворд. Найдите максимум отношения $\frac{x}{y}$ при данном $n$.
Решение
Пример. Для прямоугольника $n\times 2$ получаем $x = n + 2$, $y = 2$.
Оценка. Способ 1. Пусть в кроссворде $z$ клеток. Выберем некоторое его покрытие наименьшим количеством слов. Слова из этого покрытия назовём правильными, а остальные – неправильными. Каждая клетка содержится не более чем в одном горизонтальном и одном вертикальном слове. Хотя бы одно из этих слов правильное, так как правильные слова покрывают весь кроссворд. Значит, каждая клетка принадлежит не более чем одному неправильному слову. Поэтому сумма количеств клеток в неправильных словах не больше $z$. Если клетка является словом, то к ней не примыкает другая клетка кроссворда ни по горизонтали, ни по вертикали. Следовательно, клетка входит в любое покрытие кроссворда словами и, значит, является правильным словом. Поэтому все неправильные слова содержат не меньше чем по две клетки и количество неправильных слов не больше $\frac{z}{2}$. Так как правильные слова покрывают весь кроссворд, сумма количеств клеток в них не меньше $z$. Каждое слово содержит не больше $n$ клеток, поэтому количество правильных слов не меньше $\frac{z}{n}$. Отсюда $\frac{x}{y} \le 1 + \frac{z}{2} : \frac{z}{n} = 1 + \frac{n}{2}$, что и требовалось.
Способ 2. Заметим, что если есть слова длины 1, то они обязательно входят в любое покрытие кроссворда. Значит, их можно выкинуть, от этого отношение $\frac{x}{y}$ не уменьшится, поскольку $x \geq y$. Поэтому далее считаем, что все слова имеют длину не меньше 2. Построим двудольный граф, в котором вершины первой доли – это все слова кроссворда, а вершины второй доли – все занятые клетки (ребро соединяет две вершины, если слово содержит клетку). Рассмотрим те из вершин первой доли, которые насыщают всю вторую долю, пусть сумма их степеней равна $d$. При этом $d \leq ny$, поскольку степень каждой из этих вершин не больше $n$. Так как степень каждой из остальных вершин первой доли не меньше 2, то общее число рёбер в графе не меньше $d + 2(x - y)$. Во второй доле не более $d$ вершин, при этом степень каждой из них не больше 2, значит, число рёбер в графе не превосходит 2$d$. Отсюда $d + 2(x - y) \leq 2d$, то есть $2(x - y) \leq d \leq ny$, что и даёт оценку.
Ответ
1 + $\frac{n}{2}$.
