20200912, 03:25  #23  
Jan 2020
2^{2}×3^{2} Posts 
Quote:
Wikipedia has an useful paragraph about them (https://en.wikipedia.org/wiki/Permutation#Notations). If we want to arrange the numbers from 0 to 6 in descending order, we have: the oneline notation [6,5,4,3,2,1,0], the cycle notation (0,6)(1,5)(2,4)(3), but 1cycles like (3) are often omitted. For all RPS(n) games with n<=5, nontrivial automorphisms have exactly one cycle (more precisely, one ncycle), but this property doesn't hold in general. I guess it isn't spoiling to show the following RPS(7) game, far from being optimal: 0 > 1, 2, 3 1 > 4, 5, 6 2 > 1, 4, 5 3 > 1, 2, 6 4 > 0, 3, 6 5 > 0, 3, 4 6 > 0, 2, 5 It admits two nontrivial automorphisms: [2,4,5,1,3,0,6], or (0,2,5)(1,4,3)(6) [5,3,0,4,1,2,6], or (0,5,2)(1,3,4)(6) 

20200924, 09:43  #24 
Sep 2017
2·59 Posts 
Is it only me or are you also annoyed with less frequent updates and feedback from the new puzzlemaster? I mean the previous guy was also slow but not that much.
Only on two occasions the previous puzzlemaster updated the website once a month but that was due to technical difficulties on the website and he kept the email communication going. This guy doesn't even reply to emails or misses correct answers. I don't think they care as much as we do, and I am starting to question why I care at all. 
20200925, 17:03  #25  
Jul 2015
2^{2}·7 Posts 
Quote:


20200925, 19:11  #26 
Sep 2017
2×59 Posts 
Well, I would have expected more discipline when it is work. Nobody will question me if I don't work on a problem but all eyes are on you if it is your work to maintain the website and communicate with people.

20200926, 16:37  #27 
Jul 2015
34_{8} Posts 
I assume IBM doesn't give enough badget to this activity. They don't see any revenue from it.....

20201006, 10:53  #28 
Jan 2020
2^{2}·3^{2} Posts 
As a lucky guess, I searched for RPS(n) games which admit at least one ncycle as an automorphism.
So they admit at least n automorphisms (by repeatedly applying the cyclic shift). Can we get n*q automorphisms, with q>1? Clearly RPS(n) games can exist only for n odd; let n = 2*m+1. WLOG, I chose weapon labels so that the ncycle (0,1,...,n1) is one automorphism. The first row of the rule table uniquely determines the RPS(n) game: if weapon 0 wins on weapons w_1, ..., w_m, then weapon k wins on weapons (k+w_1)%n, ..., (k+w_m)%n. Moreover, looking at the adjacency matrix A of the game, we have a(k,0) = a(0,nk); so, for 1<=k<=m, weapon 0 must win either on weapon k or on weapon nk. We have m degrees of freedom, and at most 2^m candidate games. Some RPS(n) games with q > 1 (showing only first row of the rule table) n = 7, a = 21, q = 3. 0 > 1, 2, 4. n = 9, a = 81, q = 9. 0 > 1, 3, 4, 7 n = 11, a = 55, q = 5. 0 > 1, 3, 4, 5, 9 n = 13, a = 39, q = 3. 0 > 1, 2, 3, 5, 6, 9. n = 15, a = 1215, q = 81. 0 > 1, 2, 5, 6, 7, 11, 12. n = 19, a = 171, q = 9. 0 > 1, 4, 5, 6, 7, 9, 11, 16, 17. n = 21, a = 45927, q = 2187. 0 > 1, 2, 4, 7, 8, 9, 11, 15, 16, 18. n = 23, a = 253, q = 11; 0 > 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18. So far, no solutions with q>1 built in this way for n = 3,5,17 (the first three Fermat primes). 
20201006, 15:31  #29 
Jan 2017
2^{3}·3·5 Posts 
Although I first solved the bonus problem differently, I think the simplest way to arrive at the solution is similar to what Oscar said  consider graphs where the elements are numbers mod 11 where winning is determined by the difference of the numbers. n and n must have opposite result, so there are only 32 possibilities, or 16 if you take into account the symmetry of reversing every result.
After constructing the answer in this form, I noticed a way to explain why it works and how to generalize it to some other sizes. The winning offsets are the squares: 1, 4, 9, 16=5, 25=3. This actually works for any prime size that is 3 mod 4. For 1 mod 4, 1 is a quadratic residue and "n and n must have opposite result" is not satisfied. By selecting the quadratic residues mod p, you always get p*(p1)/2 automorphisms. One type is the obvious adding a constant to every element, which allows you to move any element to 0. The number of such automorphisms is p. The other type is multiplying every element by a square, which keeps the same element at 0 but permutes others. This keeps the graph valid, since if m is a quadratic residue then n*m is iff n is. The number of such automorphisms is (p1)/2. Together these give p*(p1)/2 automorphisms ((p1)/2 for every choice of which element is at 0). After finding that, doing a web search for quadratic residue graphs found that such graphs have a given name: Paley digraph. 
20201006, 19:10  #30  
Jan 2017
2^{3}×3×5 Posts 
Quote:
If you can map any of the 11 vertices to any other, then the number of automorphisms must be divisible by 11. (Start by mapping vertex 0 to some of the 11 vertices. Since they must be indistinguishable, the number of automorphisms which map 0 there cannot depend on the choice of the vertex. Thus the total number of automorphisms is 11 times the number of automorphisms that keep 0 at 0.) A basic result of group theory says that if the size of a finite group is divisible by a prime p, then there's an element whose generated subgroup has size p. Thus there is an automorphism that returns to identity after 11 iterations. The only permutation on 11 elements that can behave this way is an 11cycle. So you can assume an 11cycle automorphism f exists. Now you can label the nodes by arbitrarily labeling one 0, then 1 is f(0), 2 is f(1) and so on. This labeling necessarily has the property that whether x wins against y is determined by the value of yx. 

20201007, 05:28  #31 
Jan 2020
2^{2}×3^{2} Posts 
A very elegant construction, thanks uau!
Another nice construction works for composite n and solves n=9. Given two games RPS(a) and RPS(b), build a game RPS(a*b). Let z = x*b+y, with 0<=z<a*b, 0<=x<a, 0<=y<b. z1 = x1*b+y1 wins on z2 = x2*b+y2: if y1 wins on y2; or if y1==y2 and x1 wins on x2. The automorphisms of RPS(a*b) include: permutations of all weapons, by applying an automorphism of RPS(b) to y component; permutations of weapons 0*b+k,...,(a1)*b+k only, by applying an automorphism of RPS(a) to x component. So AUT(a*b) >= AUT(b)*AUT(a)^b. Doublechecking known values: n = 9 = 3*3 > (3)*(3)^3 = 81 n = 15 = 3*5 > (5)*(3)^5 = 1215 n = 21 = 3*7 > (21)*(3)^7 = 45927 Two new values n = 25 = 5*5 > (5)*(5)^5 = 15625 n = 27 = 3*9 > (81)*(3)^9 = 1594323 About ncycles, with some patience it can be checked that, if (0,...,a1) and (0,...,b1) are automorphisms of RPS(a) and RPS(b) respectively, then (0,...,a*b1) is an automorphism of RPS(a*b). Some idea about how to build a RPS(17) with more than 17 automorphisms? Last fiddled with by 0scar on 20201007 at 05:32 
20201008, 19:45  #32 
Jan 2017
170_{8} Posts 
I haven't tried to construct a maximal number of automorphisms, but you should be able to get more than 17. Basic proof of concept: embed 3 RPS(3) games in the 17 such that each game wins/loses together against everything else. It shouldn't be too hard to select things to make this a valid RPS(17) game. This'll give you 27 automorphisms, since you can permute each of the 3 games independently.

20201011, 10:31  #33 
Jan 2020
2^{2}·3^{2} Posts 
After a slight modification, uau's "algebric" construction also explains the RPS(13) game with 39 automorphisms (which is optimal, according to the paper referenced within September's solution).
Consider any odd prime p = 2*m+1. Again the weapons are numbers mod p, and x winning on y is determined by the difference z = yx, with p<z<p. Let's choose the function f(z) = z^q mod p, for some odd exponent q: if z = 0 then f(z) = 0; otherwise 0 < f(z) < p and f(z) = pf(z); so z and z give different values and we can use it to define an RPS(p) game. As an example, x wins on y if 1 <= f(yx) <= m. The automorphisms include all linear transformations of x and y which don't change the value f(yx): adding a constant mod p; multiplying by a qth root of unity mod p. We can always choose the constant in p ways, but there are only gcd(q,p1) distinct qth roots of unity mod p, so a good choice is to set q as the largest odd factor of p1. For p = 13, we get q = 3; the cube roots of unity mod 13 are 1,3,9. For p = 4*k+3, we get q = 2*k+1 = (p1)/2; according to Euler's criterion: f(z) = 1 if z is a nonzero quadratic residue mod p; f(z) = p1 if z is a nonresidue. For p = 17 (or any other Fermat prime) we get q = 1, so we can't exceed p automorphisms in this way. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
September 2019  Xyzzy  Puzzles  10  20191008 13:47 
September 2018  Xyzzy  Puzzles  2  20181011 15:31 
September 2017  R. Gerbicz  Puzzles  21  20180317 13:19 
September 2016  Batalov  Puzzles  8  20161004 14:10 
Anyone going to Vienna in September?  fivemack  Factoring  1  20070907 00:29 