8
$\begingroup$

The blackboard contains the two numbers 0 and 120. Each minute you are allowed to write an additional number $ x $ on the blackboard if $ x$ has not been written before on the blackboard and if $ x $ is the integer root of some polynomial $ P(x) $ in one variable whose coefficients are numbers on the blackboard. The game ends when you can not write further numbers on the blackboard.

Which numbers will be written on the blackboard when the game ends?

$\endgroup$
10
  • $\begingroup$ May the new X be any integer or is it limited in some range? $\endgroup$ Nov 23, 2015 at 18:03
  • $\begingroup$ Is this supposed to have some neat trick or do can I just simulate it? Am I only expected to record unique values (not 12 122s or something)? $\endgroup$
    – kaine
    Nov 23, 2015 at 18:08
  • $\begingroup$ @StillLearning The new x may be any integer, no limits. $\endgroup$
    – Haobin
    Nov 23, 2015 at 18:17
  • 3
    $\begingroup$ You should exclude the zero polynomial. $\endgroup$
    – f''
    Nov 23, 2015 at 18:57
  • 1
    $\begingroup$ To clarify: do you mean a polynomial of the form $c_0+c_1x+c_2x^2+\dots+c_nx^n$, where $c_0 \dots c_n$ are on the board, and $n > 0$, and $c_n \neq 0$? $\endgroup$
    – Lynn
    Nov 23, 2015 at 19:04

4 Answers 4

11
$\begingroup$

By the rational root theorem, any integer root of the polynomial $$a_nx^n + \dots + a_1x + a_0$$ is a divisor of its constant term $a_0$, if $a_0 \neq 0$.

We will never let $a_0 = 0$, since that means we can divide the whole polynomial by $x$ (repeatedly, if necessary; yielding a root $0$ each time, which is initially already on the board) and get a polynomial (with the same non-zero roots) for which $a_0 \neq 0$.

Thus initially, $a_0 = 120$, our only choice. From this, suppose we get a new root $p$, a divisor of $a_0 = 120$. Then the next minute, we can choose from $\{p, 120\}$, both divisors of 120, etc. Clearly, the integer roots we generate by this process will always be divisors of 120, positive or negative.

We show how to achieve all divisors of 120:

  • First, $120x+120$ gives us $x=-1$.

  • Then, $(-1)x^{120}+(-1)x^{119}+\dots+(-1)x^1+120$ gives us $x=1$.

  • Then, $x+120$ gives us $x=-120$.

We can get $2$, $3$ and $5$ using only the coefficients in $\{\pm 120, \pm 1\}$:

  • $-x^7 + x^3 \pm 120$ gives us $x = \pm 2$.
  • $-x^4 -x^3 -x^2 -x \pm 120$ gives us $x = \pm 3$.
  • $-x^3 +x \pm 120$ gives us $x = \pm 5$.

Aravind found a nice trick -- now that we have $2$, $3$, and $5$ on the blackboard, the other roots follow by dividing from $120 = 2^3 \cdot 3 \cdot 5$. (If we have $p$ and $q$ on the board, we can use $px-q$ to get $x=q/p$, so first take $q=120$ and then repeat the process with $q \to q/p$ for a prime $p$.)

We can conlude that the solution set is precisely the set of positive and negative divisors of 120.

$\endgroup$
1
  • $\begingroup$ Cool. Best answer. Thanks for the link. $\endgroup$ Nov 23, 2015 at 19:47
3
$\begingroup$

Every integer can be written on the board.

First polynomial: $$P(x) = 120x - 120$$

The root of this polynomial is 1.

Any integer:

$$P(x) = x - x$$

In this solution, it is important to note that constants are not coefficients. Also note that $-$ is an operator, not part of the coefficient. Had it been intended as the coefficient, I would have written $x + -x$ (or even more explicitly $1x + -1x$).

Edit: As an added shortcut (thanks to f''), you could simply use this polynomial from the initial board to retrieve any value for $x$:

$$P(x) = 0x$$

