Question

Математические пчёлы строят соты в форме клеток и живут в них, а их ульи состоят из квадратов 5×5 сот. Известно, что пчела просыпается, если хотя бы в двух соседних по стороне сотах кто-то жужжит, а как только она просыпается, она начинает жужжать. Зоологам интересно, какое минимальное количество пчёл им нужно разбудить, чтобы рано или поздно проснулись все пчёлы в улье?

Answer 1

Ответ:

5

Пошаговое объяснение:

По диагонали 5, и так расходятся другим двум вершинам

Answer 2

Представим каждую пчелу как вершину графа, а соседство между пчелами как ребра этого графа. В данном случае, граф будет двумерной решеткой, где каждая пчела (вершина) имеет четырех соседей (вершин), находящихся сверху, снизу, слева и справа.

Чтобы разбудить все пчелы в улье, необходимо, чтобы каждая пчела разбудила хотя бы одного из своих соседей. Таким образом, можно сформулировать задачу как задачу о покрытии ребер графа.

Минимальное количество пчел, которое нужно разбудить, чтобы разбудить всех, это количество, достаточное для покрытия всех ребер графа. В данном случае, графом является улей из квадратов 5x5.

Каждый квадрат 5x5 имеет 4 угла, 4 квадрата по сторонам и 1 внутренний квадрат. Это всего 14 квадратов, в которых могут размещаться пчелы.

Каждая пчела может покрыть 9 квадратов: тот, на котором она находится, плюс 8 соседних. Таким образом, нам понадобится (14 / 9) ≈ 1.56 пчелы.

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