|
|
 |
Условие
Назовём квартетом четвёрку клеток на клетчатой бумаге, центры которых лежат в вершинах прямоугольника со сторонами, параллельными линиям сетки. (Например, на рисунке нарисованы три квартета.) Какое наибольшее число квартетов можно разместить в
а) квадрате 5×5;
б) прямоугольнике m×n клеток?
Решение
а) В квадрате 5×5 можно расположить пять квартетов (см. рис.). Больше пяти квартетов в нем расположить нельзя, поскольку из 5·5 = 25 клеток по крайней мере пять клеток – по одной в каждой строке – в квартеты не войдут.
б) Если m и n чётны, то очевидно, что в прямоугольнике m×n можно разместить mn/4 квартетов.
Если m чётно, а n нечётно, то можно разместить ¼ m(n – 1) квартетов (аналогичная
формула верна для нечётного m и чётного n).
Если же и m и n нечётны и m ≥ n, то надо рассмотреть два случая.
1) n = 4k + 1. В этом случае можно покрыть квартетами не более mn – m = m(n – 1) клеток.
На рис. слева показано, как это сделать: из квадрата n×n выкинута диагональ, и квартеты размещены аналогично тому, как это сделано в квадрате 5×5; из прямоугольника (m–n)×n (m – n уже чётно) выкинута нижняя строка – тогда уже в прямоугольнике k×l = (m–n)×(n–1) и k и l – чётные, и как размещать квартеты очевидно. Всего – снова ¼ m(n – 1) квартетов.
