IMO 1968 Problem 3

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 9m13s

Problem

Consider the system of equations $$ ax_1^2 + bx_1 + c = x_2 $$ $$ ax_2^2 + bx_2 + c = x_3 $$ $$ \cdots $$ $$ ax_{n-1}^2 + bx_{n-1} + c = x_n $$ $$ ax_n^2 + bx_n + c = x_1 $$ with unknowns $x_1, x_2, \cdots, x_n$ where $a, b, c$ are real and $a \neq 0$. Let $\Delta = (b - 1)^2 - 4ac$. Prove that for this system

(a) if $\Delta < 0$, there is no solution,

(b) if $\Delta = 0$, there is exactly one solution,

Exploration

Let $f(x)=ax^2+bx+c$. The system imposes $x_{k+1}=f(x_k)$ for $k=1,\dots,n-1$ and $x_1=f(x_n)$, so each solution corresponds to a real sequence generated by iteration of $f$ that closes after $n$ steps.

Thus the system is equivalent to requiring $x_1$ to satisfy $f^n(x_1)=x_1$, and then defining $x_k=f^{k-1}(x_1)$. Hence solutions correspond exactly to real periodic points of $f$ of period dividing $n$.

The expression $\Delta=(b-1)^2-4ac$ is the discriminant of $f(x)-x=ax^2+(b-1)x+c$, so it controls fixed points of $f$.

If $f$ has no real fixed points, iteration cannot cycle back in a finite number of steps under continuity and monotonicity behavior of quadratics, suggesting no solutions.

If $f$ has a unique fixed point, repeated iteration should collapse to that point, forcing all $x_i$ equal.

If $f$ has two fixed points, constant sequences at each fixed point already give distinct solutions, so multiple solutions exist.

The main structure reduces the system to understanding real fixed points of $f$.

Problem Understanding

The system defines a cyclic iteration of a quadratic map $f(x)=ax^2+bx+c$. The task is to determine how the number of real solutions depends on whether $f(x)=x$ has zero, one, or two real roots, which is encoded by $\Delta=(b-1)^2-4ac$.

This is Type A since all solutions must be characterized according to the sign of $\Delta$.

A solution corresponds to a real sequence that is periodic under iteration of $f$. The core difficulty is linking algebraic conditions on a quadratic equation to global dynamical behavior under iteration.

If $\Delta<0$, the graph of $y=f(x)$ never intersects $y=x$, preventing fixed points and hence preventing periodicity.

If $\Delta=0$, there is a unique tangency point, forcing collapse to a single constant solution.

If $\Delta>0$, two fixed points exist, immediately producing multiple constant solutions.

Thus the expected classification is:

If $\Delta<0$, no solutions. If $\Delta=0$, exactly one solution. If $\Delta>0$, at least two solutions.

Proof Architecture

The first lemma identifies the equivalence between solutions of the system and solutions of $f^n(x)=x$, together with the reconstruction of the full tuple from $x_1$.

The second lemma shows that if $\Delta<0$, then $f(x)-x$ has no real roots, implying that $f(x)>x$ for all $x$ or $f(x)<x$ for all $x$, which prevents periodic points and eliminates all solutions.

The third lemma treats $\Delta=0$ and shows that $f(x)-x$ has a unique root $r$, and every iteration forces all coordinates to equal $r$, producing exactly one solution.

The fourth lemma treats $\Delta>0$ and shows that $f(x)-x$ has two distinct real roots, each producing a distinct constant solution, giving at least two solutions.

The most delicate part is the second lemma, since it requires ruling out all possible periodic behavior without assuming existence of fixed points.

Solution

Let $f(x)=ax^2+bx+c$. The system can be rewritten as

$$x_{k+1}=f(x_k)\quad (k=1,2,\dots,n-1), \qquad x_1=f(x_n).$$

