На клетчатом поле 6 × 8 располагают 7 мин. После… (математика)

Максимальная сумма чисел в «сапёре» на поле ×

На клетчатом поле $6 \times 8$ располагают 7 мин. После этого на каждой клетке без мины записывают число мин на соседних с ней клетках. Найдите максимальную возможную сумму чисел на доске.
Соседними считаем клетки, имеющие общую сторону или вершину, то есть у одной клетки может быть до 8 соседей. Ниже приведён пример подобной доски размера $5 \times 5$ с 4 минами.

Решение

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

Мина с соседями вносит не больше . Если рядом с миной стоит другая мина, эта соседняя клетка числа не получает, и вклад уменьшается.

Пусть среди мин есть пар соседних мин. Тогда сумма равна

Больше всего соседей () у клеток внутри поля. Таких клеток . У клеток на краю соседей , у угловых .

Расставить мин внутри так, чтобы они не были соседними, нельзя. Внутренний прямоугольник делится на прямоугольников , а в каждом из них можно поставить не больше одной мины. Значит, в нём не больше несоседних мин.

Рассмотрим варианты:

Шесть мин внутри без соседей и седьмая на краю: .
Все мин внутри: хотя бы одна пара соседних, , поэтому .
Любые другие варианты с миной на краю или в углу дают не больше .

Значит, .

Пример на . Нумеруем строки сверху вниз –, столбцы слева направо –. Ставим мины в клетки (строка, столбец):

Все они внутри поля. Соседними оказываются только (;) и (;), то есть . Тогда

💡 Почему так

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

Ответ

✓ dzmen.ru

Помогло?

На клетчатом поле 6 × 8 располагают 7 мин. После этого на…