В каждую клетку шахматной доски 8 ⨯ 8 записали некоторое натуральное число, не превосходящее 7. Сказочная шахматная фигура кузнечик стоит в одной из угловых клеток. Каждым своим ходом кузнечик может прыгнуть в клетку, стоящую в той же горизонтали или вертикали, что и кузнечик, и отстоящую от кузнечика на столько клеток, какое число записано в клетке с кузнечиком (в частности, если в клетке с кузнечиком записано число 1, он может переместиться на одну из соседних с ним по горизонтали или по вертикали клеток). Известно, что за 63 прыжка кузнечик может посетить все клетки доски, побывав в каждой ровно один раз. Какое наибольшее количество троек могло быть написано в клетках доски?
Разобьём клетки доски на группы, как показано на левом рисунке (разными цифрами обозначены разные группы). Заметим, что если в какой-либо группе клеток все написанные числа равны трём, то кузнечик, прыгая по клеткам этой группы, никогда не сможет попасть в клетки другой группы. Так как кузнечик может обойти все клетки доски, он смог переместиться между клетками разных групп хотя бы 8 раз. Значит, троек могло быть не более 56.
Приведём пример заполнения клеток таблицы и порядка обхода этих клеток кузнечиком (см. правый рис.). В клетках A9, B9, C6, D6, E9, F9, G6, H6 стоят единицы, во всех остальных — тройки. Порядок обхода
Ответ: 56.