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.
Asked
Active
Viewed 704 times
6
Gerard L.
- 2,536
-
... unless you are allowed to group numbers to form two-digit numbers. – Franklin Pezzuti Dyer 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
10
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?
Fimpellizzeri
- 23,126
-
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
6
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.
John Barber
- 3,924
-
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 03:41
-
2@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
-
1@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