Разделы 
Дополнительно
Задача по математике - 505
2014-06-08 
Какое наибольшее число ладей можно расставить на шахматной доске размером $3n \times 3n$ так, чтобы каждая из них находилась под ударом не более одной из остальных?
Решение:
Пусть каждая ладья на доске находится под ударом не более одной из остальных. Тогда можно выделить несколько пар ладей так, что ладьи в каждой паре бьют друг друга и не бьют ни одной из остальных, а все ладьи, не объединенные в пары, вообще ничего не бьют. Пусть количество указанных пар ладей равно A, а количество одиночных ладей равно B. Общее количество горизонталей и вертикалей на доске $3n \times 3n$ равно $6n$. Из них каждая пара ладей, бьющих друг друга, занимает три линии (две горизонтали и вертикаль или две вертикали и горизонталь), на которых уже не могут стоять никакие другие ладьи, а каждая одиночная ладья занимает две линии (вертикаль и горизонталь), отсюда $3A + 2B \leq 6n$. Поэтому для количества ладей справедлива оценка:
$2A + B \leq (2/3) (3A + 2B) \leq (2/3) \cdots 6n = 4n$.
С другой стороны, $4n$ ладей на доске расставить можно, например, так, как показано на рис. (закрашены в черный цвет те клетки, в которых должны стоять ладьи). Таким образом, наибольшее количество ладей равно $4n$.
Какое наибольшее число ладей можно расставить на шахматной доске размером $3n \times 3n$ так, чтобы каждая из них находилась под ударом не более одной из остальных?
Решение:
Пусть каждая ладья на доске находится под ударом не более одной из остальных. Тогда можно выделить несколько пар ладей так, что ладьи в каждой паре бьют друг друга и не бьют ни одной из остальных, а все ладьи, не объединенные в пары, вообще ничего не бьют. Пусть количество указанных пар ладей равно A, а количество одиночных ладей равно B. Общее количество горизонталей и вертикалей на доске $3n \times 3n$ равно $6n$. Из них каждая пара ладей, бьющих друг друга, занимает три линии (две горизонтали и вертикаль или две вертикали и горизонталь), на которых уже не могут стоять никакие другие ладьи, а каждая одиночная ладья занимает две линии (вертикаль и горизонталь), отсюда $3A + 2B \leq 6n$. Поэтому для количества ладей справедлива оценка:
$2A + B \leq (2/3) (3A + 2B) \leq (2/3) \cdots 6n = 4n$.
С другой стороны, $4n$ ладей на доске расставить можно, например, так, как показано на рис. (закрашены в черный цвет те клетки, в которых должны стоять ладьи). Таким образом, наибольшее количество ладей равно $4n$.
