6
$\begingroup$

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.

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

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?

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Wildcard May 24 '17 at 3:41
  • 2
    $\begingroup$ @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, ... $\endgroup$ – Hanno May 24 '17 at 15:35
  • $\begingroup$ ... assuming $(10,9,8)$ as basepoint choice, asks if $(27, 0, 0)\overset{?}{\in} L\cup\{(10,9,8)\}$ belongs to the translated lattice. $\endgroup$ – Hanno May 24 '17 at 15:35
  • $\begingroup$ 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? $\endgroup$ – Hanno May 24 '17 at 15:37
  • 1
    $\begingroup$ @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)$. $\endgroup$ – John Barber May 24 '17 at 15:47

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.