What is the maximum number of distinct integers $A$ can have as elements?

Question

Problem

Ross wants to build a special set $A$. He starts with $A=\{0, 42\}$. At any step, he can add an integer $x$ to the set $A$ if it is a root of a polynomial that uses the already existing integers in $A$ as coefficients. He keeps doing this, adding more and more numbers to $A$. What is the maximum number of distinct integers $A$ can have?

My thoughts

First of all, this is a contest problem and I am a bit confused with the problem statement. I am assuming that I can't use the zero polynomial to make the problem more clear.

I tried to solve the problem simply making polynomials and see what elements $A$ can have. For the first step, the polynomial is $P_1(x)=42$. So, after the first step, $A=\{0,42,42\}$. For the second step, the polynomial is $P_2(x)=42x+42$. So, after the second step, $A=\{-1,0,42\}$. For the third step, the polynomial is $P_3(x)=-x^2-x+42$ ( I am assuming that I can use some of the existing integers more than once as coefficients in a certain polynomial). So, after the third step, $A=\{-7,-1,0,6,42\}$. After this, the polynomials get harder to check.

From the first three steps, I see that divisors of $42$ (both positive and negative) can be an element in $A$. If this is true, how to prove this? And can the problem be solved in more elegant way ( not checking the polynomials)?

Answer 1

The rational root theorem says that if you have a polynomial $a_n x^n + ... + a_0$ with integer coefficients, then all rational roots must be of the form $\pm\frac{p}{q}$, where $p$ divides $a_0$ and $q$ divides $a_n$.

In particular,

• the roots can't be bigger in magnitude than $|a_0|$, so Ross can't get any elements into his set outside the range $[-42,42]$.
• All integer roots will be factors of $a_0$. Since he starts with just factors of $42$, he'll only ever get factors of $42$.

Whatever set he ends up with, it will be a subset of $R=\{0, \pm1, \pm2, \pm3, \pm6, \pm7, \pm14, \pm21, \pm42\}$. So one approach is to build his set, and stop when you get to $R$.

You already got quite far. You can get $2$ and $-3$ via $-x^2-x+6$, and then you get $1$ via $-x^2+2x-1$.

Now you have $1$, then for each $p$ you have, use $x+p$ to get $-p$.

That leaves just $\pm14$ and $\pm21$, but you can use $ax-42$ to get those for various $a$.

"Is there an easier way?"

I don't think so. In particular, I don't think Ross would always be able to get all the factors of $n$ starting from $\{0,n\}$ (although it's still true that he can only get factors of $n$) He could always get $-1$, but the fact that 42 (and then 6) gave as much as they did came down to the fact that they can be factorised as $k(k+1)$.