Разделы 
Дополнительно
Задача по математике - 1627
2019-01-20 
Множество клеток на клетчатой плоскости назовем ладейно связным, если из любой его клетки можно попасть в любую другую, двигаясь по клеткам этого множества ходом ладьи (ладье разрешается перелетать через поля, не принадлежащие нашему множеству). Докажите, что ладейно связное множество из 100 клеток можно разбить на пары клеток, лежащих в одной строке или в одном столбце.
Решение:
Индукцией по $n$ докажем утверждение задачи для любого ладейно связного множества $X$, состоящего из $2n$ клеток. База $(n =1)$ очевидна.
Клетками далее называем клетки множества $X$. Будем называть пары клеток, лежащих в одной строке или в одном столбце, доминошками. Удалим какую-нибудь доминошку, состоящую, для определенности, из клеток $A$ и $B$, лежащих в одном столбце, получим множество клеток $X^{ \prime}$. Две клетки назовем связанными в $x^{ \prime}$, если от одной из них до другой можно дойти ладьей по клеткам из $X^{ \prime}$. Покажем, что $X^{ \prime}$ распадается не более чем на три ладейно связных подмножества $M, N, L$, первое из которых остается связным при добавлении клетки $A$, второе - при добавлении клетки $B$, а третье - при добавлении любой из этих двух клеток (возможно, некоторые из множеств $M, N, L$ пусты). Действительно, в множество $M$ включим все клетки, связанные в $X^{ \prime}$ хотя бы с одной клеткой, лежащей на одной горизонтали с $A$; в множество $N$ - связанные в $X^{ \prime}$ хотя бы с одной клеткой, лежащей на одной горизонтали с $B$; в множество $L$ - связанные в $X^{ \prime}$ хотя бы с одной клеткой, лежащей на вертикали $AB$. Заметим, что если какие-то два из множеств $M, N, L$ пересеклись, то они совпадают; в таком случае будем считать одно из них пустым.
Если все три множества $M, N, L$ состоят из четного числа клеток, удалим доминошку $AB$ и применим предположение индукции к этим множествам. Если, скажем, в множествах $M$ и $N$ количества клеток нечетны, то эти множества непусты и количество клеток в каждом из них не превосходит $2n - 3$, а количество клеток в множестве $L$ четно и не превосходит $2n - 2$. Тогда можно применить предположение индукции к множествам $M \cup \{ A \}, N \cup \{B \}$ и $L$. Остальные случаи четности разбираются аналогично.
Множество клеток на клетчатой плоскости назовем ладейно связным, если из любой его клетки можно попасть в любую другую, двигаясь по клеткам этого множества ходом ладьи (ладье разрешается перелетать через поля, не принадлежащие нашему множеству). Докажите, что ладейно связное множество из 100 клеток можно разбить на пары клеток, лежащих в одной строке или в одном столбце.
Решение:
Индукцией по $n$ докажем утверждение задачи для любого ладейно связного множества $X$, состоящего из $2n$ клеток. База $(n =1)$ очевидна.
Клетками далее называем клетки множества $X$. Будем называть пары клеток, лежащих в одной строке или в одном столбце, доминошками. Удалим какую-нибудь доминошку, состоящую, для определенности, из клеток $A$ и $B$, лежащих в одном столбце, получим множество клеток $X^{ \prime}$. Две клетки назовем связанными в $x^{ \prime}$, если от одной из них до другой можно дойти ладьей по клеткам из $X^{ \prime}$. Покажем, что $X^{ \prime}$ распадается не более чем на три ладейно связных подмножества $M, N, L$, первое из которых остается связным при добавлении клетки $A$, второе - при добавлении клетки $B$, а третье - при добавлении любой из этих двух клеток (возможно, некоторые из множеств $M, N, L$ пусты). Действительно, в множество $M$ включим все клетки, связанные в $X^{ \prime}$ хотя бы с одной клеткой, лежащей на одной горизонтали с $A$; в множество $N$ - связанные в $X^{ \prime}$ хотя бы с одной клеткой, лежащей на одной горизонтали с $B$; в множество $L$ - связанные в $X^{ \prime}$ хотя бы с одной клеткой, лежащей на вертикали $AB$. Заметим, что если какие-то два из множеств $M, N, L$ пересеклись, то они совпадают; в таком случае будем считать одно из них пустым.
Если все три множества $M, N, L$ состоят из четного числа клеток, удалим доминошку $AB$ и применим предположение индукции к этим множествам. Если, скажем, в множествах $M$ и $N$ количества клеток нечетны, то эти множества непусты и количество клеток в каждом из них не превосходит $2n - 3$, а количество клеток в множестве $L$ четно и не превосходит $2n - 2$. Тогда можно применить предположение индукции к множествам $M \cup \{ A \}, N \cup \{B \}$ и $L$. Остальные случаи четности разбираются аналогично.
