Problem 2188

Solution:

We will show that the answer are the integer pairs $(u, v)$ such that $u \neq 0$, $v \neq 0$, $\{u, v\} \neq \{-1,1\}$ and $u>0$ or $v>0$.

If $u=0$ or $v=0$, then (i) will never yield a new number and we cannot use (ii) with only two numbers. Hence, if $u=0$ or $v=0$, we cannot reach every possible $y$. From now on, assume $u \neq 0$ and $v \neq 0$.

If both numbers $u, v$ were negative, we will show that there can only be negative numbers on the board. With negative numbers $a, b$, operation (i) will only yield a negative number. The same holds for operation (ii), because for a non-negative $x$ and negative $a, b, c$, we have $a x^{2}+b x+c<0$. Hence, if both $u<0$ and $v<0$, then we cannot reach every possible $y$. From now on, assume that at least one of $u, v$ is positive. Without loss of generality take $u<v$, and so $v>0$.

After one step, we can have the numbers $u, v, u+v$, which are mutually distinct due to $u, v$ being nonzero. Notice that the equation $u x^{2}+(u+v) x+v=0$ has a root $-1$, and so we can have $-1$ on the board.

We now check two cases: case $v=1$, and case $v>1$.

If $v=1$, then $u<0$. Further split the case of $v=1$ based on whether $u=-1$ or $u<-1$.

If $v=1$ and $u=-1$, we can only additionally write number $0$ on the board using operation (i); and no additional numbers using (ii) because setting $\{a, b, c\}$ to $\{-1,0,1\}$ in any order only has solutions for $x$ in $\{-1,0,1\}$. Hence, if $\{u, v\}=\{-1,1\}$, then we cannot reach every possible $y$.

If $v=1$ and $u<-1$, we can use operation (i) on numbers $u,-1$ (and then repeat choosing the obtained result and $-1$) to get any negative number smaller than $u$, and operation (i) on numbers $(u, 1)$ (and then repeat choosing the obtained result and $1$) to get any negative number larger than $u$, as well as $0$. Then, we set $(a, b, c)=(0,1,-2)$ and apply operation (ii) to additionally get number $2$. Applying (i) on $(2,1)$ (and then repeat choosing the obtained result and $1$), we can get all the remaining integers too.

From now on, assume $v>1$. Recall that we can make $u+v$ and $-1$.

We will now apply operation (i). First, $(v,-1)$ gives $v-1$. Next, $(v, v-1)$ gives $2 v-1$. Since $v>1$, we know $v \neq 2 v-1$, so we can apply operation (i) on $(v, 2 v-1)$ to get $3 v-1$, and then continue adding $(v, k v-1)$ to get $(k+1) v-1$ for any positive $k$. Since $v>1$, we can get an arbitrarily large integer by repeating this.

If $a$ is any positive number on the board, applying (i) to $(a,-1)$ gives $a-1$. By repeating this, we have that we can get all numbers smaller than $a$ and larger than or equal to $-1$. Together with previously having found a way to get an arbitrarily large integer, we have that we can get any integer $l \geq -1$ on the board.

Now, we set $(a, b, c)=(0,1,2)$ and apply operation (ii) to additionally get number $-2$. Then we can repeat operation (i) on $(-1,-2)$ (and afterwards on $-1$ and the obtained result) to get any negative number.

Therefore, if $u \neq 0, v \neq 0, \{u, v\} \neq \{-1,1\}$ and $u>0$ or $v>0$, we can write every integer on the board.

Solution:

If $u=0$ or $v=0$ then we can only get $\{u, v\}$.

Proof. If $u=0$ or $v=0$, then (i) will never yield a new number and we cannot use (ii) with only two numbers.

If $\max (u, v)<0$, we cannot get non-negative numbers.

Proof. For $a, b, c<0$ :
(i) cannot generate a non-negative number as $a+b<0$.
(ii) cannot generate a non-negative number as for $x \geq 0$ : $a x^{2}+b x+c \leq c<0$.

If $u+v \neq 0, u, v \neq 0$ and $\max (u, v)>0$, we can get every number.

Proof. $u \neq v \rightarrow u+v$ can be written. $u \neq 0$, so $u+v \neq v \rightarrow u+2 v$ can be written. $v \neq 0$, so $u+2 v \neq u$, meaning that $2 u+2 v$ can be written. If for $n>1, n(u+v)$ can be written then $(n+1)(u+v)=n(u+v)+(u+v)$ can also be written, because $u+v \neq 0$, so $n(u+v) \neq(u+v)$. Therefore, by induction for all $n>0$ the number $n(u+v)$ can be written.

Taking $n=2,3, \ldots$ and $(u+v)(x+1)(x+n)=(u+v) x^{2}+(u+v)(n+1) x+(u+v) n=0$ gives $x=-1$ and $x=-n \rightarrow$ for all $n>0$ we can get $-n$ (we can get all the negative numbers). Additionally, we can get $u+(-u)=0$.

For $n \geq 1$ we can take $0 \cdot x^{2}+u x+(-u n)=0$ as $u \neq 0 \rightarrow u,-n u, 0$ are all distinct, therefore we can get $n$. Thus, we can get all the numbers.

If $u+v=0$ and $\max (u, v)>1$ we can get all the numbers.

Proof. We can get $0=u+v$ as $u \neq v$. Take $0 \cdot x^{2}+u x-u=0$ so we can get $1$ written on the board. Take $(u', v')=(1, \max (u, v))$ and then use the result from claim 3. As $0<u'=1<\max (u, v)=v'$ and $u'+v'>0$ we can get all the numbers.

