Question

Укажите периметр наименьшего по площади прямоугольного клетчатого поля, стороны которого не меньше 6, на котором можно по линиям сетки разместить 12 не соприкасающихся между собой кораблей 1×4

Answer 1

легко, 72 же........

Answer 2

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

Заметим, что каждый корабль 1x4 занимает 4 клетки. Так как на поле не должно быть соприкасающихся кораблей, то между любыми двумя кораблями должно быть хотя бы одна свободная клетка. Значит, на каждые 5 клеток вдоль стороны поля может быть размещен только один корабль.

Рассмотрим случай, когда сторона прямоугольника поля равна 6 клеткам. Тогда вдоль каждой стороны поля можно разместить по одному кораблю, всего получится 4 корабля. Это меньше, чем требуется, значит, сторона поля должна быть больше 6.

Рассмотрим случай, когда сторона поля равна 7 клеткам. Тогда вдоль каждой стороны поля можно разместить по одному кораблю, а еще два корабля можно разместить вдоль диагоналей поля. Всего получится 6 кораблей. Это все еще меньше, чем требуется, значит, сторона поля должна быть больше 7.

Рассмотрим случай, когда сторона поля равна 8 клеткам. Тогда вдоль каждой стороны поля можно разместить по одному кораблю, а еще два корабля можно разместить вдоль диагоналей поля таким образом, чтобы они не пересекались с уже размещенными кораблями. Всего получится 8 кораблей. Это уже достаточно, значит, периметр наименьшего по площади прямоугольного клетчатого поля, на котором можно разместить 12 не соприкасающихся между собой кораблей 1x4, равен 2*(8+1) = 18 клеткам.