Решение задачи 420

Условие:

В каждой клетке доски 8×8 написано некоторое натуральное число так, что у каждой пары клеток, соседних по ребру, числа отличаются на 1. Найдите наибольшую возможную сумму чисел на главных диагоналях, если на доске присутствуют числа 6 и 20.

Решение:

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

Разность чисел равна 14, поэтому необходимо сделать хотя бы 14 шагов, потому что числа в соседних клетках отличаются на 1. Назовем расстоянием между клетками доски минимальную длину пути (число шагов) между этими клетками. Очевидно, что путь наибольшей длины -- это путь между двумя противоположными угловыми клетками. Длина такого пути как раз равна 14 (расстояние между угловыми клетками равно 14). Таким образом, числа 6 и 20 обязаны стоять в двух противоположных угловых клетках (для определенности будем считать, что они стоят в левом нижнем и правом верхнем углах). При этом все оставшиеся числа на доске определяются однозначно (т.к. пройдя по любому кратчайшему пути мы обязаны каждый раз добавлять 1 на каждом шаге):

Таким образом, сумма чисел на главных диагоналях определяется однозначно и равна 208.

Ответ: 208