More rock-paper-scissors mathematical mayhem

This is the sort of thing that can quickly eat up all my time.

Last week, I wrote a little about my initial investigations into rock-paper-scissors extensions. It turned out that people were way ahead of me on devising bigger and bigger versions, but I really wanted to look into the underlying mathematics of how these things work.

I haven't got much further with my investigation, but I did come up with one result that I thought was rather pleasing and elegant.

I mentioned last time that I was interested in figuring out how many games similar to rock-paper-scissors you could find within the structure of a larger game.

Some definitions:

A tournament is "a directed graph (digraph) obtained by assigning a direction for each edge in an undirected complete graph. That is, it is a directed graph in which every pair of vertices is connected by a single directed edge."

In my last post I used the term "fair" to describe a tournament in which every player beats and is beaten by an equal number of opponents.

RPS-n is therefore defined as the fair tournament with n participants. In my last post, I defined RPS-n as being of level L, where L=(n-1)/2. The number L is often more useful than n, as we shall see.

In the section on transitivity at the wikipedia link, a tournament in which every participant is beats at least k opponents is called k-paradoxical (translating the mathematical notation in the wikipedia page, for all ways of choosing k players in the tournament, there exists another player who beats all of them). RPS-n is 1-paradoxical because every player is beaten by at least 1 other player. However, it is possible to see that we can choose two or more players who are not both beaten by another player (for example, if I choose Spock and lizard in RPS-5, then neither rock, paper nor scissors can beat both of them).

The first thing I wanted to do was to see if I could figure out how many distinct Hamiltonian cycles there are in RPS-n. In my last post, I showed that there are exactly 2 such cycles in RPS-5. I think I've counted exactly 17 in RS-7, but that number looks weird (I am intrigued by the idea of creating a musical piece using all 17 cycles, since the diatonic scale has 7 distinct notes in it - if it sounds good, I'll probably make an mp3 of it and post it somewhere). I have not yet managed to find a general answer, however, and am currently out of ideas of how to do so.

What I have achieved so far is to work out how to calculate the number of games equivalent to RPS-3 (that is, to rock-paper-scissors) there are in RPS-n, or more accurately, the fair tournament of level L.

This involves choosing three players from n, and there are ((n-2)(n-1)n)/6 ways of doing that. However, most of those choices will not be valid because they are transitive. To find out how many ways of picking three non-transitive elements from RPS-n there are, we need to go back to the possible choices that can be made, and that means we need to use the level, L, of the game.

Define P(r) as the player that defeats P(r+1), P(r+2), ... , P(r+L) ; where the number in brackets has modulus n (that is, it behaves like a clock with n numbers on the face).

To start with, we can only choose from the first L players to start. This is because the (L+1)th player has to choose from players who can only beat the first L players - that is, they can only produce duplicates of cycles that start on the first L players. We can see this because P(L+1) can beat only up to P(2L+1), but 2L+1 = n so that means that P can only beat P(n) (which is equivalent to P(0) ), who in turn can only beat P(1) up to P(L).

So, we have L options for our start point. We then have L options for our second choice (in the level 2 game (rock-paper-scissors-lizard-Spock), we can choose to start at A or B. If we start at A, then we can choose B or C, and if we start at B then we can choose D or E). However, our options for choosing the third member of the set in order that it be non-transitive, are reduced.

With the definition of P(r) above, we can see that effectively, for each start point we want to choose three positive integers a, b, c (all of which are less than or equal to L) such that a+b+c = 2L+1. Now we can see that if a=1, then b+c=2L meaning b=c=L. In general, it resolves to choosing two items out of L, which is the same as the Lth triangular number.

It is not enough to say that there are L times the Lth triangular number ways of choosing an RPS-3 game from an RPS-n game. Some of the games will be duplicates of one another, and we have to take those away.

For P(1), there are no duplicates. For P(2), the only duplicate is where (a,b,c) = (L,L,1). This is because P(1) is included in the cycle by virtue of the fact that it is one step behind P(2), and since we have already accounted for all the cycles that include P(1) then it must be a duplicate of one of those cycles.

In general, for P(r), then we must discount all (a,b,c) where c is less than r.

For each value of c less than r, the number of duplicates is given by the cth triangular number (we can see this, because the puzzle is similar to the puzzle already solved, but counting backwards around the circle instead of forwards). But we have to add up all the duplicates from all of the different values of r. That means that the total number of duplicates is the sum of all the triangular numbers up to the (r-1)th triangular number (because the maximum value of c is r-1).

The sum of the triangular numbers up to a number n is called the nth tetrahedral number, and has formula (n(n+1)(n+2))/6.

This means that the total number of RPS-3 games to be found in RPS-n is given by L multiplied by the Lth triangular number, and then minus the (L-1)th tetrahedral number. That produces a formula as follows:

(2(L^3)+3(L^2)+L)/6

(2 times L cubed, plus 3 times L squared, plus L, and all divided by 6)

And that concludes the work I have done so far on RPS-n this week!

***

My suspicion is that for the number of distinct RPS games of level K to be found in the RPS tournament of level L (K less than L), then the formula will include the (K+2)th dimension of triangular numbers, where triangular numbers are the 2nd dimension, tetrahedral numbers are the 3rd, the 4th would be the sum of tetrahedral numbers up to n, and so on - however, I am a long way from even attempting a proof of that! For future reference, a formula for the nth k-dimensional triangular number is given on a page from the University of Toronto Mathematics Network - hopefully I can use that to show how it works for RPS-n games.