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

Проект МЦНМО
при участии
школы 57
Задача 65627
Темы:    [ Замощения костями домино и плитками ]
[ Доказательство от противного ]
[ Принцип крайнего (прочее) ]
Сложность: 4-
Классы: 5,6,7
В корзину
Прислать комментарий

Условие

Вася нарисовал карандашом разбиение клетчатого прямоугольника на прямоугольники размером 3×1 (тримино), закрасил ручкой центральную клетку каждого из получившихся прямоугольников, после чего стер карандашные линии. Всегда ли можно восстановить исходное разбиение?


Решение

  Пусть есть два разных разбиения прямоугольника, у которых совпадают закрашенные клетки. Тогда среди этих закрашенных клеток есть такие, которым в одном разбиении соответствуют вертикальной, а в другом – горизонтальной триминошке (назовем такие закрашенные клетки плохими).

  Среди плохих клеток найдём самую верхнюю (любую, если их несколько). Пусть это клетка K и в первом разбиении K покрыта вертикальной, а во втором – горизонтальной триминошкой (см. рис.). Рассмотрим клетку L – соседнюю с K сверху. Она принадлежит прямоугольнику, поскольку в первом разбиении она покрыта вертикальной триминошкой. Во втором разбиении этой триминошки нет, так что одна из клеток E1, E2, E3 – соседей L справа, слева и сверху – закрашена: это центр триминошки, покрывающей L во втором разбиении. Но в первом разбиении L покрыта не ею, так что найденная нами закрашенная клетка – плохая. Однако E1, E2 и E3 лежат выше K, что противоречит тому, как мы выбору K.


Ответ

Всегда.

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

олимпиада
Название Московская устная олимпиада для 6-7 классов
год/номер
Номер 14 (2016 год)
Дата 2016-03-20
класс
Класс 6 класс
задача
Номер 6.5

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

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