Ponder This Challenge - September 2020 - Generalized Rock Paper Scissors

In a Rock-Paper-Scissors (RPS) game, players can choose one of three "weapons": Rock, Paper, or Scissors. Each weapon defeats exactly one other weapon. By assigning numbers to the weapons, we can describe the game as

(Read "0 -> 1" as "0 beats 1", etc.)

An automorphism of an RPS game is some permutation of the weapon numbers that keeps the rules of the game the same. For example, the permutation (0 1 2) in which 0 is mapped to 1, 1 is mapped to 2 and 2 is mapped to 0 is a permutation, since applying it to the list of rules results in the same list of rules. However, the permutation (0 2), which switches 0 and 2 but keeps 1 intact, results in the rules

which are different ("Paper beats Rock"), so (0 2) is not an automorphism of RPS.

We now consider generalized versions of RPS: an RPS(n) game consists of exactly n weapons, and rules such that every weapon beats exactly (n-1) / 2 of the other weapons such that for every pair of weapons, exactly one weapon beats the other. A famous example is the RPS(5) game "Rock-Paper-Scissors-Lizard-Spock", which maintains the RPS rules but adds the weapons Lizard (beats Paper and Spock, beaten by Rock and Scissors) and Spock (beats Rock and Scissors, beaten by Paper and Lizard). Denoting Lizard by 3 and Spock by 4, this game can be described by the rules

It can be shown that any RPS(5) game has exactly five automorphisms.

Your goal is to find an RPS(9) game with at least 10 automorphisms. Give your solution as a list of the form

where the right-hand side of each row consists of four numbers between 0 and 8.

A bonus '*' for finding an RPS(11) game with at least 50 automorphisms.

Solution

• Click here to view the solution

  An RPS(9) game satisfying the requirements must have exactly 81 automorphisms. Here is one example:

   0 -> 1, 2, 3, 5
   1 -> 3, 4, 7, 8
   2 -> 1, 4, 7, 8
   3 -> 2, 4, 7, 8
   4 -> 0, 5, 6, 7
   5 -> 1, 2, 3, 6
   6 -> 0, 1, 2, 3
   7 -> 0, 5, 6, 8
   8 -> 0, 4, 5, 6
  

  An RPS(11) game satsifying the requirements must have exactly 55 automorphisms. Here is one example:

   0 -> 1, 2, 3, 4, 5
   1 -> 2, 5, 7, 9, 10
   2 -> 3, 4, 8, 9, 10
   3 -> 1, 4, 6, 7, 9
   4 -> 1, 5, 6, 8, 10
   5 -> 2, 3, 6, 7, 8
   6 -> 0, 1, 2, 8, 9
   7 -> 0, 2, 4, 6, 10
   8 -> 0, 1, 3, 7, 10
   9 -> 0, 4, 5, 7, 8
   10 -> 0, 3, 5, 6, 9
  

  The games can be analyzed by hand and using group-theoretic arguments, but the solutions can also be found by going over various RPS games and computing the number of automorphisms. A nice discussion of RPS games and their automorphism groups can be found in "Rock-Paper-Scissors Meets Borromean Rings" by Marc Chamberland and Eugene A. Herman.

Solvers