Substituting recursively yields $x_k=f^{k-1}(x_1)$ for all $k$, and the closing condition becomes $f^n(x_1)=x_1$.

Conversely, if $x_1$ satisfies $f^n(x_1)=x_1$ and $x_k=f^{k-1}(x_1)$, then all equations in the system hold. This establishes a bijection between solutions and real numbers $x_1$ satisfying $f^n(x_1)=x_1$.

Lemma 1

A tuple $(x_1,\dots,x_n)$ solves the system if and only if $x_1$ satisfies $f^n(x_1)=x_1$, with $x_k=f^{k-1}(x_1)$.

The recursive definition forces $x_k$ to equal $f^{k-1}(x_1)$, and the final equation is equivalent to the periodicity condition.

This certification establishes that the system reduces entirely to periodic points of $f$.

Lemma 2

If $f(x)-x$ has no real root, then the system has no solution.

The polynomial $f(x)-x=ax^2+(b-1)x+c$ has discriminant $\Delta=(b-1)^2-4ac$. If $\Delta<0$, this quadratic has no real root, so its sign is constant on $\mathbb{R}$. Since $a\neq 0$, the leading coefficient is nonzero, so $f(x)-x$ is either strictly positive or strictly negative for all real $x$.

Assume $f(x)-x>0$ for all $x$. Then $f(x)>x$ implies $f(f(x))>f(x)>x$, and inductively $f^k(x)>x$ for all $k\ge 1$. This contradicts $f^n(x)=x$ for any real $x$. The same contradiction arises if $f(x)-x<0$ for all $x$.

This certification excludes all periodic points when fixed points are absent.

Lemma 3

If $\Delta=0$, the system has exactly one solution.

In this case $f(x)-x$ has a unique real root $r$, so $f(r)=r$. For any $x_1\neq r$, the sign of $f(x_1)-x_1$ is nonzero, and repeated application yields a strictly monotone sequence that cannot return to its starting value, so no such $x_1$ satisfies $f^n(x_1)=x_1$. Hence $x_1=r$ is the only possible initial value.

With $x_1=r$, recursion gives $x_k=r$ for all $k$, producing a valid solution. No other solution exists.

This certification forces all solutions to collapse to a single constant orbit.

Lemma 4

If $\Delta>0$, the system has more than one solution.

Then $f(x)-x$ has two distinct real roots $r_1\neq r_2$, both satisfying $f(r_i)=r_i$. For each $i\in{1,2}$, the constant tuple $x_k=r_i$ satisfies all equations in the system.

These two tuples are distinct, giving at least two solutions.

This certification establishes multiplicity through distinct fixed points.

Combining Lemmas 2, 3, and 4 yields the classification.

Verification of Key Steps

The reduction to $f^n(x)=x$ relies on consistent substitution through the recurrence, and any attempt to assume periodicity without this equivalence would miss non-obvious constraints imposed by the closing equation.

In the case $\Delta<0$, the crucial point is that a sign-definite quadratic cannot admit any orbit returning to its starting value, since iteration preserves strict inequality at every step, preventing closure.

For $\Delta>0$, restricting attention only to constant sequences might appear insufficient in more complex dynamical systems, but here it already guarantees two distinct solutions because each fixed point independently generates a valid full cycle.

Alternative Approaches

One alternative approach linearizes the recurrence via a Möbius transformation sending the fixed points of $f$ to $0$ and $\infty$, transforming the iteration into a multiplicative dynamical system. In that framework, periodic points correspond to algebraic constraints on the multiplier.

Another approach studies $f^n(x)-x$ directly as a polynomial of degree $2^n$, then counts real roots via monotonicity intervals determined by critical points of iterates. This method is more computational and less transparent than the fixed-point reduction used above.

$$\boxed{ \begin{array}{ll} \Delta<0: & \text{no solution} \ \Delta=0: & \text{exactly one solution} \ \Delta>0: & \text{more than one solution} \end{array} }$$