Competition problem — Algebra — Maths Olympiad Prep

Library / /24 of 27

Algebra Difficulty 6.9 National olympiad Prove it Croatia

Let $S = \{0, 95\}$ . In each step, Lucija is extending the set $S$ in the following way. She chooses a polynomial with coefficients in $S$ , distinct from zero, and extends $S$ with all integer roots of a chosen polynomial. She repeats the procedure by choosing another polynomial with coefficients from the extended set $S$ as long as she can get new roots.
Prove that Lucija can, in a finite number of steps, extend the set $S$ up to the set which is no longer extensible. How many elements does the set $S$ have at the end?

Solution

If the coefficients of a polynomial are integers, then its roots must divide the constant term. Without loss of generality, we may assume that the constant term of the chosen polynomial is non-zero, so we conclude that we can extend $S$ only with the divisors of $95$ . Since $95$ has only finitely many divisors, Lucija will not be able to extend $S$ indefinitely.

We will prove that Lucija can add all the divisors of $95$ into $S$ , i.e. that $S$ will have $9$ elements in the end.

Since $-1$ is the root of the polynomial $95x + 95$ , we can add $-1$ to $S$ .

Number $1$ is a root of $-x^9 - x^{94} - \dots - x + 95$ , so $S$ can be extended with $1$ .

Now we can extend $S$ with $-95$ because it is the root of $x + 95$ .

Polynomial $-x^3 + x^2 + x + 95$ with coefficients in $S$ has a root $5$ , hence $5$ becomes an element of $S$ . Now we add $-5$ into $S$ , because $-5$ is the root of $x + 5$ .

In the end, $-19$ , $19 \in S$ since these are the roots of polynomials $5x + 95$ and $5x - 95$ .

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 and solution reproduced as published; topic and difficulty added by this site.