Olympiad Maths Prep

Library / /5 of 55

Algebra Difficulty 5.1 AIME, harder Prove it Ukraine

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

(Arseniy Nikolaev)

Solution

We are going to prove a lemma prior to the problem itself: the polynomial which will be written after kk days does not depend on Kate's choices and equals to
Fk=(…((x2+1)2+1)2+… )2⏟k+1. F_k = \underbrace{(\dots((x^2 + 1)^2 + 1)^2 + \dots)^2}_{k} + 1.

Using induction one can directly verify this lemma. Alternatively, one can use the following equality:
g2(x)+1=(h2(x)+1)2+1=(h((x2+1))2+1=h2(x2+1)+1=h2(t)+1=g(t)=g(x2+1). 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.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.