11
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Fimpellizieri Mar 24 '16 at 18:45
  • $\begingroup$ Oh, sorry, one of them is already $0$ as per the question's hypotheses, and thus $n \geq 2$. Answer's perfect! $\endgroup$ – Fimpellizieri Mar 24 '16 at 19:03
  • $\begingroup$ I was too obsessed by primes to see it :) Nice job ! $\endgroup$ – Fabich Mar 24 '16 at 21:39
3
$\begingroup$

Partial Answer : (?)

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$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – hexomino Mar 23 '16 at 16:46
  • $\begingroup$ yes any non null number is enough to get 1 and -1 I should have started with it $\endgroup$ – Fabich Mar 23 '16 at 17:32
  • 1
    $\begingroup$ How is 30 a root of $x-\frac1{30}$? You should use $\frac1{30}x-1$. $\endgroup$ – wythagoras Mar 23 '16 at 18:30
  • 1
    $\begingroup$ 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. $\endgroup$ – xnor Mar 24 '16 at 0:38
  • $\begingroup$ 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. $\endgroup$ – Fimpellizieri Mar 24 '16 at 6:12
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This does not work: You cannot write all real roots of this polynomial on the blackboard. $\endgroup$ – Haobin Mar 23 '16 at 12:58
  • $\begingroup$ Is that so? Please tell me which one cannot be written. $\endgroup$ – Ian MacDonald Mar 23 '16 at 14:01
  • $\begingroup$ That's a monomial, not a polynomial. $\endgroup$ – Hellion Mar 23 '16 at 15:25
  • $\begingroup$ @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. $\endgroup$ – Dennis Meng Mar 23 '16 at 15:35
  • $\begingroup$ @IanMacDonald well, yes, monomials are, technically speaking, a sub-class of polynomials. So you are technically correct (the best kind of correct! :-) ). $\endgroup$ – Hellion Mar 23 '16 at 16:57

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.