Вариант боев 4 (10)

Ответ: 49 пешек.

Решение. Докажем, что после того, как все пешки расставлены, на каждой горизонтали обязательно останется хотя бы одна пустая клетка. Действительно, если бы какая-то горизонталь заполнена полностью, то последняя поставленная на нее пешка, была бы установлена не по правилам. Аналогично на каждой вертикали должна остаться хотя бы одна пустая клетка.

Заметим, что если в любой момент поменять местами любые две строки или любые два столбца, то прямоугольник с вершинами в центрах четырех клеток со сторонами, параллельными сторонам доски, таковым же и останется. Поэтому можно произвольно переставлять столбцы или строки, не влияя на окончательное число пустых полей.

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

Допустим противное: что среди оставшихся пустых полей есть два поля, от каждого из которых нельзя перейти ко второму ходами ладьи по пустым полям. Возьмем одно из них, а также все пустые поля, к которым можно от него перейти ходами ладьи. Теперь переставим горизонтали доски так, чтобы вся эта группа пустых полей заняла самые нижние несколько горизонталей (возможно, одну). После этого переставим вертикали доски так, чтобы эта же группа заняла самые левые несколько столбцов. Таким образом, данная группа пустых полей расположена в некоторой прямоугольной области A (показано на рисунке), причем в каждой вертикали и каждой горизонтали области A находится хотя бы одна пустая клетка из этой группы. Тогда в прямоугольных областях B и C не должно быть пустых клеток. Действительно, для любой пустой клетки этих областей найдется пустая клетка области A, лежащая с ней на одной горизонтали и вертикали, и, следовательно, такая клетка области B или C должна была бы принадлежать той же группе пустых полей, которые лежат в области A. Поэтому все остальных пустые клетки лежат в области D. Области же B и C целиком заполнены пешками.

Рассмотрим последнюю пешку, которая была поставлена в областях B или C. Чтобы ее поставить, нужно выбрать прямоугольник с вершинами в четырех свободных клетках. Нетрудно убедиться, что ровно две из них должны лежать в областях B и C (по одной в каждой). Но в этих областях имеется лишь одна свободная клетка. Противоречие.

Будем расставлять в пустые клетки крестики (по одному), и каждую вертикаль или горизонталь, в которой еще нет крестика, назовем живой, а ту, в которой крестик уже поставлен — убитой.

Первоначально имеется всего 16 живых горизонталей и вертикалей. Поставим крестик в любую пустую клетку. При этом будут убиты одна горизонталь и одна вертикаль, то есть останутся живыми всего 14 горизонталей и вертикалей. Далее будем ставить по одному крестики на клетки, которые “связаны” с клетками, где крестики уже поставлены, ходами ладьи. После установки каждого такого крестика общее число живых вертикалей и горизонталей уменьшится не более чем на один. После расстановки всех крестиков должны быть убиты все горизонтали в вертикали, так как на каждой из них имеется пустое поле. Таким образом, после первого крестика надо поставить еще не меньше 14 крестиков, а всего — не меньше 15. Значит, после расстановки пешек должно остаться не менее 15 пустых полей, поэтому количество расставленных пешек не превышает 64 – 15 = 49. С другой стороны, расставить ровно 49 пешек можно. Например, оставляя пустыми все поля первой горизонтали и первой вертикали, можно поставить пешку на любую из оставшихся 49 клеток.

Автор задачи — И. Акулич