Докажите, что в квадрате 10х10 невозможно по правилам расставить 2 комплекта для морского боя. Один комплект - 1 по 1х4 2 по 1х3 3 по 1х2 и 4 по 1х1
Корабли не должны касаться друг друга даже угловыми клетками!
Корабли не должны касаться друг друга даже угловыми клетками!
More Questions From This User See All
Answers & Comments
- Для однопалубного корабля (состоящего из одной клетки) защитный периметр состоит из восьми клеток.
- Для двухпалубного - из десяти.
- Для трёхпалубного - из двенадцати.
- Для четырёхпалубного - из четырнадцати.
Для двух комплектов кораблей общий защитный периметр составит:
8×8+10×6+12×4+14×2=200 клеток.
Сами корабли двух комплектов состоят из 8×1+6×2+4×3+2×4=40 клеток.
Таким образом внутри поля 10×10 при заполнении его всеми кораблями останется 100-40=60 свободных клеток.
Защитный периметр одного корабля может накладываться на защитный периметр другого, что и будет происходить при таком уплотнении. Значит количество свободных клеток можно увеличить вдвое: 60×2=120 (это для справки).
Посчитаем, сколько реально нам понадобится пустых клеток внутри поля.
Корабли могут располагаться по краям игрового поля, значит часть их защитных периметров будет вынесено за его пределы. Нужно, чтобы максимальная часть вынесенных периметров накладывалась друг на друга, таким образом внутри поля можно сэкономить больше места. При расстановке как на рисунке 1 всего 10 клеток периметров накладываются за пределами поля (на рисунке зелёным цветом).
Периметр вокруг поля (на рисунке жёлтым цветом) состоит из 11×4=44 клеток.
Значит реально внутри поля нам понадобится (200-44)/2=156/2=78 и ещё минус 10 зелёных клеток, которые нам нужно посчитать дважды: 78-10=68 свободных клеток.
Однако у нас есть только 60 свободных клеток. 8 клеток не хватает. Один однопалубный корабль не поместится.
При другой раскладке с максимальным наложением вынесенных периметров друг на друга и полным заполнением периметра вокруг игрового поля (рис.2) (200-44)/2=78, 78-13=65 клеток, при фактическом наличии 60 клеток.
Доказано.