Задача по олимпиадной математике Ященко — максимальный путь в квадрате 3×3

Задача

Квадрат 3×3 заполнен цифрами так, как показано на рисунке слева. Разрешается ходить по клеткам этого квадрата, переходя из клетки в соседнюю (по стороне), но ни в какую клетку не разрешается попадать дважды.

Петя прошёл, как показано на рисунке справа, и выписал по порядку все цифры, встретившиеся по пути, – получилось число 84937561. Нарисуйте другой путь так, чтобы получилось число побольше (чем больше, тем лучше).

Решение

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

Девятизначное число тем больше, чем больше его первая цифра. Но девятизначного числа, начинающегося с 9, построить не удастся. Более того, ни для какой из чёрных клеток (см. рисунок ниже) не существует начинающегося в ней пути, проходящего по всем клеткам доски. Действительно, ход из чёрной клетки всегда приводит в белую. Всего чёрных клеток четыре, поэтому белых клеток на любом таком пути тоже не более четырёх – все пять белых клеток так не обойти.

Поэтому надо начать с самой большой "белой" цифры – цифры 5, перейти к её наибольшему соседу, цифре 7, а потом к её наибольшему соседу, цифре 3. Затем придётся перейти к клетке 6 – иначе обойти всю доску не получится. Далее путь единственен.

Ответ

Наибольшее число, которое можно получить, – 573618492 (см. рис.).

Олимпиадная задача: максимальное число по пути в квадрате 3×3 для 6–7 класса

Задача

Решение

Ответ

Подтверждение удаления