8
$\begingroup$

8 very poisonous substances named s1 to s8 are kept in a safety room.
The substances are kept in ascending order (s1,s2,s3,s4,s5,s6,s7 and s8).
In the room there are 3 robots.

First robot can "rotate left" the order of the substances.
If the order is (a,b,c,d,e,f,g,h) the robot will make it (b,c,d,e,f,g,h,a)

Second robot can split the substances into 2 parts then reverse the order of each part.
If the order is (a,b,c,d,e,f,g,h) the robot will make it (d,c,b,a,h,g,f,e)
But the robot is a bit broken, so the resulting order is a bit wrong.
The resulting order will become (d,c,a,b,h,g,f,e).

Third robot can split the substances into 4 parts then reverse the order of each part
If the order is (a,b,c,d,e,f,g,h) the robot will make it (b,a,d,c,f,e,h,g)

Questions

How many minimum steps needed by using the robots to reverse the order into descending order :

  1. If the second robot is not broken.
  2. After the second robot is broken.

Show the steps !

$\endgroup$
  • $\begingroup$ You could have just named them the numbers (1,2,3,4,5,6,7,8) you know... $\endgroup$ – smci Nov 7 '16 at 10:31
  • $\begingroup$ Do you know of any way of proving that the minimum solution is the minimum other than brute-force search? If you do, you should post it as an answer — you might earn some more rep! $\endgroup$ – Peregrine Rook Nov 7 '16 at 17:25
8
$\begingroup$

Question 1 is already answered by others.

The answer to Question 2 is

14 steps

By doing

2 dcabhgfe
1 cabhgfed
3 achbfgde
1 chbfgdea
2 fbchaedg
2 hcfbgdea
1 cfbgdeah
1 fbgdeahc
2 dgfbchae
2 bfdgeahc
1 fdgeahcb
3 dfeghabc
1 feghabcd
2 hgfedcba

I'm pretty sure it's the least number of steps because I used a computer program to find it but I don't have a proof

$\endgroup$
  • $\begingroup$ There should be a way algebraically speaking to see if certain steps cancel each other out. $\endgroup$ – The Great Duck Nov 7 '16 at 16:04
5
$\begingroup$

It's

5 if the 2nd robot isn't broken.


(s1, s3, s3, s4, s5, s6, s7, s8)

2nd Robot

(s4, s3, s2, s1, s8, s7, s6, s5)

1st Robot x 4

(s8, s7, s6, s5, s4, s3, s2, s1)

Not sure for second

$\endgroup$
  • $\begingroup$ Right, it's easy for 1st question. The second question is much harder. $\endgroup$ – Jamal Senjaya Nov 7 '16 at 7:22
  • $\begingroup$ @JamalSenjaya yes it is! $\endgroup$ – Beastly Gerbil Nov 7 '16 at 7:23
  • 1
    $\begingroup$ first × 8 just lands you back at the original order. $\endgroup$ – Rubio Nov 7 '16 at 7:58
5
$\begingroup$

For unbroken robot,

5 steps is the best case; Beastly Gerbil already identified the solution:
second robot × 1, first robot × 4.

For broken robot,

the optimal solution is: 21312211221312.
I believe this matches what Ivo Beckers posted, and there are no better solutions.

- first robot rotating the sequence can't reverse the order.
- third robot exchanging pairs can't reverse the order, because two in a row just puts you back where you were; putting a rotation in the middle doesn't get it reversed; and after enough (4) repetitions of robot 3 + robot 1 you end up back where you started.
- second robot lets you order the first half in reverse, but not the second; cycling 4x to try to fix that will end up messing up the first half, leaving you (eventually) in the same place you'd be after one use of robot 3.
- however, other uses of robot 2 with other than 4 cycles can provide a solution.

In the interest of completeness,

an exhaustive search by a non-bugged computer determined there are 5 solutions of 16 moves, 1 solution of 14 moves, and nothing lower.

$\endgroup$
  • $\begingroup$ There is only 1 solution for 14 moves, but There are more than 30 solutions for 16 moves. $\endgroup$ – Jamal Senjaya Nov 8 '16 at 2:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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