Морской бой. На какой наименьшей доске можно разместить комплект кораблей?

Слушайте, а вы задумывались когда-нибудь, раскладывая тетрадный листок в клеточку, насколько компактно можно «упихать» весь этот грозный флот? Мы привыкли к классическому квадрату десять на десять, где есть разгуляться и авианосцу, и юрким катерам. Но азарт исследователя так и подмывает задать вопрос: «Морской бой. На какой наименьшей доске можно разместить комплект кораблей?» Ведь это не просто игра в угадайку, а настоящая комбинаторная головоломка, заставляющая мозги скрипеть.

Геометрия тесноты и здравого смысла

Классический набор — это один четырехпалубник, два трехпалубника, три эсминца и четыре «единички». Итого — десять боевых единиц, занимающих в сумме двадцать клеток. Кажется, ну чего там сложного? Возьми поле пять на пять, и дело в шляпе! Но не тут-то было. Правила — вещь суровая: корабли не должны касаться друг друга ни бортами, ни даже углами. И вот тут начинается настоящая «жара».

Пытаясь ответить на вопрос, «Морской бой. На какой наименьшей доске можно разместить комплект кораблей?», математики-любители и фанаты игры исписали не один десяток черновиков. Оказывается, что если мы хотим соблюсти все каноны бесконтактной расстановки, поле 6x6 становится непреодолимым барьером. Корабли начинают «толкаться локтями», и кому-то обязательно не хватает места под солнцем.

Магическое число семь

Знаете, методом проб и ошибок, а также задействовав логику, которая порой заводит в тупик, энтузиасты выяснили: минимальный полигон для маневров — это квадрат со стороной семь. Да-да, на поле 7x7 можно аккуратно, ювелирно, буквально впритирку расположить весь арсенал. Это выглядит как идеальный пазл, где каждый свободный сантиметр на вес золота.

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

Почему это вообще важно?

Конечно, играть на таком маленьком поле — сомнительное удовольствие. Партия закончится быстрее, чем вы успеете сказать «мимо». Однако для программистов, создающих алгоритмы, или для любителей теории графов — это отличный вызов. Сложно ли это? Безусловно. Интересно ли? Еще бы!

В конце концов, такие задачи учат нас смотреть на привычные вещи под другим углом. Глядя на пустую сетку, мы видим не просто клетки, а потенциал для оптимизации. А как вы считаете, реально ли впихнуть невпихуемое на еще меньшую площадь, если слегка изменить форму доски? Это уже совсем другая история, требующая отдельного разбора. Но на сегодня ответ один: семерка — наш минимум.