Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Rock Paper Scissors for arbitrary odd number of elements

Tags:

math

How do I efficiently create a rock-scissors-paper game for n elements, where n is any odd number >=3.

In other words, I want a non-transitive complete ordering of n elements such that each element is greater than (n-1)/2 other elements and each element is lesser than (n-1)/2 other elements.

like image 285
Barry Carter Avatar asked May 30 '10 19:05

Barry Carter


1 Answers

Assume your items are numbered 0,1,2,...,n-1.

Item i beats item j iff i - j (mod n) > (n-1)/2.

In other words you can rotate the list such that your chosen item is in the middle of the list:

i - (n-1) / 2, ..., i-2, i-1, i, i+1, i+2, ..., i + (n-1) / 2

Then item i beats all the items below it in the list.

A matrix of i vs j would look like this:

  0 1 2 3 4
0 - L L W W
1 W - L L W
2 W W - L L
3 L W W - L
4 L L W W -

This is not the only possibility, but it is probably the simplest. You can construct any matrix that obeys these rules:

  • All values on the diagonal are zero.
  • The other values are 1 or -1 (win, lose).
  • It is a skew symmetric matrix.
  • It has exactly (n-1)/2 wins and losses in every row and column.

Here is another more complex example:

  0 1 2 3 4
0 - L W W L
1 W - W L L
2 L L - W W
3 L W L - W
4 W W L L -

Or phrased another way:

0 beats 2 and 3.
1 beats 0 and 2.
2 beats 3 and 4.
3 beats 1 and 4.
4 beats 0 and 1.

In this example it may be possible to relabel the items to give the same logic as in the previous game. I doubt that holds in general though.

like image 163
Mark Byers Avatar answered Oct 15 '22 08:10

Mark Byers