Назад
Задача

Назовём квартетом четвёрку клеток на клетчатой бумаге, центры которых лежат в вершинах прямоугольника со сторонами, параллельными линиям сетки. (Например, на рисунке нарисованы три квартета.) Какое наибольшее число квартетов можно разместить в

  а) квадрате 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–nn  (m – n  уже чётно) выкинута нижняя строка – тогда уже в прямоугольнике  k×l = (m–n)×(n–1)  и k и l – чётные, и как размещать квартеты очевидно. Всего – снова  ¼ m(n – 1)  квартетов.

  2)  n= 4k+ 3.  В этом случае  m(n– 1)  клеток покрыть квартетами не удастся, поскольку число  m(n– 1)  не делится на 4. Зато  m(n– 1) – 2  клетки покрыть уже можно – как именно, показано на рис. справа: выкинуты  m+ 2  заштрихованные клетки:  n– 2  – на диагонали квадрата  (n–2)×(n–2), m – n+ 2 – в правой части нижней строки исходного прямоугольника, и две клетки – в левом верхнем углу  (n– 3  делится на 4,  m – n+ 2  и  n– 1  – оба чётные).
Ответ

Ответ задачи отсутствует

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет