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

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

⚠️

На фото видно только задание . Задание обрезано, а верх страницы с пунктами а) и б) относится к другому заданию, поэтому они не решались.

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

Соседними считаем клетки, имеющие общую сторону или вершину, то есть у одной клетки может быть до 8 соседей.

Ниже приведён пример подобной доски размера $5 \times 5$ с 4 минами.

Решение

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

Пусть — число пар соседних мин. У мины в середине поля соседей, у мины на краю , в углу . Тогда сумма равна

Вычитаем , потому что каждая пара соседних мин «съедает» по одному соседу у каждой из двух мин.

Оценка.

Внутренняя часть поля — квадрат . Разобьём его на квадратиков . В каждом квадратике любые две клетки соседние, поэтому в нём не более одной мины без соседней пары.
Если все мин стоят внутри, то по принципу Дирихле в каком-то квадратике окажутся две мины, то есть . Значит, .
Если хотя бы одна мина стоит на краю, у неё не более соседей. Тогда .

Итак, .

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

строка : столбцы , , , ;
строка : столбцы , , ;
строка : столбцы , , .

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

💡 Почему так

Сумма чисел равна числу пар «мина — соседняя клетка без мины». Максимум достигается, когда все мины внутри поля и ровно одна пара мин соседняя.

Ответ

✓ dzmen.ru

Помогло?

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