Легко разместить комплект кораблей для игры в "Морской бой" на доске 10х10. А на какой наименьшей квадратной доске можно разместить этот комплект?

Если под полным комплектом кораблей понимать набор из кораблей с длинами от 1 до 4, включительно, размещаемых к количествах, растущих с убыванием длины (1 четырёхклеточный корабль, 2 трёхклеточных, и т.д.), то понятно, что одна из сторон поля обязана быть не меньше 4 (для размещения одного, самого большого корабля). Суммарная площадь кораблей равна 1*4+2*3+3*2+4*1=20 [клеток]. Число 20 можно представить произведением 4*5 и это даёт подходящую самую маленькую прямоугольную доску с наиплотнейшей упаковкой кораблей без зазоров (без воды!) -- вдоль наименьшей стороны можно разместить корабль о 4 клетках, прилежащую линию (строку или столбец) можно занять четырьмя одноклеточными кораблями, оставшиеся же 2 блока 3x2 можно занять двумя трёхклеточными и тремя двуклеточными кораблями, соответственно:
Нарастив это решение ещё одной водной "линией" вдоль большей стороны можно получить минимальное квадратное поле.
Итак: минимальное поле имеет размеры 4x5 (прямоугольное, с соприкасающимися кораблями) или 5x5 (квадратное, с соприкасающимися кораблями); но играть на такой доске ооочень сложно.
Если же нужны водные зазоры и кораблям запрещено соприкасаться друг с другом, то можно попробовать модифицировать имеющееся решение, просто увеличив нулевые зазоры до одноклеточных водных. Однако, в приведённой ранее конфигурации, три двуклеточные корабля как-раз помещались рядом с одним трёхклеточным, перпендикулярно ему. Теперь же один двуклеточный корабль окажется лишним, но расширившееся за счёт трёх одноклеточных водных промежутков между четырьмя одноклеточными кораблями игровое поле теперь увеличилось в размерах на три (вдоль большого корабля) и позволяет разместить этот двуклеточный корабль рядом с самым большим, соосно последнему.
Осталось заметить, что по обе стороны от ряда одноклеточных кораблей теперь тоже по одному водному зазору и, поэтому, сторона, имевшая ранее длину 5 должна удлиниться на 2. В конечном счёте должно получиться что-то вроде:
Получается, что после добавления водных зазоров, поле увеличилось до (4+3)x(5+2), т.е. до размеров 7x7 (корабли не касаются друг друга).