September 2020
[url]http://www.research.ibm.com/haifa/ponderthis/challenges/September2020.html[/url]

[QUOTE=tgan;555530][URL]http://www.research.ibm.com/haifa/ponderthis/challenges/September2020.html[/URL][/QUOTE]
[QUOTE] the permutation (0 2), which switches 0 and 2 but keeps 1 intact, results in the rules [CODE] 2 > 1 1 > 0 0 > 2 [/CODE][/QUOTE] The challenge description is buggy, or not? 
[QUOTE=Till;555535]The challenge description is buggy, or not?[/QUOTE]
I think so, too. If rps = 0,1,2, then 0 > 1 would mean: rock beats paper. When I was a child, a rock was envelopped by paper... 
I guess its not buggy
description says "which are different ("Paper beats Rock"), so (0 2) is not an automorphism of RPS." which means (0 2) is not automorphism of RPS(3) fyi:I think permutation (012) is automorphism of RPS(3) because if you change 0 to 1, 1 to 2, 2 to 0, it keeps vertices and edges btw, I can't still understand what "a0 b0 c0 d0" means.. what does alphabet at left hand side mean? 
[QUOTE=virgo;555630]I guess its not buggy
description says "which are different ("Paper beats Rock"), so (0 2) is not an automorphism of RPS." which means (0 2) is not automorphism of RPS(3) fyi:I think permutation (012) is automorphism of RPS(3) because if you change 0 to 1, 1 to 2, 2 to 0, it keeps vertices and edges btw, I can't still understand what "a0 b0 c0 d0" means.. what does alphabet at left hand side mean?[/QUOTE] The solution shall be something like 0 > 1,2,3,4 1 > 2,3,4,5 ......... 8 > 0,1,2,3 
[QUOTE=virgo;555630]I guess its not buggy
description says "which are different ("Paper beats Rock"), so (0 2) is not an automorphism of RPS." which means (0 2) is not automorphism of RPS(3) fyi:I think permutation (012) is automorphism of RPS(3) because if you change 0 to 1, 1 to 2, 2 to 0, it keeps vertices and edges btw, I can't still understand what "a0 b0 c0 d0" means.. what does alphabet at left hand side mean?[/QUOTE] The examples are unusual. 0 > 1 1 > 2 2 > 0 with rps would mean „rock beats paper and paper beats scissors and scissors beats rock. 
[QUOTE=virgo;555630]I guess its not buggy
description says "which are different ("Paper beats Rock"), so (0 2) is not an automorphism of RPS." which means (0 2) is not automorphism of RPS(3) fyi:I think permutation (012) is automorphism of RPS(3) because if you change 0 to 1, 1 to 2, 2 to 0, it keeps vertices and edges btw, I can't still understand what "a0 b0 c0 d0" means.. what does alphabet at left hand side mean?[/QUOTE] The example 0 > 1, 3 1 > 2, 4 2 > 0, 3 3 > 1, 4 4 > 0, 2 is consistent, and it has 5 automorphisms, but it isn‘t the usual „RockPaperScissorsLizardSpock" game. The usual game is 0 > 2, 3 1 > 0, 4 2 > 1, 3 3 > 1, 4 4 > 0, 2 (rock beats scissors and lizard and so on. If that‘s wrong, please tell me! 
[QUOTE=Dieter;555636]but it isn‘t the usual „RockPaperScissorsLizardSpock" game.[/QUOTE]
Isn't this just the same issue as with the first example, in that it doesn't seem to match the obvious assignment of numbers to names (rock=0, paper=1, scissors=2)? Both have "0 beats 1" while normally rock does not beat paper. But the structure of the game is the same, and if you swap the labels "0" and "2" then you get the standard rockpaperscissors, and the 5choice version matches what you gave too. 
Formulation is not buggy, is just bad worded: "permutation blah blah is a permutation because blah blah". Of course is a permutation, but it should say "is an automorfism because blah blah"... And so on. The "math" is right.
The puzzle is not very difficult. 
So this is just [url=https://en.wikipedia.org/wiki/Nontransitive_dice]nontransitive dice[/url] in disguise, right?

[QUOTE=retina;555860]So this is just [URL="https://en.wikipedia.org/wiki/Nontransitive_dice"]nontransitive dice[/URL] in disguise, right?[/QUOTE]
Game is the same. Puzzle is different. 
Guys, you are worrying me...
Shouldn't the permutation (0 2) lead to the rules [CODE] 2 > 0 1 > 1 0 > 2 [/CODE]instead of [CODE] 2 > 1 1 > 0 0 > 2 [/CODE]?? 
[QUOTE=Till;555885]Guys, you are worrying me...
Shouldn't the permutation (0 2) lead to the rules [CODE] 2 > 0 1 > 1 0 > 2 [/CODE]instead of [CODE] 2 > 1 1 > 0 0 > 2 [/CODE]??[/QUOTE] 2 becomes 0 and 2 becomes 0. Einfach nur die zweien und die Nullen austauschen! 
[QUOTE=Dieter;555888]2 becomes 0 and 2 becomes 0.
Einfach nur die zweien und die Nullen austauschen![/QUOTE] I wanted to say: 2 becomes 0 and 0 becomes 2, of course! 
[QUOTE=Dieter;555890]I wanted to say:
2 becomes 0 and 0 becomes 2, of course![/QUOTE] I see... Compare that to [url]http://www.research.ibm.com/haifa/ponderthis/challenges/September2020.html[/url] Just wondering how long it takes... 
Has anyone found an RPS(11) game with more than 55 automorphisms?

[QUOTE=Dieter;556171]Has anyone found an RPS(11) game with more than 55 automorphisms?[/QUOTE]
Did you find one with 55? I think the question required at least 50. 
[QUOTE=SmartMersenne;556274]Did you find one with 55? I think the question required at least 50.[/QUOTE]
There are many games with 5 or 11 and some with 9. I have found three games with 55. Seems again to be the search for the needle ... 
[QUOTE=SmartMersenne;556274]Did you find one with 55? I think the question required at least 50.[/QUOTE]
Needle in a haystack, computing times: When I fix a0,...e0,a1,...,e1,a2,...,e2, the code is able to make an exhaustive search of a3,...,e10. Usually it finds 40000...50000 valid games, needing 7 hours (one thread). The time is needed for checking the 11! permutations of the games. One of these a0,...e0,a1,...,e1,a2,...,e2combinations, chosen at random, yielded three games with 55 automorphisms. Pure luck! I have tested some of the permutations with pencil and paper, and they were correct. So I hope that the code works correctly. 
[QUOTE=Dieter;556305]Needle in a haystack, computing times:
When I fix a0,...e0,a1,...,e1,a2,...,e2, the code is able to make an exhaustive search of a3,...,e10. Usually it finds 40000...50000 valid games, needing 7 hours (one thread). The time is needed for checking the 11! permutations of the games. One of these a0,...e0,a1,...,e1,a2,...,e2combinations, chosen at random, yielded three games with 55 automorphisms. Pure luck! I have tested some of the permutations with pencil and paper, and they were correct. So I hope that the code works correctly.[/QUOTE] This is not pure luck. After some point it is a skill, and you have proven yourself to have that problemsolving skill. 
I have some solutions, but it felt way too easy, so I am pretty sure I am missing something and would like to check my understanding of the problem:
First of all, for the RPS(5) game, is the "permutation" that changes none of the labels also counted as an automorphism or not? I only found 4 permutations that change at least one of the labels for the given example. I am also confused by how the permutations are defined and what permutations are actually allowed in this case. Let's assume I have a permutation that relabels the numbers as follows: 0 to 1 1 to 2 2 to 0 3 to 4 4 to 3 I can't define this permutation in a single list. If we draw this in a graph, we get a disconnected graph with two cycles. Are we limited to permutations that result in a single cycle? 
[QUOTE=Walter;556630]I have some solutions, but it felt way too easy, so I am pretty sure I am missing something and would like to check my understanding of the problem:
First of all, for the RPS(5) game, is the "permutation" that changes none of the labels also counted as an automorphism or not? I only found 4 permutations that change at least one of the labels for the given example. I am also confused by how the permutations are defined and what permutations are actually allowed in this case. Let's assume I have a permutation that relabels the numbers as follows: 0 to 1 1 to 2 2 to 0 3 to 4 4 to 3 I can't define this permutation in a single list. If we draw this in a graph, we get a disconnected graph with two cycles. Are we limited to permutations that result in a single cycle?[/QUOTE] 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. You just have to be careful in applying this permutation to the game: do not apply one by one otherwise you will mess things up. It has to be applied all at once. Let's apply your mapping to the game given in the problem: 0 > 1, 3 1 > 2, 4 2 > 0, 3 3 > 1, 4 4 > 0, 2 Here is the result: 1 > 2, 4 2 > 0, 3 0 > 1, 4 4 > 2, 3 3 > 1, 0 when sorted by the left hand side this yields the game in canonical form: 0 > 1, 4 1 > 2, 4 2 > 0, 3 3 > 1, 0 4 > 2, 3 I hope that it is clear now. 
[QUOTE=SmartMersenne;556715]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. [/QUOTE] I didn't know the chosen "cycle notation" too, I always used the "oneline notation" described by SmartMersenne. Wikipedia has an useful paragraph about them ([url]https://en.wikipedia.org/wiki/Permutation#Notations[/url]). 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) 
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. 
[QUOTE=SmartMersenne;557732]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.[/QUOTE] You are correct for us it is a hobby and for him it is work so........ 
[QUOTE=tgan;557862]You are correct for us it is a hobby and for him it is work so........[/QUOTE]
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. 
I assume IBM doesn't give enough badget to this activity. They don't see any revenue from it.....

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). 
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. 
[QUOTE=0scar;559031]As a lucky guess, I searched for RPS(n) games which admit at least one ncycle as an automorphism.[/QUOTE]
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 nonuniform 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 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. 
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? 
[QUOTE=0scar;559127]Some idea about how to build a RPS(17) with more than 17 automorphisms?[/QUOTE]
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. 
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. 
[QUOTE=uau;559281]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.[/QUOTE]
I followed uau's suggestion. Given a RPS(n) game, we can always extend it to a RPS(n+2) game: [FONT="Courier New"]aaavw aaavw aaa10 ww001 vv100[/FONT] where A is the adjacency matrix of the RPS(n) game, V is a column vector of even length n1 with (n1)/2 zeros and (n1)/2 ones, W is the negation of V. The "cartesian product" block construction provides a RPS(15) game which embeds five independent RPS(3) games. I chose V so that the elements of four RPS(3) games still win/lose together against everything else, obtaining a RPS(17) game with 81 automorphisms: 0 1 0 1 1 1 1 1 1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 1 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 1 0 0 This approach can be easily generalized: given a prime p, choose the largest odd composite n=3*q not exceeding p; build a RPS(n) with q independent RPS(3) blocks; extend it once or twice, so that the elements of the first q1 RPS(3) blocks can still be shifted independently. Asymptotically, the number of automorphisms grows from O(p^2) to O(3^(p/3)). As an example, for p=23 we get 23*11 = 253 and 3^6 = 729 respectively. A more refined solution has 1323 automorphisms: 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 Here the starting RPS(21) game embeds three independent RPS(7) games. The extended RPS(23) game admits: for the first two blocks, any of the 21 possible automorphisms; for last block, the 3 automorphisms which keep last element unchanged. 
All times are UTC. The time now is 20:00. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2022, Jelsoft Enterprises Ltd.