10
$\begingroup$

5 persons numbered 1 to 5 are standing in a row at 5 spots.

1 2 3 4 5

Any person can call another person among the remaining 4. When someone calls someone else, the person who was called comes on the adjacent spot toward his side, on the same side of the person that called him, and then the others rearrange themselves accordingly. (see example ahead)

Now the first and last spot are special. After each time someone calls someone else, subsequent to the rearrangement, the two persons standing on the first and last spot teleport to each others’ spots!

For example, if person 2 calls person 5, and after rearrangement and teleportation, person 1 calls person 4, these two steps can be represented in the following way:

enter image description here

They can’t call anyone who’s already adjacent to them of course, since they’re already on their side, and it won't be counted as a step.

What is the minimum number of steps that’ll take for the people for going

from:

1 2 3 4 5

to:

5 4 3 2 1

NOTE: I'm new at creating puzzles, I might have missed some important detail, so please bear with me. I'll try to respond promptly to the comments and make any required changes.

$\endgroup$

2 Answers 2

7
$\begingroup$

I think it can be done in 3 calls (and 3 corresponding switches).

1 2 3 4 5     
              (2 calls 4)
5 2 4 3 1     (4 moves next to 2, then 1 and 5 switch) 
              (5 calls 4)
1 4 2 3 5     (4 moves next to 5, then 5 and 1 switch again) 
              (4 calls 3)
5 4 3 2 1     (3 moves next to 4, and 5 and 1 switch one last time) 

A brilliant observation from Tyler Seacrest

Note that there is no one move solution, because after one move, either 5 or 1 is in the correct ending position. Then, after another move, the 5 or 1 is no longer in the correct ending position. So there is no two-move solution either.

$\endgroup$
6
  • $\begingroup$ This is what I have written on a post-it, and I can't think of how to do it better! $\endgroup$
    – Bailey M
    Commented Aug 7, 2015 at 17:49
  • $\begingroup$ Haha, beat me to it for sure. I blame my mangled finger, but I came up with the same solution. $\endgroup$
    – Josh
    Commented Aug 7, 2015 at 17:50
  • $\begingroup$ I'm also keen on seeing if this can be bettered. $\endgroup$
    – CodeNewbie
    Commented Aug 7, 2015 at 17:53
  • $\begingroup$ Note that, although there is no one move solution, after one move, either 5 or 1 is in the correct ending position. Then, after another move, the 5 or 1 is no longer in the correct ending position. So there is no two-move solution. $\endgroup$ Commented Aug 7, 2015 at 17:53
  • $\begingroup$ ^ that makes sense. @CodeNewbie, This seems to be the solution. I guess I can make it more complex by adding more people, or more weird contraptions like the teleportation thing. Any suggestions on having such a variation that is more elegant and not too complex? $\endgroup$ Commented Aug 7, 2015 at 17:58
1
$\begingroup$

3 steps.

Like this:

12345 -> 52431 -> 14235 -> 54321

or because of the symmetry:

12345 -> 53241 -> 13425 -> 54321


Edit: if there are more people, we can do this (omitting the first and the last end):

$2, 3, ..., n-1$
$n-1, 2, 3, ..., n-2$

Now that we've managed to put $n-1$ in its right place, we can drag others next to it.

After putting numbers from 2 to $n-2$ ($n-3$ numbers) into their right place in $n-4$ more moves, we'll have made $n-3$ in total. If $n-3$ is odd ($n$ is even), it can be done. Otherwise we start with the ones from 5 to $n-2$ ($n-6$ numbers) in $n-6$ more moves, then finish the 432 part with another 3 moves, making $n-2$ moves in total:

234
324
342
432

or

234
243
423
432

$\endgroup$
2
  • $\begingroup$ For the general case, what if involving the first and last spots in the rearrangements makes a difference and reduces the number of steps? Your algorithm is valid, and works for 5 people I understand, but I was just wondering if involving first and last spot people make any difference. $\endgroup$ Commented Aug 8, 2015 at 2:35
  • $\begingroup$ No, it doesn't. Edited accordingly to make it clearer. $\endgroup$
    – Nautilus
    Commented Aug 8, 2015 at 10:31

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