Как решить эту задачку? "Скучающая Катюша расставила по кругу цифры от 1 до 9 таким образом, что любые две соседние цифры, если их прочитать по часовой стрелке, образуют двузначное число, имеющее не менее k делителей. Найдите наибольшее возможное значение k." Однако мне интересен более красивый, аналитический способ. Есть у кого-нибудь идеи?

Предыдущий
вопрос Следующий
вопрос

Для решения данной задачи можно воспользоваться следующим подходом:

Заметим, что двузначные числа с наибольшим количеством делителей - это квадраты простых чисел. Поэтому наибольшее значение k будет достигаться, если каждая пара соседних цифр будет образовывать квадрат простого числа.

Поскольку сумма цифр от 1 до 9 равна 45, то для того, чтобы каждая пара соседних цифр образовывала квадрат простого числа, сумма квадратов этих чисел должна быть максимально возможной.

Подберем комбинацию цифр от 1 до 9 таким образом, чтобы сумма квадратов была максимальной и каждая пара соседних цифр образовывала квадрат простого числа:

9 - 3 - 1 - 8 - 6 - 4 - 5 - 2 - 7

Таким образом, наибольшее возможное значение k для данной задачи равно 6.