Задача
ALG-B3-M02-P023 Циклы кубического многочлена
Пусть \(F(x)\) - кубический многочлен. Назовём тройку различных чисел \((a,b,c)\) циклом, если \(F(a)=b\), \(F(b)=c\), \(F(c)=a\). Известно, что существуют семь циклов, причём все \(21\) участвующее число различны. Докажите, что среди семи сумм \(a+b+c\), соответствующих этим циклам, есть хотя бы три различных значения.
Подсказка 1. Предположите, что различных сумм не больше двух.
Подсказка 2. Для четырёх циклов с одной суммой рассмотрите \(G(x)=x+F(x)+F(F(x))-s\).
Предположим противное: среди семи сумм не более двух различных. Тогда одна из сумм, скажем \(s\), встречается хотя бы в четырёх циклах. Для любого числа \(x\) из такого цикла выполнено \(x+F(x)+F(F(x))=s\). Значит все \(12\) чисел этих четырёх циклов являются корнями многочлена \(G(x)=x+F(x)+F(F(x))-s\). Так как \(F\) кубический, степень \(F(F(x))\) равна \(9\), значит степень \(G\) не больше \(9\). Но у ненулевого многочлена степени не больше \(9\) не может быть \(12\) различных корней. Противоречие. Следовательно, различных сумм хотя бы три.
A. Анализ источника. Главные объекты: итерации кубического многочлена и циклы длины три.
B. Недостаточный первый ход. Пытаться анализировать сами циклы по отдельности слишком сложно.
C. Скрытое наблюдение. Одинаковая сумма цикла превращает все его элементы в корни одного многочлена.
D. Нужный ход. Нужно применить принцип Дирихле к суммам и построить x+F(x)+F(F(x))-s.
E. Число идей. Три идеи: pigeonhole, переход от цикла к корням, ограничение числа корней степенью.
F. Обоснование уровня. Финальный уровень 8: задача требует увидеть многочлен от итерации, а не вычислять циклы.
G. Почему это не одношаговая задача. Это не одношаговая задача: сначала нужна группировка циклов, затем построение многочлена и подсчёт степени.