6
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ 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? $\endgroup$ Jun 23, 2021 at 8:18
  • $\begingroup$ Note that the polynomial $P_1(x) = 42$ does not have $42$ as a root. $\endgroup$ Jun 23, 2021 at 8:22
  • 1
    $\begingroup$ @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? $\endgroup$ Jun 23, 2021 at 8:30
  • $\begingroup$ @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. $\endgroup$ Jun 23, 2021 at 10:08

1 Answer 1

3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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\}.$$ $\endgroup$ Jun 23, 2021 at 8:33
  • $\begingroup$ 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\}$ $\endgroup$ Jun 23, 2021 at 8:34
  • $\begingroup$ Ahhh yes. Nice answer. $\endgroup$ Jun 23, 2021 at 8:36
  • 2
    $\begingroup$ 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...$. $\endgroup$ Jun 23, 2021 at 9:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.