mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)

 0scar 2020-09-12 03:25

[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 "one-line 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 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)

 SmartMersenne 2020-09-24 09:43

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.

 tgan 2020-09-25 17:03

[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

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........

 SmartMersenne 2020-09-25 19:11

[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.

 tgan 2020-09-26 16:37

I assume IBM doesn't give enough badget to this activity. They don't see any revenue from it.....

 0scar 2020-10-06 10:53

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).

 uau 2020-10-06 15:31

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.

 uau 2020-10-06 19:10

[QUOTE=0scar;559031]As a lucky guess, I searched for RPS(n) games which admit at least one n-cycle 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 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.

 0scar 2020-10-07 05:28

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,...,(a-1)*b+k only, by applying an automorphism of RPS(a) to x component.

So AUT(a*b) >= 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?

 uau 2020-10-08 19:45

[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.

 0scar 2020-10-11 10:31

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<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) = p-f(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(y-x) <= m.
The automorphisms include all linear transformations of x and y which don't change the value f(y-x):
multiplying by a q-th root of unity mod p.
We can always choose the constant in p ways, but there are only gcd(q,p-1) distinct q-th roots of unity mod p, so a good choice is to set q as the largest odd factor of p-1.

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 = (p-1)/2; according to Euler's criterion:
f(z) = 1 if z is a non-zero quadratic residue mod p;
f(z) = p-1 if z is a non-residue.

For p = 17 (or any other Fermat prime) we get q = 1, so we can't exceed p automorphisms in this way.

All times are UTC. The time now is 22:39.