Высшая проба 2026, 8 класс, задача 6
( балла) У Миши есть клетчатая доска и полных наборов кораблей для игры в морской бой (каждый набор содержит один корабль в виде прямоугольника , два , три и четыре ). Он хочет разместить корабли из этих наборов на доске по правилам морского боя (никакие два различных корабля не соприкасаются стороной или углом) таким образом, чтобы суммарное число клеток, покрытых кораблями, было наибольшим. Какое наибольшее количество клеток сможет покрыть Миша?
Ответ. клеток.
Решение. Оценка. Заметим, что у доски всего узлов (вершин клеток). Также заметим, что раз корабли не касаются друг друга даже углами, каждый узел покрыт не более, чем кораблем. В силу того, что каждый корабль накрывает четное число узлов, всего будет покрыто не более узлов.
Предположим, что корабли размещены на доске по правилам. Запишем по числу в каждый из узлов: в каждый узел, не накрытый никаким кораблем, в каждый узел одноклеточного корабля, в каждый узел двуклеточного корабля, в каждый узел трехклеточного корабля, в каждый узел четырехклеточного корабля. Нетрудно видеть, что сумма чисел в узлах равна общему количеству клеток, покрытых кораблями. Как уже было показано выше, по крайней мере узел будет содержать ноль. Четырехклеточных кораблей у нас всего , поэтому не более чем в узлов будет записано число , а в оставшиеся узлы будет записано число, не превышающее . Так как , сумма всех чисел не превысит , а значит, всего будет покрыто не более клеток.
Пример. Покажем, что можно покрыть ровно клеток пользуясь таким набором. Разрежем полоску на трехклеточных кораблей и на четырехклеточных корабля, после чего послойно составим из таких полосок прямоугольник и изготовим два таких прямоугольника. Аналогично, разрежем полоску на трехклеточных корабля и на четырехклеточных кораблей, после чего послойно составим из таких полосок прямоугольник и изготовим два таких прямоугольника. Разместим этих прямоугольника «спиралью» вокруг одного центрального узла в квадрате - тогда все узлы, кроме центрального, будут заняты, всего будет ровно трехклеточных кораблей и ровно четырехклеточных кораблей, то есть, покрыто ровно клеток. (Ниже показаны полоски, из которых нужно составить прямоугольники и показан пример аналогичной «спирали» из прямоугольников в квадрате ; покрыты все узлы, кроме центрального, отмеченного красным).
Верная оценка на 3950 и корректный пример на 3950 клеток. Баллы за критерии с литерой П суммируются с критериями с литерой О, но не более чем наБаллы за критерии с одной литерой не суммируются.
О1. Только верная оценка на 3950 клеток.
О2. Оценка с ошибкой, в том числе оценка, не доведённая до конца, но с верной идеей.
П1. Пример на 3950 клеток.
П2. Пример на не менее чем 3940 и не более чем 3949 клеток.
П3. Пример на не менее чем 3851 и не более чем 3939 клеток.
П4. Пример на 3850 клеток.