59th Ukrainian National Mathematical Olympiad

Question

A polynomial x^2 + 1 is written on the blackboard. Every day Kate wipes off currently written polynomial F(x) and writes one of the F^2(x) + 1 and F(x^2 + 1) instead, choosing at her discretion. Prove that the constant (free) term will exceed 2^2^222 in one year. (Arseniy Nikolaev)

Accepted Answer

We are going to prove a lemma prior to the problem itself: the polynomial which will be written after

k

days does not depend on Kate's choices and equals to

F_{k} = k (\dots ((x^{2} + 1)^{2} + 1)^{2} + \dots)^{2} + 1.

Using induction one can directly verify this lemma. Alternatively, one can use the following equality:

g^{2} (x) + 1 = (h^{2} (x) + 1)^{2} + 1 = (h ((x^{2} + 1))^{2} + 1 = h^{2} (x^{2} + 1) + 1 = h^{2} (t) + 1 = g (t) = g (x^{2} + 1) .

to get the aforementioned result.