1
$\begingroup$

We see the standard version of the puzzle in:
The Puzzle That's HARDER After Seeing the Solution!

Which corresponds to the case $n=2$ in my follow up problem.

5 coin puzzle

In short, you are presented with 2 types of coins (let there be small ones and big ones since we all are not using the same currencies), which are laid out in a straight line like: $\text{OoOoO}$

Your goal is to reach the sorted state of coins: $\text{OOOoo}$

By respecting the Rules:

  • You may only move 2 conjoined coins that are not of the same type per move.

  • The held coins cannot be twisted, separated or used to push other coins around.

  • All coins need to be aligned on the same line.

In the linked video, the best solution using only $4$ moves is shown.
There is also a $5$ move solution shown in the video, which would apply to a restricted variant that includes:

  • Upon releasing the coins, at least one of the held coins must be touching one other coin.


Follow Up Problem

I want to know if there exist solutions for $2n+1$ coins or not, and if there is a best generalized method to reach them in least moves.

(Both for the standard set of rules and the restricted variation)

The solution for $n=1$ is trivial: we have $\text{OoO}$ where $1$ move solves to $\text{OOo}$ and holds for both variations.

The solutions for $n=2$ are shown in the video. ( $4$ and $5$ moves )

For $n=3$ we have: $\text{OoOoOoO}$ , where I found a solution in $11$ moves for standard set of rules, and one in $15$ moves for a restricted variation.

The solutions for $n\ge4$ are yet to be found or proven impossible.
(I believe that all $n$ have a valid solution following a similar pattern)


In the video, they reference the case they are showing as "11 cent puzzle", since they are using dimes and cents, thus you are always moving 11 cents per move.

Solution update

I have found a general solution that solves it in $n^2$ moves, and in $\frac{n(3n-1)}{2}$ moves for the restricted variation.

This is better than my previous solutions for $n=3$, and I believe the optimal method.

It wasn't actually that complicated. I will post it if no one is able to solve it ( or at least find a general solution of their own ).

$\endgroup$
4
  • $\begingroup$ It likely isn't 11 cents as there's no way to add 2x+3y to get 11 in a system where the choices for x,y are 1, 5, 10, 25. $\endgroup$ Mar 11, 2017 at 12:59
  • $\begingroup$ @IanMacDonald You didn't even watch the video. 11 cents come from the fact that you are moving 11 cents at a time. 10+1 is 11 $\endgroup$
    – Vepir
    Mar 11, 2017 at 13:05
  • $\begingroup$ Is the final state allowed to have gaps between coins? E.g. OOxOOxooo, where 'x' is a gap. $\endgroup$
    – Lawrence
    Mar 11, 2017 at 15:04
  • $\begingroup$ @Lawrence No gaps in the final solution. $\endgroup$
    – Vepir
    Mar 11, 2017 at 16:28

1 Answer 1

4
$\begingroup$

Here is a general solution for the standard version.

It is easiest to do it in reverse, starting at the end, because then there are not so many movable pairs. I'll denote the two coin types by X and O. The solution works by reversing an XOXOXO sequence to an OXOXOX sequence by pasting it next to a loose O and then removing the other end, i.e. O+XOXOXO = OXOXOX+O. With this trick as a building block, you can turn a separated sequence OOOOXXXX of even length to an alternating sequence OXOXOXOX from the inside out by reversing successively larger strings of alternating coins.

 ................................OOOOOOXXXXX..
 ..............................OXOOOOO..XXXX..
 ..............................O..OOOOXOXXXX..
 ..........................OXOXO..OOO....XXX..
 ..........................O......OOOXOXOXXX..
 ....................OXOXOXO......OO......XX..
 ....................O............OOXOXOXOXX..
 ............OXOXOXOXO............O........X..
 ............O....................OXOXOXOXOX..
 ..OXOXOXOXOXO................................
This solution takes $n^2$ moves: The first reversal takes $1+1$ moves, the second $2+2$ moves, ... the last reversal takes $2(n-1)$ moves, and after that we need a final $n$ moves to join up the loose O with the alternating sequence of length $2n$. The solution therefore takes $1+2+3+...+(n-1)+n+(n-1)+...+3+2+1 = n^2$ moves.

Here is a general solution for the restricted rule set.

In the normal solution, it all works except for the first $n$ moves. These are the moves that go to here:

 ............O....................OXOXOXOXOX..
from here:
 ..OXOXOXOXOXO................................
These $n$ moves need to be replaced by a set of $n(n+1)/2$ moves, each of which simply moves the leftmost OX and appends it at the right-hand side. This gives a restricted solution of $n(n+1)/2 + n^2 - n = n(3n-1)/2$ moves.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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