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$
  • $\begingroup$ May the new X be any integer or is it limited in some range? $\endgroup$ – 4386427 Nov 23 '15 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 '15 at 18:08
  • $\begingroup$ @StillLearning The new x may be any integer, no limits. $\endgroup$ – Haobin Nov 23 '15 at 18:17
  • 3
    $\begingroup$ You should exclude the zero polynomial. $\endgroup$ – f'' Nov 23 '15 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 '15 at 19:04
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$
  • $\begingroup$ Cool. Best answer. Thanks for the link. $\endgroup$ – 4386427 Nov 23 '15 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$
  • $\begingroup$ How did you let -120 be a coefficient? $\endgroup$ – Aravind Nov 23 '15 at 18:35
  • $\begingroup$ Is it valid to use -120 ? It is not on the board... $\endgroup$ – 4386427 Nov 23 '15 at 18:35
  • $\begingroup$ You guys both didn't read the final sentence in the answer. $\endgroup$ – Ian MacDonald Nov 23 '15 at 18:35
  • $\begingroup$ Only polynomials in one variable imsc.res.in/~kapil/geometry/prereq1/node5.html $\endgroup$ – Haobin Nov 23 '15 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$ – Ian MacDonald Nov 23 '15 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$
  • $\begingroup$ You can only get divisors of 120. Can you get them all? $\endgroup$ – Aravind Nov 23 '15 at 18:51
  • $\begingroup$ Hmm... I see... I'll give it a try... 3 should be next then... $\endgroup$ – 4386427 Nov 23 '15 at 18:52
  • $\begingroup$ You can get 10 because 10 times 12 is 120 and you have 1,2 already. $\endgroup$ – Aravind Nov 23 '15 at 18:53
  • $\begingroup$ 2x-10=0 gives 5, 10x-120=0 gives 12. $\endgroup$ – Aravind Nov 23 '15 at 18:56
  • $\begingroup$ @Aravind - I don't have 10 on the board yet $\endgroup$ – 4386427 Nov 23 '15 at 18:58

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.