## Ordering of five or more players

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Ralp
Posts: 25
Joined: Sat Dec 16, 2006 9:44 am UTC
Location: internet
Contact:

### Ordering of five or more players

Is there a way to arrange a sequence of five (or n) players taking a sequence of 20 turns, in 4 rounds of 5 (or n-1 rounds of n turns), such that:
Each player gets exactly one turn each round,
Each player plays first, second, third, etc during a round no more once during the game,
Each player immediately follows each other player no more than once (ideally, exactly once if the sequence loops back around (in fact I conjecture that any solution will necessarily have this property)), and no player ever immediately follows him or herself. This criterion considers the first player in a round to immediately follow the last player in the prior round.

And if so what is such a way? (this ain't homework, I can actually use a solution!) I think this should be a simple coding theory problem but it's been a long time for me.

dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

### Re: Ordering of five or more players

Here's a start:

Spoiler:
For n=1 player it is possible (although a bit stupid).
For n=2 it is also trivially possible.

n=3 is where it gets interesting; it turns out (with a bit of trial and error) to be impossible:
123 <- first round without loss of generality.
Next turn has to be 2 (can't be 1 since 1 has already gone first, can't be 3 since then 3 would play twice in a row).
Then the next turn has to be 1 (3 can't follow 2 again)
So then you have no legal player for the last turn.

For n=4, the first two turns of the second round give you four different options; so lets investigate those.
a)
1234
2143
end
b)
1234
2413
end
c)
1234
3142
4 end
d)
1234
3421
41 end

Turns out it's impossible for n=4 as well.

I would conjecture that for n > 2 it will be impossible.
It seems like there are just too many different restrictions (If you made it to the nth turn of n-1th round, there would be (n-1) numbers it couldn't be because of the 'same round' rule, n-2 numbers it couldn't be because of the 'same position' rule, and n-1 numbers it couldn't be because of the 'can't follow twice or follow yourself' rule.)
I haven't proved it yet though!

ThirdParty
Posts: 347
Joined: Wed Sep 19, 2012 3:53 pm UTC
Location: USA

### Re: Ordering of five or more players

Spoiler:
I executed the following code. (Sorry for how ugly it is. I'm not a programmer.)

Code: Select all

`<html><head><script language="JavaScript">var followedYet = new Array(6);followedYet[0] = [2,1,0,0,0];followedYet[1] = [0,2,1,0,0];followedYet[2] = [0,0,2,1,0];followedYet[3] = [0,0,0,2,1];followedYet[4] = [0,0,0,0,2];var i = new Array(21);i[1] = 0;i[2] = 1;i[3] = 2;i[4] = 3;i[5] = 4;var depth = 6;function goDeeper() {   var a; var b; var j; var checkGroup;   if (depth <= 20) {      for (i[depth] = 0; i[depth] < 5; ++i[depth]) {         if ((i[depth] != i[depth-5]) && (i[depth] != i[depth-10]) && (i[depth] != i[depth-15])) {            checkGroup = 0;            for (j = depth-1; j%5 != 0; --j) {               if (i[depth] == i[j]) {                  checkGroup = 1;                  break;               }            }            if (checkGroup == 0) {               a = i[depth-1]; b = i[depth];               if (followedYet[a][b] == 0) {                  followedYet[a][b] = 1;                  ++depth;                  goDeeper();                  --depth;                  followedYet[a][b] = 0;               }            }         }      }   } else {      document.write("answer: ");      for (j = 1; j < depth; ++j) {         document.write(i[j]+1 + ",");         if (j % 5 == 0) {            document.write(";");         }      }      document.write("<br>");   }}</script></head><body>Running ...<script language="JavaScript">goDeeper();</script>... Ran</body></html>`
The output was "Running ... ... Ran".

So unless my code is buggy (which I doubt, since it had no trouble finding solutions if I decreased the total number of turns from 20 to 15), the answer to your question is: "No, it's not possible."

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

### Re: Ordering of five or more players

ThirdParty wrote:
Spoiler:
So unless my code is buggy (which I doubt, since it had no trouble finding solutions if I decreased the total number of turns from 20 to 15), the answer to your question is: "No, it's not possible."

I brute forced it by hand, and I agree with your conclusion.

dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

### Re: Ordering of five or more players

Not related to the puzzle, but to the motivation behind it - perhaps you could add some system to the game (cf: agricola) where players have the ability to forego some other benefit in order to get the first turn in each round (or a smaller benefit in order to secure later turns). That way the problem of turn order would become part of the game strategy, rather than an obstacle to it.

Ralp
Posts: 25
Joined: Sat Dec 16, 2006 9:44 am UTC
Location: internet
Contact:

### Re: Ordering of five or more players

Thanks all. I chose to just add a couple more rounds to the game, and change the constraints a little, such that everyone goes first, second, third etc at least once, instead of at most. It was easy to find solutions to this modified problem just by trial and error.