Question

На шахматной доске расположено несколько ладей. Ладьи атакуют друг друга, если стоят на одной линии (горизонтали или вертикали) и между ними нет других ладей. Для каждой ладьи посчитали количество атакованных ею ладей. Пусть m - наименьшее из найденных чисел. Ясно, что m - характеристика расстановки. Каково наибольшее возможное значение m, если рассматривать все возможные расстановки?

Answer 1

Во-первых, это задача просто о ладьях, а не о реальной партии.
На доске можно поставить и пуговицы, только договориться, что каждая бьет как ладья, по горизонтали и по вертикали.
Поэтому их может быть сколько угодно, хоть все 64.
Ладья бьет ладьи, которые стоят с ней на одной вертикали или горизонтали, но только ближайшие.
Максимум ладья может бить 4 ладьи. Например, d5 бьет d1, d8, a5, e5.
Но, если поставить ладьи d4 и c5, то d5 уже не будет бить d1 и a5.
Минимум, естественно равен 0. Например, если 8 ладей стоят на одной диагонали a1 - h8 или a8 - h1, то каждая не бьет ни одной ладьи.
Найдем наибольший из таких минимумов.
Пусть на доске стоит несколько ладей.
Найдем самый левый столбец, содержащий ладью.
В этом столбце найдем самую верхнюю.
Слева и сверху от нее ладей нет, поэтому она бьет максимум 2 ладьи - одна снизу и одна справа.
Например, ладья a6 бьет a5 и d6.
Точно также, найдем самую верхнюю строку, содержащую ладью.
В этой строке найдем самую левую.
Например, ладья b8 бьет b6 и d8.
Таким образом, наибольший из минимумов m = 2.

Answer 2

Наибольшее возможное значение m будет достигаться в случае, когда все ладьи будут расположены на одной горизонтали или вертикали. В таком случае каждая ладья будет атаковать все остальные ладьи, кроме себя самой, и количество атакованных ладей для каждой из них будет равно n-1, где n - общее количество ладей на доске.

Таким образом, наибольшее возможное значение m будет равно n-1.