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

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

У каждой клетки не более 8 соседей, поэтому сумма чисел не превосходит 80. Если бы она равнялась 80, все 10 мин должны были бы стоять во внутренних клетках, и ни две мины не могли бы быть соседними. Но в квадрате 6 × 6 внутренних клеток нельзя разместить 10 попарно несоседних клеток: разбив их на девять блоков 2 × 2, в каждом можно выбрать не более одной такой клетки. Значит, сумма не может быть 80.

Для достижения 78 возьмём внутренние клетки, считая их координаты от 1 до 6. Поставим мины в клетках с координатами (r, c), где r и c независимо принимают значения 1, 3, 5, а также в клетке (6, 6). Получится 10 мин. Среди них ровно одна соседняя пара — (5, 5) и (6, 6). Поэтому сумма чисел равна числу соседств, выходящих от мин: 10 · 8 − 2 · 1 = 78. Каждое соседство между двумя минами вычитается дважды.

Ответ: 78.