Головоломка недели: игра «Морской бой»

Тебя ждет веселье: надо уместить на поле морского боя максимальное число кораблей.

Напоминаем, что такое «Морской бой» для тех, кто в танке (поэтому ни разу не бывал на флоте). Классическая игра предполагает, что ты начертил поле 10х10 клеток и разместил в нем 10 кораблей. Один четырехклеточный, два трехклеточных, три двухклеточных и четыре одноклеточных (как амеба).

Задача

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

8 кораблей по одной клетке, 6 по 2 клетки, 4 по 3 клетки и два 4-клеточных.

Вопрос

Уместится ли удвоенное число кораблей на стандартном поле со стандартными правилами расстановки (то есть суда не будут соприкасаться друг с дружкой)?

Решать разрешено любым методом: или произвести математические расчеты, или просто взять ручку и начать перебирать варианты.

Ответ будет дан в самом конце статьи. Но только тем из читателей, кто хорошо себя вел.

Ответ

Математически можно себе представить масштабы эскадры. Каждое судно занимает не только свои клетки, но и отнимает несколько соседних, чтобы не соприкасаться с другими кораблями. Назовем эти промежуточные клетки «личным пространством».

На поле у нас 10 столбцов и 10 строк. То есть 100 клеток, которые могут занимать корабли. А вот личное пространство у каждого корабля добавляется лишь с двух сторон — например, справа и снизу. Так как другие две стороны — это личное пространство уже другого корабля-соседа (это очень важно!).

Посмотри. 1-клеточный корабль отнимает 4 клетки, 2-клеточный — 6 клеток, 3-клеточный — 8 клеток, 4-клеточный — 10 клеток.

(8*4)+(6*6)+(4*8)+(2*10)=120. Итого для удвоенной эскадры понадобится 120 клеток. Но это еще не все…

Корабль со своим личным пространством

Так как личное пространство можно добавить справа и снизу к крайнему кораблю, и оно может вылезти за пределы поля, то у нас по факту поле не 10 на 10 клеток, а 11 на 11. Ура, в нашем распоряжении 121 клетка! А надо 120. Неужели задача решена и останется даже одна лишняя клетка?

Нет. Запас в одну клетку оказывается слишком мал для того, чтобы скомбинировать строй из кораблей разной длины с четными и нечетными сторонами. Что и демонстрирует картинка с максимально возможным наполнением:

Нам не хватило места буквально на один одноклеточный кораблик! Удвоенная эскадра целиком на поле не поместилась. Но адмиралтейство было близко к успеху, это надо признать.

Олег «Апельсин» Бочаров

27 мая 2021