Moving Coins (find winning strategy)

Question

I have question about exercise Coin Slide on page 149 I found in "Thinking Mathematically" by Mason, Burton and Stacey. Here it is:

I was able to solve it successfully for $3-3$ case (original problem) and $4-4$ as well by try and error "strategy". But I'm looking for a conceptional strategy which can be extended to 5-5, 6-6, ...n-n cases. Let denote by $B$ the big circle, by $S$ the small circe, and by $-$ the gap of length of big circle and $.$ the gap of length of small circle. Then the possible solutions for $3-3$ and $4-4$ are:

Problem: I solved these two cases more less by try and error and unfortunatelly I ain't recognized a general "winning strategy" which can be successfully extended to $n-n$ case. The reason why I think that there exist such general winning strategy to attack every $n-n$ case is author's hint in the exercise: Remember Leapfrogs.

The Leapfrog exercise on p 52 is:

And the important thing is that elaboration of simpler cases of this exercise reveals a strategy that can easily applied to general cases:

That is the straight forward Leapfrog strategy is that after every move the colours in the row should alternate. The point is that since the author gives this Leapfrogs exercise as hint for my original Coin Slide problem, I think that there should be also exist a general winning strategy to attack it independent of $n$ in the $n-n$ case. Does somebody see how this exercise is related to Leapfrogs and what is the successful strategy in this game?

Answer 1

Here's a strategy that I think works but I can't say that is optimal. For simplicity, let's assume I can move more than 2 coins but always an even number. For example, moving 8 coins at once is the same as 4 moves of 2(as long as I am careful with the moves). Also, let $L_S$ denote the largest length of consecutive small coins and $L_B$ respectively of big coins.

• Step 1: Pick an $SB$ from the middle and move it to the end
• Step 2: Pick the $SS$ from the end and move it to the front
• Repeat steps 1 and 2 until it's not possible to do so

The invariant is that after every couple of steps either $L_S$ or $L_B$ will be increased by one.

Example: $5-5$

$Loop\ 1: bsbsbsbsbs \\ Step\ 1: bsbsbsbsSB \\ Step\ 2: SSbsbsbsbb \\ Loop\ 2: ss\_bsbsbs\_bb \\ Step\ 1: ss\_bsbsSB\_bb \\ Step\ 2: ss\_SSbsbb\_bb \\ Loop\ 3: ssss\_bs\_bbbb $

Close enough! Note that for even $n$ it would have worked as the outer $S...S$ and $B...B$ are always of even size. Let's finish the job for odd $n$. Just move the remaining $BS$ in the front and then the $S...S$ in the front and we are done.

Answer 2

Partial solution: Let $n = 4k + r$. The problem is solvable if $r = 0, 1, 3$.

The solution is actually very easy. Starting with the original pattern, working on the right side, using the OP's solution for $n=4$, we can arrange the last $8$ coins into ssssBBBB while not touching all other coins. Now that the ssssBBBB is established, we can move them all far away (i.e. some long distance away but still along the row) by moving them as ss, ss, BB, BB.

Do this repeatedly until there are $r <4$ pairs of coins left, and now we just need to arrange these remaining coins. If $r=0$ or $1$, they are already arranged, and if $r=3$ we can use the OP's $n=3$ solution to arrange them. Finally, re-assemble the whole row by moving all those far-away pairs back and attaching them to the correct end.

The only difficulty is the $r=2$ case. If $n=2$, I think the puzzle is unsolvable. The case I'm still undecided is $n=6$: Certainly my approach above won't work (since $n=2$ seems unsolvable), but is there a more clever way to solve $n=6$? I don't know.