|
|
 |
Условие
Множество клеток на клетчатой плоскости назовем ладейно связным, если из каждой его клетки можно попасть в любую другую, двигаясь по клеткам этого множества ходом ладьи (ладье разрешается перелетать через поля, не принадлежащие нашему множеству). Докажите, что ладейно связное множество из 100 клеток можно разбить на пары клеток, лежащих в одной строке или в одном столбце.
Решение
Индукцией по n докажем утверждение задачи для любого ладейно связного множества X, состоящего из 2n клеток. Клетками далее называем клетки множества X. База (n = 1) очевидна.
Шаг индукции. Будем называть пары клеток, лежащих в одной строке или в одном столбце, доминошками. Удалим какую-нибудь доминошку, состоящую, для определенности, из клеток A и B, лежащих в одном столбце. Останется множество клеток X'. Две клетки назовём связанными в X', если от одной из них до другой можно дойти ладьёй по клеткам из X'.
Построим три ладейно связных подмножества множества X': в подмножество M включим все клетки, связанные в X' хотя бы с одной клеткой, лежащей на одной горизонтали с A; в подмножество N – связанные в X' хотя бы с одной клеткой, лежащей на одной горизонтали с B; в подмножество L – связанные в X' хотя бы с одной клеткой, лежащей на вертикали AB. Заметим, что если какие-то два из множеств M, N, L пересеклись, то они совпадают; в таком случае будем считать одно из них пустым.
Ясно, что X' = M ∪ N ∪ L. Кроме того, M остаётся связным при добавлении клетки A, N – при добавлении клетки B, а L – при добавлении любой из этих двух клеток.
Если все три множества M, N, L состоят из чётного числа клеток, применим предположение индукции к этим множествам, а потом добавим доминошку AB.
Если, скажем, в множествах M и N количества клеток нечётны, то эти множества непусты и количество клеток в каждом из них не превосходит 2n – 3, а количество клеток в множестве L чётно и не превосходит 2n – 2. Тогда можно применить предположение индукции к множествам M ∪ {A}, N ∪ {B} и L. Остальные случаи чётности разбираются аналогично.