$\endgroup$
11
  • $\begingroup$ How did you let -120 be a coefficient? $\endgroup$
    – Aravind
    Nov 23, 2015 at 18:35
  • $\begingroup$ Is it valid to use -120 ? It is not on the board... $\endgroup$ Nov 23, 2015 at 18:35
  • $\begingroup$ You guys both didn't read the final sentence in the answer. $\endgroup$ Nov 23, 2015 at 18:35
  • $\begingroup$ Only polynomials in one variable imsc.res.in/~kapil/geometry/prereq1/node5.html $\endgroup$
    – Haobin
    Nov 23, 2015 at 18:36
  • $\begingroup$ @Haobin: there is only one variable in the polynomials above. The $y$ that I have used is a construction for the reader, not the participants of the game. $\endgroup$ Nov 23, 2015 at 18:37
3
$\begingroup$

I believe the OP's intended answer is:

Exactly the divisors of 120. This is true of the non-zero numbers on the board at any stage. If $P(x)=0$, then we can write it as $xg(x)+d=0$ and $d$ is a divisor of 120, this implies that so is $x$.

StillLearning's answer shows that all of them can be obtained.

Once $2,3,5$ are obtained, other divisors of 120 can be obtained by repeated division, eg: $2x-120=0$ to get $60$, then $2x-60-0$ to get $30$ etc.

$\endgroup$
3
$\begingroup$

I started like this

$$\begin{align} 120x + 120 = 0 &\rightarrow& x &= &-1\\ - x^{120} - x^{119} - ... - x^2 - x^1 +120 = 0 &\rightarrow&x &= &1\\ x + 120 = 0 &\rightarrow& x& = &-120\\ x^7 - x^3 + 120 = 0 &\rightarrow& x &= &-2\\ x - 2 = 0 &\rightarrow& x &= &2\\ \end{align} $$

Now we have $-120, -2, -1, 0, 1, 2, 120$.

Having both $-1$ and $1$ means that I can always get the negated value of any new number.

But I can't crack this puzzle as I keep finding new numbers.

Wonder if I got it all wrong...

Edit:

Some more (thanks to Aravind for the first 3)...

$$ \begin{align} x^2 + 2x - 120 = 0 &\rightarrow& x &= &10\\ 2x - 10 = 0 &\rightarrow& x &= &5\\ 10x - 120 = 0 &\rightarrow& x &= &12\\ x^4 + x^3 + x^2 + x - 120 = 0 &\rightarrow& x &= &3\\ \end{align} $$

And

$$ \begin{align} 2x - 120 = 0 &\rightarrow& x &= &60\\ 3x - 120 = 0 &\rightarrow& x &= &40\\ 5x - 120 = 0 &\rightarrow& x &= &24\\ 5x^4 + 10x - 120 &\rightarrow& x &= &4\\ 4x - 120 = 0 &\rightarrow& x &= &30\\ 4x^2 + 4x -120 &\rightarrow& x &= &5\\ 5x -120 = 0 &\rightarrow& x &= &24\\ 3x^2 + 2x - 120 = 0 &\rightarrow& x &= &6\\ 6x - 120 = 0 &\rightarrow& x &= &20\\\\ -2x^2 - x + 120 = 0 &\rightarrow& x &= &-8\\\\ -8x + 120 = 0 &\rightarrow& x &= &15\\ \end{align} $$

So far I have

$\{0, 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120\}$ (and all the negated numbers as well).

As far as I understand from other answers/comments this should be the complete list. I still wonder how that is proved.

$\endgroup$
8
  • $\begingroup$ You can only get divisors of 120. Can you get them all? $\endgroup$
    – Aravind
    Nov 23, 2015 at 18:51
  • $\begingroup$ Hmm... I see... I'll give it a try... 3 should be next then... $\endgroup$ Nov 23, 2015 at 18:52
  • $\begingroup$ You can get 10 because 10 times 12 is 120 and you have 1,2 already. $\endgroup$
    – Aravind
    Nov 23, 2015 at 18:53
  • $\begingroup$ 2x-10=0 gives 5, 10x-120=0 gives 12. $\endgroup$
    – Aravind
    Nov 23, 2015 at 18:56
  • $\begingroup$ @Aravind - I don't have 10 on the board yet $\endgroup$ Nov 23, 2015 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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