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