Белоснежка и несколько гномов хотят заселиться в домик, представляющий собой 5х11 квадрат клеток (клетка – это одна комната). Одну комнату в домике должна занять Белоснежка, а в…

Задача сводится к правилу гномов: каждый гном either стоит рядом со Snow White (Белоснежка) или не имеет соседей вообще. Соседи – 8 направлений (по стороне и по диагонали).

Пошаговое решение

1. Разберёмся, сколько гномов можно разместить вокруг Белоснежки.

• Если Белоснежка стоит в внутренней клетке сетки, вокруг неё существует 8 соседних комнат (клеток): сверху, снизу, слева, справа и по диагоналям.
• Любого гнома, стоящего в одной из этих 8 клеток, условие 1 выполняется (Белоснежка — сосед). Значит, таких гномов можно поселить всех восемь.

2. Пробуем добавить ещё гномов вне окружности Белоснежки.

• Гном, стоящий в какой-то другой клетке, не имеет Белоснежку среди соседей. Чтобы он согласился, у него должны быть ноль соседей-гномов.
• Но любая клетка вне окружности Белоснежки на Chebyshev-близости от неё (расстояние по максимальному координатному изменению ≥ 2) будет иметь по крайней мере одну соседнюю клетку, занятую гномом из окружности Белоснежки. Значит такой гном не сможет поселиться.

Следовательно, максимум гномов — это ровно количество клеток вокруг Белоснежки: максимум 8.

3. Можно ли достигнуть 8 на данной доске 5×11?

• Да. Разместим Белоснежку в внутренней клетке (например, в координатах (3,6) по нормальной нумерации). Вокруг неё восемь соседних клеток можно занять гномами. Это даст ровно 8 гномов.

Ответ

• Максимальное количество гномов, которых можно заселить: 8.

Дополнение

• Это достигается, когда Белоснежка стоит во внутренней клетке, где у неё ровно 8 соседей. На границе и углах число соседей меньше, следовательно и максимум гномов меньше (например, на краю — меньше 8).