# 10 zeroes, 9 ones, and 8 twos are written on the board. Given the operations, can you set all numbers to become zero?

You are allowed to replace 0 and 1 with two 2s, 0 and 2 with two 1s, or one and two by two zeroes.
My thinking was that you had to set all numbers to 1 and 2. However, this isn't possible since there are an odd number of numbers and each operation modifies two.

• ... unless you are allowed to group numbers to form two-digit numbers. – Frpzzd May 23 '17 at 22:00
• You have the right idea. Your permutations are even, and you would need an odd permutation to get to your goal. – Doug M May 23 '17 at 22:03

## 2 Answers

Hint: Consider the total value modulo $3$ of the initial configuration and the final configuration. For each move, what is the effect of that move on the total value modulo $3$ of a configuration?

• I see. The mods don't change with the operations, so you can't get 0 mod 3. – Gerard L. May 23 '17 at 23:35

The modulo 3 answer is very good. Here's a geometrical solution:

These operations can be interpreted as moves in a three-dimensional space. Let $x$ be the number of $0$s, $y$ be the number of $1$s, and $z$ be the number of $2$s. We start out at $\vec{r} = (x,y,z) = (10,9,8)$. The operation "$0$ $1$ becomes $2$ $2$" can be interpreted as adding $\vec{u}=(-1,-1,2)$ to the current position. Likewise, "$0$ $2$ becomes $1$ $1$" and "$1$ $2$ becomes $0$ $0$" can be interpreted as adding $\vec{v} = (-1,2,-1)$ or $\vec{w}=(2,-1,-1)$, respectively, to the current position.

A solution to this problem would consist of three non-negative integers $a$, $b$, and $c$ such that $$(10,9,8) + a\, \vec{u} + b\, \vec{v} + c\, \vec{w} = (27, 0, 0)\, .$$ Taking the $y$ and $z$ components of this expression yields: \begin{align} 9 - a + 2b - c &= 0\\ 8 + 2a - b - c &= 0 \end{align} Subtracting the second of these from the first results in $$3(a-b)=1\, ,$$ which has no solution in integers $a$ and $b$. Thus there is no solution to the original problem.

• When I see "Here's a geometrical solution" I expect to see something I can visualize, not just more formulas! But I like your idea. Let's make it tangible: $x$ is rightwards, $y$ is forwards and $z$ is upwards from your starting point. If you can get onto the $x$ axis from your starting point of $(10,9,8)$, you win. Legal moves are: Two steps right, one step down and back; two steps forward, one step down and left; two steps up, one step left and back. The rest of your solution unfortunately is exactly equivalent to the modular arithmetic approach—not geometric at all. – Wildcard May 24 '17 at 3:41
• @Wildcard I like this idea too, even very much, coz it's so geometrical. In addition you may easily visualise it: The three moves $\vec{u},\vec{v}$, and $\vec{w}$ define a lattice in $L\subset\mathbb R^3$ which is 2-dimensional because $\vec{u} + \vec{v} +\vec{w}= \vec 0$, but any two out of $\{\vec{u},\vec{v},\vec{w}\}$ are linearly independent. Hence $\{a\,\vec u +b\,\vec v +c\,\vec w\mid a,b,c\in\mathbb N_0\} = \{p\,\vec u +q\,\vec{v}\mid p,q\in\mathbb Z\}=L$ and the question, ... – Hanno May 24 '17 at 15:35
• ... assuming $(10,9,8)$ as basepoint choice, asks if $(27, 0, 0)\overset{?}{\in} L\cup\{(10,9,8)\}$ belongs to the translated lattice. – Hanno May 24 '17 at 15:35
• Interesting geometric follow-up Q: If $(27, 0, 0)$ is not contained as it turned out, then which point or points in the translated lattice are closest? – Hanno May 24 '17 at 15:37
• @Hanno You are correct that these steps are confined to a plane. In fact, the set of accessible points lies on a hexagonal grid. I find that the closest reachable point to $(27,0,0)$ which does not go negative is $(26,1,0)$, which is achieved with $(a, b, c) = (2, 2, 10)$. – John Barber May 24 '17 at 15:47