На клетчатом поле 10 × 8… (вероятность и статистика)

№ Максимальная сумма чисел на поле с минами

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

Решение

. Что считает сумма. Каждая мина прибавляет по к каждой соседней клетке без мины. Поэтому сумма равна числу пар «мина — соседняя клетка без мины». Для мины это число равно (число её соседей) − (число соседних с ней мин).

Пусть у мин суммарно соседей, а пар соседних мин . Каждая пара соседних мин уменьшает сумму на , поэтому

. Оценка. Клетка внутри поля (не на границе) имеет соседей. Таких клеток , они образуют прямоугольник . Клетка на границе имеет не более соседей.

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

Если хотя бы одна мина стоит на границе, то

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

строки , , и столбцы , , , — это мин, никакие две не соседние;
ещё одна мина в клетке (; ), она соседняя только с миной (; ).

Все мин стоят внутри поля, у каждой соседей, а пара соседних мин ровно одна. Сумма равна

💡 Почему так

Сумма чисел равна числу пар «мина — соседняя пустая клетка». Выгодно ставить мины во внутренние клетки (по соседей) и не рядом друг с другом, но мин без соседства внутри поля не поместить — остаётся одна пара.

Ответ

✓ dzmen.ru

Помогло?

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