15
$\begingroup$

I read the following question on internet.

Start at 2011. By moving through the maze and doing any arithmetic operations you encounter, exit the maze with a result of 2012. You may pass through an operation several times, but not twice in a row.

enter image description here

Out of curiosity, I'd like to ask the following two questions:

  • One solution is on the site. Is the solution to this problem unique?

  • How can we find a solution?

1 Answers 1

17

Note that if a fractional value is ever reached (by applying $[\div 2]$ to an odd number), no integer is subsequently reachable. Therefore, the first move must be $[+7]$, giving $2018$. Similarly, since $2012$ is not divisible by three, the last move must be $[-5]$, starting from $2017$. The walk from $2018$ to $2017$ must consist of any number of the following "loop" operations, taken in any order:

  • $A=[\times 3][-5],\qquad A(x)=3x-5$
  • $B=[-5][\times 3],\qquad B(x)=3x-15$
  • $C=[\div 2][+7], \qquad C(x)=\frac{1}{2}x+7$; apply to even $x$ only
  • $D=[+7][\div 2], \qquad D(x)=\frac{1}{2}x+\frac{7}{2}$; apply to odd $x$ only.

The shortest walk from $2018$ to $2017$ takes 13 such operations: $DAC^3A^4D^2C^2$, corresponding to a solution with 28 moves: $ \begin{eqnarray} 2011&\xrightarrow{[+7]}&2018\xrightarrow{C}1016\xrightarrow{C}515\xrightarrow{D}261\xrightarrow{D}134\xrightarrow{A}397 \\ &\xrightarrow{A}&1186\xrightarrow{A}3553\xrightarrow{A}10654\xrightarrow{C}5334\xrightarrow{C}2674 \\ &\xrightarrow{C}&1344\xrightarrow{A}4027\xrightarrow{D}2017\xrightarrow{[-5]}2012. \end{eqnarray} $ The solution is not unique; the next-shortest walk is of length 16: $C^2D^2C^3B^2ABDACAD$. Not surprisingly, there are also families of solutions of arbitrary length. For instance, $C(14)=14$, and so any solution passing through $14$ can be padded with any number of copies of $C$. The shortest such family is $C^2A^2B^2A^2C^{k}D^3CDACD^2C^2$.

  • 0
    @asta: You're right! Appropriate timing, too, coming on the evening of the actual transition from 2011 to 2012. That invalidates the results in the post... in fact, you can't have a $D$ on the right, or an $A$ on the left, or have substrings $AB$ or $BA$ or $CD$ or $DC$ anywhere in the interior. The shortest-walk solution I posted is *almost* correct: there's a single $DC$ in the interior. The other solutions are way off. (The strings are to be read right-to-left, by the way, so the operation on $2018$ is a $C$, which is legal.)2012-01-01