Question

В деревне во всех домах живут мыши. Как только в доме заводят кошку, все мыши убегают из этого дома и из всех домов , соединённых с ними дорожкой (см.рисунок). В каком наименьшем числе домов надо завести кошек,чтобы мыши покинули деревню?
(А) 1.
(Б) 2.
(В) 3.
(Г) 4.
(Д) 5.

Answer 1

Одной кошки явно будет недостаточно, так как нет такого дома, который был бы соединен дорожками со всеми остальными. Для двух кошек можно показать требуемую расстановку (картинка).
Ответ: 2 кошки