Разделы 
Дополнительно
Задача по математике - 2686
2019-04-01 
Какое наибольшее число ладей можно расставить на доске $m \times n$ так, чтобы каждая била не более двух других? (Если три ладьи стоят на одной горизонтали или вертикали, то крайние не бьют друг друга.)
Решение:
Первое решение. Посчитаем общее число ладей, которых бьёт ладья, обходящая доску по периметру (рис.). Их не более чем $2(m+n)$. При этом каждую из стоящих на доске ладей мы посчитали по крайней мере дважды. Поэтому число ладей на доске не более $m+n$.
Пример расстановки $m + n$ ладей показан на рис.
Второе решение. Докажем индукцией по $k = m + n$, что на доске размера $m \times n$ можно расставить не более $m + n$ ладей, чтобы каждая из них била не более двух других.
База индукции. Для досок размера $1 \times n$ и $2 \times 2$ это утверждение не вызывает сомнений.
Индукционный переход. Предположим, что мы уже доказали утверждение для досок $m \times n$ с $m + n \leq k$. Возьмём теперь некоторую доску $m \times n$ ($m$ строк и $n$ столбцов) с $m + n = k + 1$. Для определённости будем считать, что $m \leq n$.
Выберем строку, в которой стоят по крайней мере три ладьи (такая строка обязательно существует, поскольку иначе общее число ладей не превосходило бы $2m \leq m + n$). Рассмотрим столбец, содержащий среднюю из этих ладей (или одну из средних), рис. В этом столбце не может стоять более ни одной ладьи, поскольку в противном случае одна из ладей била бы более двух ладей. Удалим этот столбец, «схлопнув» доску. Мы получим доску размером $m \times (n- 1)$, на которой, согласно предположению индукции, стоит не более $m + n - 1$ ладей. Значит, на исходной доске их было не более $m + n$.
Какое наибольшее число ладей можно расставить на доске $m \times n$ так, чтобы каждая била не более двух других? (Если три ладьи стоят на одной горизонтали или вертикали, то крайние не бьют друг друга.)
Решение:
Первое решение. Посчитаем общее число ладей, которых бьёт ладья, обходящая доску по периметру (рис.). Их не более чем $2(m+n)$. При этом каждую из стоящих на доске ладей мы посчитали по крайней мере дважды. Поэтому число ладей на доске не более $m+n$.
Пример расстановки $m + n$ ладей показан на рис.
Второе решение. Докажем индукцией по $k = m + n$, что на доске размера $m \times n$ можно расставить не более $m + n$ ладей, чтобы каждая из них била не более двух других.
База индукции. Для досок размера $1 \times n$ и $2 \times 2$ это утверждение не вызывает сомнений.
Индукционный переход. Предположим, что мы уже доказали утверждение для досок $m \times n$ с $m + n \leq k$. Возьмём теперь некоторую доску $m \times n$ ($m$ строк и $n$ столбцов) с $m + n = k + 1$. Для определённости будем считать, что $m \leq n$.
Выберем строку, в которой стоят по крайней мере три ладьи (такая строка обязательно существует, поскольку иначе общее число ладей не превосходило бы $2m \leq m + n$). Рассмотрим столбец, содержащий среднюю из этих ладей (или одну из средних), рис. В этом столбце не может стоять более ни одной ладьи, поскольку в противном случае одна из ладей била бы более двух ладей. Удалим этот столбец, «схлопнув» доску. Мы получим доску размером $m \times (n- 1)$, на которой, согласно предположению индукции, стоит не более $m + n - 1$ ладей. Значит, на исходной доске их было не более $m + n$.