Remaining case: If $v=1$ and $u=-1$, we can only additionally write number $0$ on the board using operation (i); and no additional numbers using (ii) because setting $\{a, b, c\}$ to $\{-1,0,1\}$ in any order only has solutions for $x$ in $\{-1,0,1\}$. Hence, if $\{u, v\}=\{-1,1\}$, then we cannot reach every possible $y$.

Solution:

We show none of the initial number can be $0$, as in Solution 1. Then, we split into three cases: initial numbers having different signs, both being positive, and both being negative.

Case 1. Suppose we have two numbers $u, v$ with different signs such that $\operatorname{gcd}(u, v)=k$ for some $k \in \mathbb{Z}^{+}$. Without loss of generality assume that $u>0$ and $v<0$.

Case 1.1. $v<-k$ :
We can generate all numbers $y$ such that $k \mid y$ and $y \leq u$.

Proof. Define $u'=\frac{u}{k}, v'=\frac{v}{k}$. Note that by definition, $\operatorname{gcd}(u', v')=1$. If starting with numbers $u', v'$, we can make a sequence of applications of only the (i) rule to write a number $y=p \cdot u'+q \cdot v'$ on the board, then we can apply the same sequence of moves to $u, v$ to write $k \cdot y=p \cdot u+q \cdot v$ on the board.

Therefore, we will prove instead that if $v'<-1$, we can write all numbers $y<u'$ on the board, which is equivalent to the lemma.

We attempt to write numbers $u'+q \cdot v'$ for $q \in \mathbb{Z}^{+}$ on the board by repeatedly adding $v'$ to $u'$. This process can only ever halt if we reach a point where $u'+q \cdot v'=v'$. That cannot occur, as it would imply $u'=(1-q) \cdot v'$. Taking into account that $u', v' \neq 0$, that implies $\operatorname{gcd}(u', v')=|v'|$. That is a contradiction, as $|v'|>1$.

Therefore, we can write all numbers of the form $u'+q \cdot v'$ on the board for $q \in \mathbb{Z}^{+}$. We will use these numbers to construct an arbitrary integer $y$.

If we want to write a number $y<u'$ on the board, and we already have a number $n<y$ on the board such that $y \equiv n \pmod{u'}$, then we can construct $y$ by repeatedly adding $u'$ to $n$ until we reach $y$, skipping all numbers that are already on the board. As $y<u'$, none of the numbers we attempt to add $u'$ to will be equal to $u'$.

Suppose we fix any number $y<u'$. As $\operatorname{gcd}(u', v')=1$, $q \cdot v'$ takes all residues modulo $u'$ as $q$ runs through the positive integers. Therefore, we will always be able to find a number $n$ of the form $u'+q \cdot v'$ such that $y \equiv n \pmod{u'}$. We can generate an arbitrarily small $n'$ by taking $n'=n+l \cdot u' \cdot v'=u'+(q+l \cdot u') \cdot v'$ for large enough $l$, making both $n'<y$ and $n' \equiv y \pmod{u'}$ true.

Therefore, we can write all numbers $y<u'$ on the board. Thus, starting from $u$ and $v$, we can get all numbers $y \leq u$ such that $k \mid y$.

The numbers $k, 0$ and all negative multiples of $k$ are a subset of the integers $y \leq u$ such that $k \mid y$. Therefore, we have all of those numbers on the board.

We can now get an arbitrary nonzero number by applying (ii) to the polynomial $k \cdot (x-n)(x+n)=k \cdot x^{2}+0 \cdot x-n^{2} \cdot k$. The coefficients of this polynomial are distinct for all integers $n \neq 0$, and they are from the set $\{k, 0\} \cup \{q \cdot k \mid q<0\}$, which we have on the board. Therefore the rule application is valid.

As this works for all integers $n \in \mathbb{Z} \setminus \{0\}$, and $0$ is already on the board, we have proven that we can write all integers on the board.

Case 1.2. $v=-k$ :

Case 1.2.1. $k \neq 1$.
If $k \neq 1$, we can generate $-1$ from the polynomial $u \cdot x^{2}+(u+v) x+v$. We can now repeatedly add $-1$ to $v=-k$ until we reach $-2k$ on the board. Now, we can appeal to Case 1.1.

Case 1.2.2. $k=1$.
To restate the conditions of this sub-case, $v=-k=-1$, and $u$ is an arbitrary positive number.

Case 1.2.2.1. $u=1$.
If $u=1$, we are only ever able to construct the numbers $-1,0,1$, no matter how we apply the rules.

Case 1.2.2.2. $u \neq 1$.
We can subtract $1$ from $u$ until we reach $0$. This procedure also generates $1$. We now add $1$ to $u$ until we get all positive numbers.

Now, we find an arbitrary polynomial with different positive coefficients that have a negative root smaller than $-1$. An example is $(x+3)^{2}$.

We will now keep adding $-1$ to $-3$ to get all the negative numbers $y \leq -3$. To get $-2$, we can add $-3$ to $1$, generating all integers.

Case 2. Suppose that both of $u, v$ are positive.

We can now use any method from the previous solutions to generate a negative number, and then appeal to Case 1.

Case 3. Suppose $u<0, v<0$.

Then there can only be negative numbers on the board. With negative numbers $a, b$, operation (i) will only yield a negative number. The same holds for operation (ii), because for a non-negative $x$ and negative $a, b, c$, we have $a x^{2}+b x+c<0$. Hence, if both $u<0$ and $v<0$, then we cannot reach every possible $y$.