Тебя ждет веселье: надо уместить на поле морского боя максимальное число кораблей.
Напоминаем, что такое «Морской бой» для тех, кто в танке (поэтому ни разу не бывал на флоте). Классическая игра предполагает, что ты начертил поле 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
