Здравствуйте)
Недавно наткнулся на одну занимательную, на мой взгляд, задачу. Несколько дней думал, но в итоге решить полностью так и не удалось. Интересно узнать, как она все-таки решается. Буду рад любым идеям.
Условие таково: доказать, что для любого натурального n ≥ 12 найдется такая перестановка чисел от 1 до n {π1, π2, π3, ..., πn}, что πi + i является полным квадратом для любого 1 ≤ i ≤ n .
P.S. Заранее прошу прощения, если задача широко известна и где-то уже обсуждалась. Я не нашел.
Внесу небольшой вклад)
n = 12: 3 2 1 12 11 10 9 8 7 6 5 4n = 13: 8 2 13 12 11 10 9 1 7 6 5 4 3Других валидных перестановок длины 12 и 13 нет.
n = 14: 3 2 1 5 4 10 9 8 7 6 14 13 12 11n = 15: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1n = 18: 15 14 13 12 11 10 18 17 16 6 5 4 3 2 1 9 8 7По ходу правок можно отследить процесс работы перебора? :)
скорее процесс борьбы с маркапом
Она парсочем решается :) http://pastie.org/4586142
Можно попробовать делать так.
Для исходной длины n берём максимальное число, не превышающее n и дающее с ним в сумме полный квадрат — пусть оно равно k. Тогда если существует хорошая перестановка длины k-1, то, приписав к ней все числа от n до k (именно в таком порядке), мы тоже получим хорошую перестановку.
Есть только одно число большее 17, для которого k<=12. Это 24. Но для него хорошая перестановка очевидна — это обратная перестановка.
Таким образом, если воспользоваться результатами Hohol или программой yarrr и убедиться, что для всех чисел от 12 до 17 существуют хорошие перестановки, то можно считать теорему доказанной.
Спасибо большое! Красивое решение.
"Есть только одно число большее 17, для которого k<=12."
Почему это так?
До 24 проверим утверждение вручную. Пусть есть x ≥ 25: n2 ≤ x < (n + 1)2, для некоторого n ≥ 5. Если (n + 1)2 - x > 12 то, действительно k > 12. Иначе, предположим противное: пусть k ≤ 12, тогда предложим в качестве k следующее: k = (n + 2)2 - x. Заметим, что k = (n + 2)2 - x = (n + 2)2 - (n + 1)2 + ((n + 1)2 - x)) = 2 * (n + 1) + 1 + ((n + 1)2 - x)) ≤ 2 * (n + 1) + 1 + 12 = 2n + 15. Ясно, что 2n + 15 < n2 ≤ x. Значит k ≤ x и также ясно, что k > 12, т.к. k ≥ 2(n + 1) + 1 > 12. Пришли к противоречию.
Рассмотрим функцию k(n). Она как правило убывает с ростом n, что логично, ведь когда n увеличивается на 1, почти всегда у нас не появится нового максимального числа меньше n, которое в сумме с ним даёт полный квадрат.
В каких же случаях она возрастает? В случаях, когда n — половина некоторого квадрата, округлённая вверх.
Таким образом можно проследить, что отрезки убывания k(x) — это
Теперь посмотрим зависимость минимального значения k(x) на полуинтервале от x. Максимальное, конечно —
, а минимальное меньше его на длину полуинтервала минус 1. То есть 
.
Если x — чётное, то есть x = 2y, то минимальное k(y) = 2y(y - 1). Если x — нечётное, то есть x = 2y + 1, то минимальное k(y) = 2y2
Теперь осталось для каждого случая решить неравенство k(y) < = 12. И получим, соединив оба случая, что x < = 6. Но случаи x < = 5 относятся к n < 18, а в случае x = 6 получим, что только на правой границе будет достигнуто равенство 12 — как раз в точке 24.
В общем, много букв и прочих символов, но, надеюсь, понятно.