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

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

Условие

Автор: Фольклор

Имеется прямоугольная доска m×n, разделённая на клетки 1×1. Кроме того, имеется много косточек домино размером 1×2. Косточки уложены на доску, так что каждая косточка занимает две клетки. Доска заполнена не целиком, но так, что сдвинуть косточки невозможно (доска имеет бортики, так что косточки не могут выходить за пределы доски). Докажите, что число непокрытых клеток
  а) меньше  mn/4;
  б) меньше  mn/5.


Решение

  a) Заметим, что столбец не может состоять из пустых клеток: ближайшую к такому столбцу доминошку можно сдвинуть. Докажем, что даже две пустые клетки рядом стоять не могут. Пусть такие нашлись, например, одна над другой. Будем "идти" по пустым клеткам вверх и вниз, пока не упрёмся с одной из сторон (пусть вверху) в доминошку. Если её нельзя сдвинуть вниз, то она горизонтальна, и под ее второй клеткой есть другая доминошка. Эту последнюю можно сдвинуть в сторону нашей группы пустых клеток.
  Теперь ясно, что пустая клетка не может оказаться на границе прямоугольника: одна из трёх (двух для угловой клетки) соседних доминошек может быть сдвинута.
  Ни в одном из квадратов 2×2 этого прямоугольника не может оказаться более одной пустой клетки. Действительно, согласно доказанному выше в таком квадрате две пустые клетки могут стоять только по диагонали, а две оставшиеся клетки должны быть заняты. Но тогда доминошка, которой принадлежит занятая клетка, сдвигается.
  Разобьём теперь весь прямоугольник на квадраты 2×2, оставив на краю одну или две горизонтальные полоски высоты 1 и, возможно, одну вертикальную полоску ширины 1. В этих полосках пустых клеток нет, а в квадратах их не больше четверти. Таким образом, пустых клеток меньше  mn/4.

  б) Из а) следует, что каждая пустая клетка "окружена" четырьмя доминошками. Но две пустые клетки (a и b), разделённые одной клеткой (см. рис.), одновременно окружить нельзя. Значит, таких положений нет.

  Добавим к каждой пустой клетке четыре соседних. Из вышеизложенного следует, что полученные кресты из пяти клеток не пересекаются и не выходят за пределы доски. Но они не покрывают угловых клеток, поэтому число крестов (т.е. число пустых клеток) меньше  mn/5.

Замечания

баллы: 2 + 4

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

олимпиада
Название Турнир городов
Турнир
Дата 1989/1990
Номер 11
вариант
Вариант осенний тур, основной вариант, 8-9 класс
Задача
Номер 5

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

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