• Lorenz Reichel (31/8/2020 4:02 PM IDT)
• *Alper Halbutogullari (31/8/2020 5:28 PM IDT)
• Parth Trivedi (31/8/2020 9:29 PM IDT)
• Eitan Levine (31/8/2020 11:15 PM IDT)
• *Bert Dobbelaere (31/8/2020 11:21 PM IDT)
• *Reiner Martin (1/9/2020 12:36 AM IDT)
• *Anders Kaseorg (1/9/2020 2:39 AM IDT)
• *Bertram Felgenhauer (1/9/2020 5:08 AM IDT)
• Sanandan Swaminathan (1/9/2020 6:57 AM IDT)
• Sean Egan (1/9/2020 8:57 AM IDT)
• *Uoti Urpala (1/9/2020 11:25 AM IDT)
• *Guillermo Wildschut (1/9/2020 12:26 PM IDT)
• Victor Chang (1/9/2020 7:10 PM IDT)
• Ayal & Noam Zaks (1/9/2020 10:40 PM IDT)
• Dan Piponi (2/9/2020 6:25 AM IDT)
• Alex Fleischer (2/9/2020 12:54 PM IDT)
• *Florian Fischer (2/9/2020 5:53 PM IDT)
• Almog Yair (3/9/2020 3:04 AM IDT)
• Jacob Burnim (3/9/2020 5:52 AM IDT)
• Dieter Beckerle (3/9/2020 10:56 AM IDT)
• Ben (4/9/2020 2:27 AM IDT)
• *Charles E. Carroll (4/9/2020 5:17 AM IDT)
• *Li Li (4/9/2020 4:39 PM IDT)
• Graham Hemsley (4/9/2020 6:12 PM IDT)
• Siddhartha Srivastava (4/9/2020 8:25 PM IDT)
• *Michael Branicky (5/9/2020 6:05 AM IDT)
• Rif A. Saurous (5/9/2020 8:29 AM IDT)
• *Eden Saig (5/9/2020 2:22 PM IDT)
• *Dieter Beckerle (5/9/2020 3:11 PM IDT)
• Adam Grunwald (6/9/2020 6:37 PM IDT)
• JJ Rabeyrin (6/9/2020 11:41 PM IDT)
• Amos Guler (6/9/2020 11:51 PM IDT)
• Clive Tong (7/9/2020 1:58 PM IDT)
• Klaus Hoffmann (7/9/2020 6:52 PM IDT)
• Michael Liepelt (8/9/2020 11:42 PM IDT)
• *David Smalling (9/9/2020 3:42 AM IDT)
• Fabio Michele Negroni (9/9/2020 7:44 AM IDT)
• Todd Will (10/9/2020 2:41 AM IDT)
• *Tamir Ganor & Shouky Dan (11/9/2020 10:45 AM IDT)
• *Tiffany Harris (12/9/2020 5:40 AM IDT)
• Evert van Dijken (12/9/2020 10:16 AM IDT)
• *Sri Mallikarjun J (12/9/2020 12:31 PM IDT)
• *Daniel Pavlich (12/9/2020 11:18 PM IDT)
• Emmanuel Pilliat (13/9/2020 8:39 PM IDT)
• *David Greer (13/9/2020 9:15 PM IDT)
• Balakrishnan Varadarajan (13/9/2020 11:40 PM IDT)
• *Robbert Rietkerk (14/9/2020 12:09 PM IDT)
• Andy Greig (14/9/2020 3:35 PM IDT)
• *Daniel Chong Jyh Tar (14/9/2020 6:31 PM IDT)
• *Chris Shannon (16/9/2020 7:50 AM IDT)
• *Evert van Dijken (16/9/2020 8:40 PM IDT)
• Friedman, David (16/9/2020 11:24 PM IDT)
• Dan Dima (17/9/2020 12:16 PM IDT)
• *Walter Sebastian Gisler (18/9/2020 9:28 AM IDT)
• *Vladimir Volevich (18/9/2020 5:52 PM IDT)
• *Alexandre Gilotte (20/9/2020 6:50 PM IDT)
• *Harald Bögeholz (20/9/2020 7:06 PM IDT)
• *James Muir (22/9/2020 11:11 PM IDT)
• Marco Bellocchi (23/9/2020 10:09 AM IDT)
• Yasodhar Patnaik (25/9/2020 7:54 PM IDT)
• Daniel Bitin (25/9/2020 10:13 PM IDT)
• *Motty Porat (27/9/2020 1:28 AM IDT)
• *Li Wang (27/9/2020 5:48 PM IDT)
• *Zhou Hangbo (27/9/2020 6:31 PM IDT)
• Nyles Heise (28/9/2020 8:46 AM IDT)
• Yongxing Jim Wang (29/9/2020 8:30 AM IDT)
• *Muralidhar Seshadri (29/9/2020 9:47 AM IDT)
• *Jan Fricke (29/9/2020 12:53 PM IDT)
• *Amir Sarid (29/9/2020 3:50 PM IDT)
• *Keith Schneider (29/9/2020 4:03 PM IDT)
• Karl Mahlburg (30/9/2020 3:43 AM IDT)
• Dipto Thakurta (30/9/2020 8:14 AM IDT)
• *Kang Jin Cho (30/9/2020 7:43 PM IDT)
• *Radu-Alexandru Todor (30/9/2020 11:23 PM IDT)
• Marcel Caria (30/9/2020 11:40 PM IDT)
• *Oscar Volpatti (1/10/2020 8:33 AM IDT)
• Vincent Beaud (1/10/2020 10:24 PM IDT)
• *Hu Shuai (2/10/2020 1:34 PM IDT)
• Jiazhen Tan (3/10/2020 7:52 AM IDT)