4. На клетчатую доску размером 100х100 поставили 1975 ладей (каждая ладья занимает одну клетку, разные ладьи стоят на разных клетках). Какое наибольшее количество пар ладей, бьющих друг друга, могло при этом получиться? Напомним, что ладья может бить на любое число клеток по горизонтали и вертикали, но не бьёт ладью, загороженную другой ладьёй.

Ответ: 3861 пара.

В одной строке, если стоит \(k\) ладей, они могут бить только соседних по этой строке ладей, потому что остальные закрыты. Значит, строка даёт не больше \(k-1\) пар. То же самое верно для каждого столбца.

Пусть занято \(R\) строк и \(C\) столбцов. Тогда общее число пар равно:

\[1975-R+1975-C=3950-(R+C)\]

Чтобы пар было как можно больше, нужно сделать \(R+C\) как можно меньше. При этом \(RC\ge 1975\). Минимально подходит \(44\cdot45=1980\), значит \(R+C=89\).

Тогда:

\[3950-89=3861\]

Такое расположение возможно: взять прямоугольник \(44\times45\) и убрать из него 5 ладей так, чтобы все строки и столбцы остались непустыми.

0 0 Пожаловаться