# Moving back and forth between two terrible fates

You have been taken prisoner and your captor has set a fiendish problem with which to torture you.

You are stood between two terrible fates. Two steps in front of you is a nest of angry vipers. Two steps behind you is sheer cliff with a drop to certain death. Taking one step forward or back is safe but taking two steps in either direction will be fatal.

Your villainous captor has promised to let you go free if you can write a safe pattern of 12 steps. Unfortunately he will choose whether you follow all the step or every 2nd, 3rd, 4th, 5th or 6th step.

Can you find a pattern that will ensure your release?

Rules:

1. Each step must be forward or back you can not choose to stay still or move in any other direction.
2. The sequence must work for all of the following conditions
• all steps 1,2,3,4,5,6,7,8,9,10,11,12 are followed
• only multiples of 2 - steps 2,4,6,8,10,12
• only multiples of 3 - steps 3,6,9,12
• only multiples of 4 - steps 4,8,12
• only multiples of 5 - steps 5 and 10
• only multiples of 6 - steps 6 and 12

The origin of the puzzle is this video https://www.youtube.com/watch?v=pFHsrCNtJu4

(Spoiler warning : the video contains the solution)

No, it's not possible.

Your first and second moves must be in opposite directions, or you die. Then, you're back to the start position, so your third and fourth steps must be in opposite directions, and so on. So, these pairs of moves must be opposites.

$$(1,2), (3,4), (5,6), (7,8), (9,10), (11,12)$$

The same must be true for the sequence of every second step, or every third step, and so on.

$$(2,4), (6,8), (10,12)$$ $$(3,6), (9,12)$$ $$(4,8)$$ $$(5,10)$$

But then steps $9$, $10$, and $12$ must all be opposite to each other, a contradiction.

We could make $11$ steps though, since those edges form a bipartite graph. The solution is unique up to reflection.

$$RLLRLRRLLRL$$

Also, if the restriction was weakened to step sizes being powers of 2, we could survive for arbitrarily many steps using the Thue-Morse sequence.

• Does anyone know how many moves you can make if you can move at most $k$ steps from the origin? I have some very vague memory of some theorem of Erdos (?) that it must still be finite and some connection to the prime-counting function. – xnor Apr 19 '15 at 1:19
• It's called the Erdos Discrepancy Conjecture. It's known to be finite for $k=2$ (by exhaustive search) but AFAIK is wide open above that. – Lopsy Apr 19 '15 at 5:46

You are doomed.

In any successful list,

• Instructions 5 and 6 must differ. Consider what happens when you follow all instructions. Steps 1 and 2 must bring you back to the starting square (else you would die). Same for 3 and 4. Thus, 5 and 6 must differ, else you will take 2 steps in the same direction from the starting square.

• Instructions 6 and 12 must differ, to prevent death in the multiples of 6 case.

• Instructions 12 and 9 must differ, for the multiples of 3 case. Instructions 3 and 6 either kill you, or bring you back to the start, so 9 and 12 must differ.

• Instructions 9 and 10 must differ, by identical reasoning to the first bullet point.

• Instruction 10 and 5 must differ, else you die when you follow multiples of 5.

So, 5 differs from 6 differs from 12 differs from 9 differs from 10 differs from 5, implying step 5 differs from step 5, a contradiction.