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

## 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)?

• Mayve you can use Viete's formulas: proofwiki.org/wiki/Vi%C3%A8te%27s_Formulas in which you can see that roots of a polynomial are combinations of products and sums of the coefficients. Or is that how you are already attacking this problem? Jun 23, 2021 at 8:18
• Note that the polynomial $P_1(x) = 42$ does not have $42$ as a root. Jun 23, 2021 at 8:22
• @PrimeMover: Did you make a typo? Vieta's formulae show you how the coefficients are a combination of sum/products of the roots. Not the other way around, right? Jun 23, 2021 at 8:30
• @AryamanMaithani No, I didn't make a typo, I made a stupid mistake. A typo is where you hit the wrong key by accident. A stupid mistake is when you hit the keys you were intending to hit, but the thing you wrote was wrong. Jun 23, 2021 at 10:08

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)$$.

• Ross can get more than $R$ though. If he manages to get $1$ and $42$, then he can get $1/42$ as $42x - 1$. My guess was that he'll end up with the set $$\left\{\frac{a}{b} : a, b \mid 42,\ a, b \in \Bbb Z\right\} \cup \{0\}.$$ Jun 23, 2021 at 8:33
• He can only add integers to the set. If he can add arbitrary rationals, he can get $\{\pm2^a 3^b 7^c|a,b,c\in Z\}\cup\{0\}$ Jun 23, 2021 at 8:34
• Ahhh yes. Nice answer. Jun 23, 2021 at 8:36
• Here's all the n under 1000 for which Ross can get $\{0\}\cup\{\pm f : f | n\}$ starting from $\{0,n\}$, using only polynomials of degree 2 or less: $\{1, 2, 4, 6, 9, 12, 16, 20, 25, 30, 36, 42, 49, 81, 90, 121, 144, 156, 169, 256, 272, 289, 361, 400, 420, 529, 625, 841,900, 930, 961\}$ Allowing any degree polynomial will add more elements to this list. For example, 3. The next numbers that work are $n=1296, 1332, 1369, 1681...$. Jun 23, 2021 at 9:31