ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 73794
Темы:    [ Замощения костями домино и плитками ]
[ Деление с остатком ]
[ Четность и нечетность ]
Сложность: 4
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

Назовём квартетом четвёрку клеток на клетчатой бумаге, центры которых лежат в вершинах прямоугольника со сторонами, параллельными линиям сетки. (Например, на рисунке нарисованы три квартета.) Какое наибольшее число квартетов можно разместить в
  а) квадрате 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  – оба чётные).

Источники и прецеденты использования

журнал
Название "Квант"
год
Год 1974
выпуск
Номер 4
Задача
Номер М259

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .