Задача 115384
|
|
 |
Условие
Легко разместить комплект кораблей для игры в "Морской бой" на доске 10× 10 (см. рис.). А на какой наименьшей квадратной доске можно разместить этот комплект? (Напомним, что согласно правилам корабли не должны соприкасаться даже углами.)Решение
Пример расстановки кораблей на доске 7×7 изображен на рис. Остается доказать, что на доске 6×6 корабли расставить нельзя.
Доказательство 1.
Будем считать не клетки, а узлы доски, занимаемые кораблями. Корабль 1×4 занимает 2·5=10 узлов, корабль 1×3 занимает 8 узлов, корабль 1×2 —6 узлов, корабль 1×1 — 4 узла; причем по правилам расстановки один узел не может принадлежать более чем одному кораблю. Значит, все корабли занимают 10+2· 8+3· 6+4·4=60 узлов, и выставить их все на доску с меньшим числом узлов невозможно. Но всего на доске 6×6 имеется лишь(6+1)2=49<60 узлов.
Ту же идею можно оформить иначе. А именно, заключим каждый корабль в прямоугольник, увеличив его на полклетки в каждую сторону. Такие прямоугольники не могут пересекаться и занимают всего 10+2·8+3·6+4·4=60 клеток. А если бы все корабли можно было разместить на доске 6×6, то все соответствующие прямоугольники располагались бы на доске 7×7, на которой имеется лишь 49<60 клеток. (Отметим, что каждая клетка этой новой доски содержит ровно один узел старой — поэтому вычисление и получается точно таким же, как в первом доказательстве.)
Доказательство 2. Разрежем доску 6× 6 на 9 квадратов 2× 2. Каждый такой квадрат при расстановке по правилам может содержать клетки только одного корабля. Но всего кораблей 10, поэтому их на такой доске разместить нельзя. (Отметим, что это рассуждение доказывает, что на доску 6× 6 все 10 кораблей нельзя было бы поставить, даже если все они имели бы размеры 1× 1.)
