Maths Olympiad Prep

Library / /17 of 37

Algebra Difficulty 4.8 AIME Find the answer Italy

Problem:

Given the polynomial p(x)=x(x+1)(x2)2p(x) = x(x+1)(x-2)^2, we consider the polynomial q(x)=p(p(p((p(x)))))q(x) = p(p(p(\ldots(p(x)) \ldots))) given by the composition of p(x)p(x) with itself 2024 times. How many integers kk are there such that q(k)=0q(k) = 0?

Pick one

Solution

Solution:

The answer is (C)\mathbf{(C)}. Let us call qk(x)=p(p((p(x))))q_{k}(x) = p(p(\ldots(p(x)))) the polynomial obtained by composing the polynomial pp with itself kk times, so that q(x)=q2024(x)q(x) = q_{2024}(x). It is clear that qk(x)q_{k}(x) is a polynomial with integer coefficients. Since for k>1k > 1 we have qk(x)=p(qk1(x))q_{k}(x) = p\left(q_{k-1}(x)\right) and since the only solutions to the equation p(x)=0p(x) = 0 are given by x=0x = 0, x=1x = -1 and x=2x = 2, we have that qk(x)=0q_{k}(x) = 0 if and only if qk1(x){0,1,2}q_{k-1}(x) \in \{0, -1, 2\}.

We observe that the equation p(x)=1p(x) = -1 has no integer solutions, while p(x)=0p(x) = 0 (resp. p(x)=2p(x) = 2) has as its only solution x=0x = 0 (resp. x=1x = 1); therefore, for k2k \geq 2 we have qk1(x)=p(qk2(x)){0,1,2}q_{k-1}(x) = p\left(q_{k-2}(x)\right) \in \{0, 1, 2\} if and only if qk2(x){0,1}q_{k-2}(x) \in \{0, 1\}.

Finally, since p(x)=1p(x) = 1 has no integer solutions, we have that for k>3k > 3 the equation qk2(x)=p(qk3(x))=1q_{k-2}(x) = p\left(q_{k-3}(x)\right) = 1 has no solutions and therefore qk1(x)=p(qk2(x)){0,1,2}q_{k-1}(x) = p\left(q_{k-2}(x)\right) \in \{0, 1, 2\} if and only if qk2(x)=0q_{k-2}(x) = 0.

Summing up the above, for k>3k > 3, we have that qk(x)=0q_{k}(x) = 0 holds if and only if qk2(x)=0q_{k-2}(x) = 0. Concatenating this implication enough times, we obtain that q(x)=q2024(x)=0q(x) = q_{2024}(x) = 0 if and only if q2(x)=p(p(x))=0q_{2}(x) = p(p(x)) = 0, which can easily be verified to have as solutions x{1,0,1,2}x \in \{-1, 0, 1, 2\}.

Want a route through all this instead of 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 translated into English from it; metadata (topic, difficulty) added by this project.