Поставьте как можно меньше одноклеточных кораблей на доску 6 * 6 так, чтобы нельзя было поставить ещё один корабль ( корабли не могут стоять в соседних по стороне или диагонали клетках)

Задача: на доске 6×6 расставить одноклеточные корабли так, чтобы они не стояли рядом по стороне или диагонали, и чтобы больше нельзя было поставить ещё один корабль. Найти минимальное число кораблей. Решение 1) Предел по минимальности (нижняя граница) - Каждая одиночная клетка корабля блокирует для размещения ещё одного корабля до 8 соседних клеток (по горизонтали, вертикали и по диагоналали). - Всего на доске 6×6 = 36 клеток. Пусть размещено k кораблей. Осталось пустых клеток: 36 − k. - Чтобы не могло быть добавлено ещё одно корабльное размещение, каждая пустая клетка должна быть соседей хотя бы одного корабля. Совокупность соседних клеток всех кораблей имеет суммарную максимальную ёмкость ≤ 8k (а фактически может перекрываться, но максимум — 8k). - Следовательно, 36 − k ≤ 8k, откуда 36 ≤ 9k и k ≥ 4. - Значит минимально возможно 4 корабля. 2) Конструкция с 4 кораблями (показывает достижимость минимума) Разместим корабли в следующих клетках доски (указываю по координатам row, column, начиная с 1): - (2, 2) - (2, 5) - (5, 2) - (5, 5) Проверки: - Ни две корабля не стоят рядом: расстояние по любой оси между любыми двумя равно либо 3, либо больше, так что запрет на соседство соблюдается. - Каждая пустая клетка оказывается соседней как минимум к одному из этих кораблей. Объяснение удобнее всего сделать разбиением доски на четыре квадрата 3×3: - TL (rows 1–3, cols 1–3) содержит корабль в центре (2,2). Все остальные клетки TL лежат в его соседях. - TR (rows 1–3, cols 4–6) содержит корабль (2,5). Оставшиеся клетки TR — его соседи. - BL (rows 4–6, cols 1–3) содержит корабль (5,2). Остальные клетки BL — его соседи. - BR (rows 4–6, cols 4–6) содержит корабль (5,5). Остальные клетки BR — его соседи. Таким образом, каждую пустую клетку можно отнести к одному из этих четырех квадрантов, и она окажется в соседях соответствующего корабля. Поэтому после такой расстановки нельзя поставить ещё один корабль без нарушения правила. 3) Вывод - Минимальное число одноклеточных кораблей равно 4. - Приведённая расстановка S: (2,2), (2,5), (5,2), (5,5) удовлетворяет условиям и является минимальной. - Любое размещение на 3 кораблях невозможно, потому что тогда максимум 8×3 = 24 пустых клеток могли бы быть соседями к кораблям, а пустых клеток на доске 36 − 3 = 33, поэтому найдётся клетка, не соседняя ни с одним кораблём, и её можно было бы поставить новый корабль. Итог: 4 корабля — минимально возможное число; пример размещения — в клетках (2,2), (2,5), (5,2), (5,5).