Problem
ALG-B3-M02-P023 Cycles of a cubic polynomial
Let \(F(x)\) be a cubic polynomial. Call a triple of distinct numbers \((a,b,c)\) a cycle if \(F(a)=b\), \(F(b)=c\), \(F(c)=a\). Suppose there are seven cycles and all \(21\) numbers involved are distinct. Prove that among the seven sums \(a+b+c\) corresponding to these cycles, at least three distinct values occur.
Hint 1. Assume that there are at most two distinct sums.
Hint 2. For four cycles with the same sum, consider \(G(x)=x+F(x)+F(F(x))-s\).
Assume the contrary: among the seven sums there are at most two distinct values. Then one value, say \(s\), occurs in at least four cycles. For every number \(x\) in such a cycle, \(x+F(x)+F(F(x))=s\). Hence all \(12\) numbers from these four cycles are roots of \(G(x)=x+F(x)+F(F(x))-s\). Since \(F\) is cubic, \(F(F(x))\) has degree \(9\), so \(G\) has degree at most \(9\). A nonzero polynomial of degree at most \(9\) cannot have \(12\) distinct roots. Contradiction. Therefore at least three distinct sums occur.
A. Source analysis. Main objects: iterations of a cubic polynomial and 3-cycles.
B. Insufficient first move. Trying to analyze the cycles separately is too difficult.
C. Hidden observation. A common cycle sum turns all elements of those cycles into roots of one polynomial.
D. Required move. Use pigeonhole on the sums and build x+F(x)+F(F(x))-s.
E. Number of ideas. Three ideas: pigeonhole, turning cycles into roots, and bounding roots by degree.
F. Difficulty justification. Final level 8: the problem requires seeing a polynomial of an iteration, not computing cycles.
G. Why it is not one-step. It is not one-step: one must group cycles, construct a polynomial, and count its degree.