б)  n(k – 1)  ладей можно расставить в первых  k – 1  столбцах, и тогда больше чем  k – 1  ладей выбрать невозможно.   Лемма. При  n > 1,  1 < k < n  из  n(k – 1) + 1  ладей всегда можно выбрать такую, что в её кресте – проходящих через ладью столбце и строке – стоит не более чем  n + k – 2  ладьи.

  Доказательство. Пусть этого сделать нельзя. Выберем среди всех рядов (строк и столбцов) тот, в котором ладей больше всего; обозначим их число через l. По предположению в кресте каждой из этих ладей стоит по крайней мере  n + k – 1  ладья; значит, всего ладей не меньше l(n + k – 1 – l) + l = l(n + k – l).  При этом  n + k – l ≤ l ≤ n,  откуда  l ≥ k.  Следовательно,  l(n + k – l) – nk = (n – l)(l – k) ≥ 0,  то есть

l(n + k – l) ≥ nk > n(k – 1) + 1,  если n больше единицы. Противоречие.   Докажем индукцией по n, что  m = n(k – 1) + 1  ладей достаточно. Докажем индукцией по n, что  m = n(k – 1) + 1  ладей достаточно.

  Шаг индукции. Отметим ладью, в кресте которой стоит не более чем  n + k – 2  ладьи, и вырежем её крест из доски. Из оставшихся частей составим доску (n–1)×(n–1). На новой доске будет не меньше  m – (n + k – 2) = (n – 1)(k – 2) + 1  ладей. По предположению индукции при

k > 2  можно выделить  k – 1  ладью так, что никакие две не бьют друг друга. При  k = 2  это очевидно. Добавляя к ним выбранную ранее ладью, получим нужные k ладей.   а) Возьмём  n = 10,  k = 6.  Обозначим произвольное двузначное число через  xy  (x = 1, ..., 9;  y = 0, 1, ..., 9).  Будем считать, что ладья соответствует числу  ab,  если она стоит в a-й строке и b-м столбце доски(нумерацию строк и столбцов доски начинаем с нуля; ладьи все будут размещаться даже в прямоугольнике 9×10). Две ладьи бьют друг друга тогда и только тогда, когда у соответствующих им чисел совпадают цифры в одном из разрядов. В б) доказано, что из  10·5 + 1 = 51  ладьи можно выбрать шесть таких, что никакие две не бьют друг друга.

Ответ задачи отсутствует