|
|
 |
Условие
Рассматриваются покрытия шахматной доски доминошками, содержащими две соседние клетки.
Каких покрытий больше – тех, которые содержат доминошку a1-a2, или тех, которые содержат доминошку b2-b3?
Подсказка
Поставьте в соответствие каждому покрытию, содержащему доминошку b2-b3, некоторое покрытие, содержащее доминошку a1-a2.
Решение
Исключим из рассмотрения все покрытия, в которых присутствует как доминошка a1-a2, так и доминошка b2-b3. Рассмотрим оставшиеся покрытия. Назовём покрытие покрытием типа A, если оно содержит доминошку a1-a2, и покрытием типа B, если оно содержит доминошку b2-b3. Покажем, что покрытий типа A больше.
Рассмотрим некоторое покрытие типа B. Так как в нём нет доминошки a1-a2, то клетка a1 покрыта доминошкой a1-b1. Следовательно, клетка a2 может быть покрыта только доминошкой a2-a3. Итак, в покрытии типа B левый нижний угол 2×3 покрыт доминошками b2-b3, a1-b1, a2-a3. Поставим в соответствии покрытию типа B покрытие типа A, в котором левый нижний угол 2×3 покрыт доминошками a1-a2, b1-b2, a3-b3, а остальная часть доски покрыта так же, как и в исходном покрытии типа B. Итак, каждому покрытию типа B поставлено в соответствие покрытие типа A, причём различным покрытиям типа B соответствуют различные покрытия типа A. Однако покрытие типа A, состоящее только из вертикальных доминошек, не соответствует при этом никакому покрытию типа B. Таким образом, покрытий типа A больше.
Ответ
Больше тех, которые содержат доминошку a1-a2.
Источники и прецеденты использования
| web-сайт | |
| задача |
