|
|
 |
Условие
Доска 7×7 либо пустая, либо на ней лежит "по клеткам" невидимый корабль 2×2. Разрешается расположить в некоторых клетках доски по детектору, а потом одновременно их включить. Включённый детектор сигнализирует, если его клетка занята кораблём. Какого наименьшего числа детекторов хватит, чтобы по их показаниям гарантированно определить, есть ли на доске корабль, и если да, то какие клетки он занимает?
Решение
Оценка. В каждом прямоугольнике 2×3 должно быть хотя бы два детектора: прямоугольник состоит из трёх доминошек 1×2, (полосок, и если детектор в крайней доминошке, мы можем не понять, есть ли корабль на двух других доминошках, а если детектор в средней доминошке, мы можем не понять, какую из крайних доминошек занимает корабль вместе со средней доминошкой. Поэтому всего должно быть не менее 16 детекторов (см. рис.).
Пример. На рисунке ниже чёрным указано расположение 16 детекторов. Всякий корабль пересекается ровно с одним чёрным квадратом 2×2 по одной клетке, по двум соседним или по всем четырём. В любом случае однозначно определяется положение корабля или его отсутствие.
Ответ
16 детекторов.
Замечания
1. 16 детекторов можно расположить только тремя принципиально различными способами. Один указан в решении, остальные два см. на рисунке ниже.
2. 8 баллов.
