utnapishti (![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
utnapishti) wrote2017-01-22 07:15 pm
utnapishti) wrote2017-01-22 07:15 pm
Entry tags:
задачка
Наткнулся на такую задачку (источник - одна из верхних записей ![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
falcao):
Написать числа 1, 2, 3, ..., 32 по кругу (иными словами: составить из них замкнутую цепь) в таком порядке, чтобы сумма каждой пары соседних чисел была квадратом какого-нибудь целого числа.
То есть: сумма любой пары соседей должна быть одним из чисел: 4, 9, 16, 25, 36, 49.
Например, соседями числа 5 могут быть только 4, 11, 20 и 31.
Вот чем эта задачка приятна:
Прежде всего, нетрудно догадаться, как начинать решение. Есть несколько чисел, у которых изначально есть всего два кандидата в соседи. Например, для числа 32 это будут числа 4 и 17 (т.е. 32+4=36 и 32+17=49). Поэтому цепочка "4 - 32 - 17" должна быть частью ответа. Но после того, как мы выписываем все такие случаи, у нас всё ещё остаётся довольно много чисел, у которых больше, чем 2, кандидатов в соседи, и неочевидно, как всё это соединить в одну замкнутую цепь.
На этом этапе может показаться, что надо пробовать разные варианты и отсекать те, что приводят к противоречию.
Тем не менее оказывается, что на каждом этапе можно найти число, соседи которого определяются однозначно и "сразу", без перебора вариантов (но с использованием уже собранной информации). При этом конкретные аргументы - разные в разных случаях.
(В частности, поскольку это верно для всех этапов, то решение оказывается единственным.)
(В общем, это приятная разминка для мозгов, но не думаю, что у этой задачи есть какой-нибудь "математический смысл". В частности, думается, что вопрос о том, на что можно заменить 32 в условии - безнадёжный.)
falcao):Написать числа 1, 2, 3, ..., 32 по кругу (иными словами: составить из них замкнутую цепь) в таком порядке, чтобы сумма каждой пары соседних чисел была квадратом какого-нибудь целого числа.
То есть: сумма любой пары соседей должна быть одним из чисел: 4, 9, 16, 25, 36, 49.
Например, соседями числа 5 могут быть только 4, 11, 20 и 31.
Вот чем эта задачка приятна:
Прежде всего, нетрудно догадаться, как начинать решение. Есть несколько чисел, у которых изначально есть всего два кандидата в соседи. Например, для числа 32 это будут числа 4 и 17 (т.е. 32+4=36 и 32+17=49). Поэтому цепочка "4 - 32 - 17" должна быть частью ответа. Но после того, как мы выписываем все такие случаи, у нас всё ещё остаётся довольно много чисел, у которых больше, чем 2, кандидатов в соседи, и неочевидно, как всё это соединить в одну замкнутую цепь.
На этом этапе может показаться, что надо пробовать разные варианты и отсекать те, что приводят к противоречию.
Тем не менее оказывается, что на каждом этапе можно найти число, соседи которого определяются однозначно и "сразу", без перебора вариантов (но с использованием уже собранной информации). При этом конкретные аргументы - разные в разных случаях.
(В частности, поскольку это верно для всех этапов, то решение оказывается единственным.)
(В общем, это приятная разминка для мозгов, но не думаю, что у этой задачи есть какой-нибудь "математический смысл". В частности, думается, что вопрос о том, на что можно заменить 32 в условии - безнадёжный.)