 mersenneforum.org September 2020
 Register FAQ Search Today's Posts Mark Forums Read  2020-09-12, 03:25   #23
0scar

Jan 2020

31 Posts Quote:
 Originally Posted by SmartMersenne Yes, the identity mapping is counted as a permutation. And the mapping can have two disconnected cycles, but I doubt that it would yield a solution. Here is how you should define the mapping: [1,2,0,4,3] where the indices are the original numbers and the entries are the result of the permutation.
I didn't know the chosen "cycle notation" too, I always used the "one-line notation" described by SmartMersenne.
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 one-line notation [6,5,4,3,2,1,0],
the cycle notation (0,6)(1,5)(2,4)(3),
but 1-cycles like (3) are often omitted.

For all RPS(n) games with n<=5, non-trivial automorphisms have exactly one cycle (more precisely, one n-cycle), 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

[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)   2020-09-24, 09:43 #24 SmartMersenne   Sep 2017 6416 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.   2020-09-25, 17:03   #25
tgan

Jul 2015

2610 Posts Quote:
 Originally Posted by SmartMersenne 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.
You are correct for us it is a hobby and for him it is work so........   2020-09-25, 19:11   #26
SmartMersenne

Sep 2017

11001002 Posts Quote:
 Originally Posted by tgan You are correct for us it is a hobby and for him it is work so........
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.   2020-09-26, 16:37 #27 tgan   Jul 2015 2·13 Posts I assume IBM doesn't give enough badget to this activity. They don't see any revenue from it.....   2020-10-06, 10:53 #28 0scar   Jan 2020 31 Posts As a lucky guess, I searched for RPS(n) games which admit at least one n-cycle 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 n-cycle (0,1,...,n-1) 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,n-k); so, for 1<=k<=m, weapon 0 must win either on weapon k or on weapon n-k. 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).   2020-10-06, 15:31 #29 uau   Jan 2017 5A16 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*(p-1)/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 (p-1)/2. Together these give p*(p-1)/2 automorphisms ((p-1)/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.   2020-10-06, 19:10   #30
uau

Jan 2017

2×32×5 Posts Quote:
 Originally Posted by 0scar As a lucky guess, I searched for RPS(n) games which admit at least one n-cycle as an automorphism.
By the way, for the bonus question this follows from a more obviously reasonable assumption: that for any pair of vertices, there exists an automorphism mapping one to the other. Or in other words, that the graph is not non-uniform in such a manner that you could divide it into proper subsets which are distinguishably different from each other and thus cannot be mapped to each other in any automorphism.

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 11-cycle. So you can assume an 11-cycle 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 y-x.   2020-10-07, 05:28 #31 0scar   Jan 2020 378 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= AUT(b)*AUT(a)^b. Double-checking 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 n-cycles, with some patience it can be checked that, if (0,...,a-1) and (0,...,b-1) are automorphisms of RPS(a) and RPS(b) respectively, then (0,...,a*b-1) 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 2020-10-07 at 05:32   2020-10-08, 19:45   #32
uau

Jan 2017

10110102 Posts Quote:
 Originally Posted by 0scar Some idea about how to build a RPS(17) with more than 17 automorphisms?
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.   2020-10-11, 10:31 #33 0scar   Jan 2020 111112 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 = y-x, with -p Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Xyzzy Puzzles 10 2019-10-08 13:47 Xyzzy Puzzles 2 2018-10-11 15:31 R. Gerbicz Puzzles 21 2018-03-17 13:19 Batalov Puzzles 8 2016-10-04 14:10 fivemack Factoring 1 2007-09-07 00:29

All times are UTC. The time now is 03:11.

Sat May 15 03:11:28 UTC 2021 up 36 days, 21:52, 0 users, load averages: 1.77, 2.17, 2.30