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

Postby Ralp » Wed Oct 17, 2012 9:14 pm UTC

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.

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

Re: Ordering of five or more players

Postby dudiobugtron » Wed Oct 17, 2012 10:55 pm UTC

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!
Image

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

Re: Ordering of five or more players

Postby ThirdParty » Thu Oct 18, 2012 12:54 am UTC

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

Postby Xias » Sat Oct 20, 2012 2:58 am UTC

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.

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

Re: Ordering of five or more players

Postby dudiobugtron » Sat Oct 20, 2012 5:47 am UTC

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

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

Re: Ordering of five or more players

Postby Ralp » Mon Oct 22, 2012 10:55 pm UTC

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.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 6 guests