Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I read the following question on this site:

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

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?

share|improve this question
    
@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

1 Answer 1

up vote 14 down vote accepted

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

share|improve this answer
    
Nice! Did you use a computer for this? –  joriki Dec 12 '11 at 20:18
1  
@joriki: Yes, I wrote a Python script for breadth-first search. –  mjqxxxx Dec 12 '11 at 22:12
3  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.