Page 1 of 1

Ordering of five or more players

Posted: Wed Oct 17, 2012 9:14 pm UTC
by Ralp
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.)

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

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.