mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2020-09-12, 03:25   #23
0scar
 
Jan 2020

1B16 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post
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

It admits two non-trivial 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)
0scar is offline   Reply With Quote
Old 2020-09-24, 09:43   #24
SmartMersenne
 
Sep 2017

2×43 Posts
Default

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.
SmartMersenne is online now   Reply With Quote
Old 2020-09-25, 17:03   #25
tgan
 
Jul 2015

101102 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post
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........
tgan is online now   Reply With Quote
Old 2020-09-25, 19:11   #26
SmartMersenne
 
Sep 2017

2·43 Posts
Default

Quote:
Originally Posted by tgan View Post
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.
SmartMersenne is online now   Reply With Quote
Old 2020-09-26, 16:37   #27
tgan
 
Jul 2015

1616 Posts
Default

I assume IBM doesn't give enough badget to this activity. They don't see any revenue from it.....
tgan is online now   Reply With Quote
Old 2020-10-06, 10:53   #28
0scar
 
Jan 2020

33 Posts
Default

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).
0scar is offline   Reply With Quote
Old 2020-10-06, 15:31   #29
uau
 
Jan 2017

79 Posts
Default

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 is offline   Reply With Quote
Old 2020-10-06, 19:10   #30
uau
 
Jan 2017

7910 Posts
Default

Quote:
Originally Posted by 0scar View Post
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.
uau is offline   Reply With Quote
Old 2020-10-07, 05:28   #31
0scar
 
Jan 2020

338 Posts
Default

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?

Last fiddled with by 0scar on 2020-10-07 at 05:32
0scar is offline   Reply With Quote
Old 2020-10-08, 19:45   #32
uau
 
Jan 2017

10011112 Posts
Default

Quote:
Originally Posted by 0scar View Post
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.
uau is offline   Reply With Quote
Old 2020-10-11, 10:31   #33
0scar
 
Jan 2020

33 Posts
Default

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):
adding a constant mod p;
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.
0scar is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
September 2019 Xyzzy Puzzles 10 2019-10-08 13:47
September 2018 Xyzzy Puzzles 2 2018-10-11 15:31
September 2017 R. Gerbicz Puzzles 21 2018-03-17 13:19
September 2016 Batalov Puzzles 8 2016-10-04 14:10
Anyone going to Vienna in September? fivemack Factoring 1 2007-09-07 00:29

All times are UTC. The time now is 07:17.

Wed Dec 2 07:17:28 UTC 2020 up 83 days, 4:28, 1 user, load averages: 1.25, 1.41, 1.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.