# Blackboard problem with polynomial

At the beginning the blackboard contains $n$ real numbers, one of which is $0$. In every step, we may take any polynomial such that all its coefficients are currently on the blackboard, we compute all real roots of this polynomial and also write them on the blackboard. After some time you look at the blackboard and see all the integer numbers from -2016 to +2016 written on it.

What is the smallest possible value $n$ for this story to happen?

The smallest possible value of $n$ is

$2$. The numbers written on the board initially could be $0$ and $2016!$.

Claim: We can get every non-negative integer $n\leq 2016$ on the board.

Proof: By induction. We start with $n=0$ on the board. We can get $1$ using Lord of the Dark's method: $2016!x+2016!=0$ has $-1$ as a root, $-x^2+2016!=0$ has $\pm\sqrt{2016!}$ as roots, and $\sqrt{2016!}x-\sqrt{2016!}$ has $1$ as a root.

Now suppose we have $0,1,2,\ldots,n-1$ written on the board. We can write $2016!$ in base $n$: $$2016!=\sum_{i=1}^k a_i n^i,$$ where $a_i\in\{0,1,\ldots,n-1\}$. The sum starts at $i=1$ instead of $i=0$ because $2016!$ is divisible by $n$. Now we get $n$ as the root of $$\sum_{i=1}^k a_i x^i-2016!=0$$ (we can get $-2016!$ on the board as a root of $x+2016!=0$). $\blacksquare$

So we have $0,1,\ldots,2016$ on the board. For each $n$ on the board, we can get $-n$ as a root of $x+n=0$. This gives every integer between $-2016$ and $2016$.

• You don't need $0$ on the board. For any nonzero $a$, $aX$ has $0$ as a root. I guess this also shows self-evidently that the smallest possible value for $n$ is $1$. Besides that, very nice answer and reasoning! Mar 24, 2016 at 18:45
• Oh, sorry, one of them is already $0$ as per the question's hypotheses, and thus $n \geq 2$. Answer's perfect! Mar 24, 2016 at 19:03
• I was too obsessed by primes to see it :) Nice job ! Mar 24, 2016 at 21:39

you need at most all the (positive) prime numbers and 0. You can probably do better... OR prove that this is the minimal solution !

Explanation :

* -1 is the root of $aX+a$ (for any non-null a)
* with a>0 : $aX²-1$ gives you $+-\sqrt{\frac{1}{a}}$ and 1 is the root of $\sqrt{\frac{1}{a}}X-\sqrt{\frac{1}{a}}$
* Once we have a number Y we can take the root of $X + Y$ (which is -Y) so we only need to find positive numbers.
* If you have all the prime numbers at your disposal you can find every non prime with easy iterations on polynomial of degree 1 (see example after)

Example :

Example on $30 = 5*3*2$.
* the root of $5X-1$ is $\frac{1}{5}$.
* the root of $3X-\frac{1}{5}$ is $\frac{1}{15}$
* the root of $2X-\frac{1}{15}$ is $\frac{1}{30}$
* the root of $\frac{1}{30}X-1$ is $30$

• Of course you also need 1 at the beginning to make the polynomial X+Y (i.e, the coefficient of X) so perhaps this needs to be included at the start? Mar 23, 2016 at 16:46
• yes any non null number is enough to get 1 and -1 I should have started with it Mar 23, 2016 at 17:32
• How is 30 a root of $x-\frac1{30}$? You should use $\frac1{30}x-1$. Mar 23, 2016 at 18:30
• Maybe you can use the rational root theorem to argue that if a prime wasn't present at the start, then you can't get it via roots? I could imagine though that you could go through irrational numbers as a step to rational ones.
– xnor
Mar 24, 2016 at 0:38
• Any nonzero number gets you $-1$, but how do you get $1$ from there? Remember that in $X^2 - 1$ the coefficient of $X^2$ is $1$ itself. Mar 24, 2016 at 6:12

The smallest value is 1.

When 0 is the only number written on the board, we can construct the polynomial
$$0x$$
All numbers can be written on the board as real roots of this polynomial, which is a set that certainly includes all integers from -2016 to 2016.

• This does not work: You cannot write all real roots of this polynomial on the blackboard. Mar 23, 2016 at 12:58
• Is that so? Please tell me which one cannot be written. Mar 23, 2016 at 14:01
• That's a monomial, not a polynomial. Mar 23, 2016 at 15:25
• @IanMacDonald The set of all reals (and hence the set of all roots of your polynomial) is uncountably infinite, whereas any infinite set that can be made into an infinitely long list is "only" countably infinite. I'm assuming Haobin either wants countably infinite, or won't allow infinite sets at all. Mar 23, 2016 at 15:35
• @IanMacDonald well, yes, monomials are, technically speaking, a sub-class of polynomials. So you are technically correct (the best kind of correct! :-) ). Mar 23, 2016 at 16:57