На шахматную доску $n \times n$ клеток уложено $k$ плиток размером $2 \times 1$, причём так, что положить $(k+1)$-ю плитку, не перемещая уже имеющихся плиток, нельзя. Докажите, что свободных клеток осталось не более чем
$\dfrac{n^2+n+1}3$;
$\dfrac{n^2+2}3$;
$\dfrac{n^2}3$.
Можно ли получить для некоторых $n$ ещё более точную оценку?
а) Сопоставим каждой свободной клетке, не лежащей на верхней горизонтали доски, плитку, «накрывающую» её сверху (рис. 1). Ясно, что каждая плитка сопоставлена не более чем одной клетке (так что количество свободных клеток, не лежащих на верхней горизонтали доски, не больше общего количества $\dfrac{n^2-x}{2}$ плиток, уложенных так, как сказано в задаче). Пусть на верхней горизонтали доски $x_1$ свободных клеток; тогда $x_1 \le \dfrac{n+1}{2}$. Имеем
$$
x-x_1 \le \dfrac{n^2-x}{2},
$$
т. е.
$$
3x \le n^2+2x_1 \le n^2+n+1,
$$
откуда
$$
x \le \dfrac{n^2+n+1}{3}.
$$
б) Обозначим через $x_1$ количество свободных клеток внутри доски, через $x_2$ количество свободных клеток на границе доски, не считая угловых клеток; наконец, через $x_3$ количество свободных угловых клеток доски. Тогда $x=x_1+x_2+x_3$. Через $y_1$ обозначим количество расположенных строго внутри доски плиток; через $y_2$ количество плиток, выходящих на края доски хотя бы одной клеткой; тогда $y_1+y_2=d\dfrac{n^2-x}{2}$.
Подсчитаем, сколько имеется пар: свободная клетка — граничащая с ней плитка. С одной стороны, их $4x_1+3x_2+2x_3$. С другой стороны, поскольку плитки уложены так, что добавить ни одной уже нельзя, этих пар не более чем $4y_1+3y_2$ (каждая плитка, выходящая на край доски, граничит не более чем с тремя клетками, а каждая плитка строго внутри доски — не более чем с четырьмя). Поэтому
$$
4x_1+3x_2+2x_3\le4y_1+3y_2.\tag1
$$
Поскольку каждые две свободные клетки на границе доски разделяются плиткой, имеем
$$
x_2+x_3\le y_2.\tag2
$$
Складывая неравенства (1) и (2), получаем
$$
4x_1+4x_2+3x_3\le4(y_1+y_2),
$$
или $$
x-\dfrac14x_3\le\dfrac{n^2-x}2.
$$
Но $x_3\le4$; значит, $x\le\dfrac{n^2-x}2+1$ или $3x\le n^2+2$, откуда $x\le \dfrac{n^2+2}3$.
Заметим, что если неравенство (1) — строгое, то мы получим то, что надо в пункте в): строгое неравенство $x\lt\dfrac{n^2-x}2+1$ равносильно такому нестрогому:
$x\le\dfrac{n^2-x}2$, откуда $x\le\dfrac{n^2}3$. Поэтому, если допустить, что $x\gt\dfrac{n^2}3$, то во всяком случае нужно, чтобы к каждой плитке обязательно прилегало максимально возможное число свободных клеток. В частности, к любой стороне плитки длины 1, не упирающейся в край доски, должна прилегать свободная клетка. Поэтому плитки должны располагаться «рядами» (рис. 2), причём «ряды» не могут ни упираться друг в друга, ни пересекаться друг с другом, поскольку и в том и в другом случае возникает картинка, изображённая на рисунке 3, — до тех пор, пока не достигнем края. Значит, все «ряды» должны быть параллельны, что возможно лишь тогда, когда $n$ делится на 3. В этом случае число плиток равно$\dfrac{n^2}3$ (соответствующий пример изображён на рисунке 4). Итак, для досок $n\times n$, где $n=3k$, оценка $\dfrac{n^2}3$ — точная.
