# Is the solution to this holiday puzzle unique?

I read the following question on internet. this site:(the link is broken now.)

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.

Because 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?

-
@AustinMohr No, you can't "retrace" a path. For instance, the "+7" path will add seven, no matter which way you go through. Also, it specifically states you can't go through the same corridor twice in a row. – Arthur Dec 9 '11 at 7:07

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$.

-
Nice! Did you use a computer for this? – joriki Dec 12 '11 at 20:18
@joriki: Yes, I wrote a Python script for breadth-first search. – mjqxxxx Dec 12 '11 at 22:12
@mjqxxxx, regarding the shortest path that you have provided, which takes 13 operations starting with D: since you are beginning with 2018, you are in the middle and have just passed through +7. Having operation D first involves doing +7 first. This would make you do +7 twice in a row, which is illegal. – user22057 Dec 31 '11 at 20:06
@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.) – mjqxxxx Jan 1 '12 at 1:45