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.

Re: Ordering of five or more players

Posted: Wed Oct 17, 2012 10:55 pm UTC

by dudiobugtron

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!

Re: Ordering of five or more players

Posted: Thu Oct 18, 2012 12:54 am UTC

by ThirdParty

Spoiler:

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

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."

Re: Ordering of five or more players

Posted: Sat Oct 20, 2012 2:58 am UTC

by Xias

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.

Re: Ordering of five or more players

Posted: Sat Oct 20, 2012 5:47 am UTC

by dudiobugtron

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.

Re: Ordering of five or more players

Posted: Mon Oct 22, 2012 10:55 pm UTC

by Ralp

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.