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?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
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$.

Improve this answer
$\endgroup$
3
  • $\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$
    – Fimpellizzeri
    Mar 24, 2016 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$
    – Fimpellizzeri
    Mar 24, 2016 at 19:03
  • $\begingroup$ I was too obsessed by primes to see it :) Nice job ! $\endgroup$
    – Fabich
    Mar 24, 2016 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$

Improve this answer
$\endgroup$
6
  • $\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, 2016 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, 2016 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, 2016 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, 2016 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$
    – Fimpellizzeri
    Mar 24, 2016 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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ This does not work: You cannot write all real roots of this polynomial on the blackboard. $\endgroup$
    – Haobin
    Mar 23, 2016 at 12:58
  • $\begingroup$ Is that so? Please tell me which one cannot be written. $\endgroup$
    – Ian MacDonald
    Mar 23, 2016 at 14:01
  • $\begingroup$ That's a monomial, not a polynomial. $\endgroup$
    – Hellion
    Mar 23, 2016 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, 2016 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, 2016 at 16:57

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.