5
$\begingroup$

We have 10 sheep: 5 black and 5 white, two shores and a bridge through a river. 5 black sheep on a shore and 5 white sheep on another one. We have to move sheep on the opposite side. Sheep can move only forwards and jump through one sheep on an empty space. How to change side for every sheep?

Example:

Right:

11111_00000
1111_100000 - 1 steps right
111101_0000 - 0 jumps left

Wrong:

11111_00000 - 
1111_001000 - 1 jumps through 2 sheep is wrong

Wrong:

11111_00000
1111_100000 - 1 steps right
11111_00000 - 1 steps left is wrong

Wrong:

111011_0000
110111_0000 - you can move a sheep only on the empty space
$\endgroup$
  • $\begingroup$ I believe this question is asked before... $\endgroup$ – Oray Feb 3 '18 at 18:44
  • $\begingroup$ I didn't find it. $\endgroup$ – TigerTV.ru Feb 3 '18 at 18:46
  • $\begingroup$ that's fine, just I know the question maybe... $\endgroup$ – Oray Feb 3 '18 at 18:47
  • $\begingroup$ If you know the question than you know the answer. $\endgroup$ – TigerTV.ru Feb 3 '18 at 18:51
  • 1
    $\begingroup$ ...and after all that I find out it was a dupe :( Oh well, nice question anyway! $\endgroup$ – Jonathan Allan Feb 3 '18 at 22:06
3
$\begingroup$

I can, using a method devised below, do it in

35 moves

Starting with a simple case, 1_0, it's pretty obvious the optimal steps are:

1_0        1_0
_10   or   10_
01_        _01
0_1        0_1

both of which take three moves (we know we can always invert solutions like the above).

At each point there are at most four choices, move the sheep that is two to the left of the space, one to the left of the space, one to the right of the space, or two to the right of the space. Let's call these moves L,l,r, and R; now the simple solutions above are lRl and rLr (both palindromes).

Now lets look at the next puzzle, 11_00:

11_00
1_100 l
101_0 R
1010_ r
10_01 L
_0101 L
0_101 r
001_1 R
00_11 l  -> lRrLLrRl  = lR + rLLr + Rl

You can see that this solution, lRrLLrRl is a palindrome again and that it starts and ends just as the solution to 1_0. If we do the same for 111_000 we should start with lRrLL, do something to reverse the line up of sheep and space then do LLrRl...

111_000
11_1000 l  << this stage is the
1101_00 R  << same instructions
11010_0 r  << as the first half
110_010 L  << of the previous
1_01010 L  << plus one instruction:  lRrLL
           ... now we want to get to 01010_1 so,...
_101010 l  ... keep going left as fast as we can to the edge...
01_1010 R  ... then right as fast as we can...
0101_10 R
010101_ R  ... and then make the centre a palindrome...
01010_1 l  ... with a single last instruction, to find us at the right place!...
           ... then just use the reverse instructions from before...
010_011 L  << these ones
0_01011 L  << are just
00_1011 r  << the reverse
0001_11 R  << of the beginning
000_111 l  << which is LLrl
           i.e. lRrLL + lRRRl + LLrRl = lRrLLlRRRlLLrRl

Note that what was performed in the middle is exactly like what was performed in the middle of the previous puzzle (move as fast as possible in the same direction until the space hits the edge it was travelling toward, then go as fast as possible in the other direction, then palindrome-ise the centre instructions so as to get to the reverse of what had been reached before the process, then add the reverse of the start to complete a palindromic instruction set.

If we repeat this procedure we will find a solutions of length

$s=(p+1)^2-1$

where $p$ is the count of pairs of sheep.

For 1111_0000 we get:

1111_0000
111_10000 l
11101_000 R
111010_00 r
1110_0100 L
11_010100 L
1_1010100 l
101_10100 R
10101_100 R
1010101_0 R

10101010_ r
101010_01 L
1010_0101 L
10_010101 L
_01010101 L
0_1010101 r

001_10101 R
00101_101 R
0010101_1 R
001010_11 l
0010_0111 L
00_010111 L
000_10111 r
00001_111 R
0000_1111 l  -> lRrLLlRRR + rLLLLr + RRRlLLrRl = lRrLLlRRRrLLLLrRRRlLLrRl (24)

Finally, for the puzzle in question, 11111_00000 (five pairs) we find this solution (and of course its inverse):

35 moves: lRrLLlRRRrLLL + LlRRRRRlL + LLLrRRRlLLrRl:

 11111_00000
 1111_100000 l
 111101_0000 R
 1111010_000 r
 11110_01000 L
 111_0101000 L
 11_10101000 l
 1101_101000 R
 110101_1000 R
 11010101_00 R
 110101010_0 r
 1101010_010 L
 11010_01010 L
 110_0101010 L
 1_010101010 L  << centre portion starts with this move
 _1010101010 l
 01_10101010 R
 0101_101010 R
 010101_1010 R
 01010101_10 R
 0101010101_ R
 010101010_1 l
 0101010_011 L << and ends with this one
 01010_01011 L
 010_0101011 L
 0_010101011 L
 00_10101011 r
 0001_101011 R
 000101_1011 R
 00010101_11 R
 0001010_111 l
 00010_01111 L
 000_0101111 L
 0000_101111 r
 000001_1111 R
 00000_11111 l

$\endgroup$
  • $\begingroup$ Jonathan Allan: It is great!!! $\endgroup$ – TigerTV.ru Feb 3 '18 at 22:58
2
$\begingroup$

I was originally going to post a step by step solution, but I realized that it would be very long and tedious. However, I was able to complete a puzzle using physical tokens in my house.

The strategy is to start by getting each sheep alternating black, white, black, etc.

Then

You can move each piece out to it's respective side

It would be long and confusing (but possible) to post a thorough solution using the number format you showed.

Here's a video that will give you the general idea of what this strategy is trying to accomplish. It shows a similar puzzle with four pegs on each side (instead of five sheep). The rules of the puzzle differ slightly, in such a way that only even-numbered puzzles are possible.

$\endgroup$

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