Аня и Боря играют в игру на клетчатом поле 9×9. За один ход Аня ставит точку в одну из свободных клеток. Боря за свой ход может сократить размеры поля с любого края, вычеркнув столбец или строку, если там находится не более 2 точек (которые ещё не были вычеркнуты). Игроки ходят по очереди, начинает Аня. Игра заканчивается, когда Боря не может сделать ход. Какое наибольшее количество клеток может остаться на поле?

Разберу игру как задачу на оптимальную стратегию: Аня старается оставить поле как можно больше, Боря — уменьшить его как можно сильнее. Главная идея будет в том, сколько точек нужно, чтобы «защитить» крайние строки и столбцы от вычеркивания.

Ответ: 30 клеток.

Обозначим через $a \times b$ поле, которое осталось в конце игры. Игра заканчивается только тогда, когда Боря уже не может вычеркнуть ни одну крайнюю строку или крайний столбец. Значит, в каждой из четырёх сторон оставшегося прямоугольника должно быть не меньше 3 точек.

То есть в конце:

• в верхней строке не меньше 3 точек;

• в нижней строке не меньше 3 точек;

• в левом столбце не меньше 3 точек;

• в правом столбце не меньше 3 точек.

Оставшийся прямоугольник не может иметь высоту меньше 3 или ширину меньше 3, иначе какой-нибудь крайний столбец или строка содержали бы не больше 2 клеток, а значит, не больше 2 точек, и Боря смог бы сделать ход.

Теперь оценим, сколько точек нужно, чтобы Боря не мог ходить. Четыре стороны вместе требуют как минимум

«попаданий» точек на стороны. Одна точка может считаться сразу для двух сторон только в углу. Углов максимум 4, значит максимум 4 точки могут быть засчитаны дважды. Поэтому реальных точек нужно не меньше

Значит, к моменту окончания игры на оставшемся поле должно быть хотя бы 8 точек.

Пусть Боря сделал $k$ ходов. Тогда Аня сделала $k+1$ ход, потому что начинает Аня, а игра заканчивается после её хода, когда Боря уже не может ходить. Следовательно, всего Аня поставила $k+1$ точку. Чтобы в конце осталось хотя бы 8 точек, нужно

то есть

Каждый ход Бори уменьшает поле либо на одну строку, либо на один столбец. Изначально поле было $9 \times 9$. Если в конце осталось поле $a \times b$, то Боря вычеркнул

строк и столбцов. Значит,

откуда

Нужно максимизировать площадь $ab$ при условии $a+b \le 11$. Максимальное произведение получается, когда числа как можно ближе друг к другу:

Больше 30 клеток остаться не может.

Осталось показать, что 30 клеток действительно могут остаться. Например, можно оставить прямоугольник $5 \times 6$. Аня ставит 8 точек на его границе так, чтобы на каждой стороне было по 3 точки: четыре точки в углах и ещё по одной точке на каждой стороне. Боря за 7 ходов вычёркивает строки и столбцы снаружи этого прямоугольника. После этого остаётся поле $5 \times 6$, и на каждой его стороне уже есть не меньше 3 точек. Поэтому Боря больше не может сделать ход.

Итак, наибольшее количество клеток, которое может остаться на поле, равно