Question

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

Answer 1

Ответ:

81

Восемьдесят один

Answer 2

Эта задача связана с теорией автоматов на клеточных автоматах и имеет отношение к теории перколяции. В данном случае, у нас есть сетка сот, и каждая сота может быть либо активной (просыпшейся) или пассивной (спящей).

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

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

Поскольку у нас сетка 9x9, мы можем разместить активные соты на внешней границе улья размером 7x7 (внутри оставляя пустое пространство 5x5). Теперь давайте посмотрим, какая часть улья будет активирована.

makefileCopy code
P = активная сота
S = спящая сота

PPPPPPP
PSSSSSP
PSSSSSP
PSSSSSP
PSSSSSP
PSSSSSP
PPPPPPP

Как видно из вышеуказанной конфигурации, мы активировали 37 сот. Оставшиеся спящие соты находятся внутри активированного участка. Теперь, если каждая из этих спящих сот разбудится по крайней мере одним активным соседом, они также начнут жужжать и дальше активировать своих соседей.

Таким образом, чтобы гарантировать, что рано или поздно проснутся все пчёлы в улье, достаточно разбудить 37 пчёл на внешней границе улья.