mersenneforum.org September 2020
 Register FAQ Search Today's Posts Mark Forums Read

2020-10-12, 03:06   #34
0scar

Jan 2020

31 Posts

Quote:
 Originally Posted by uau 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.
I followed uau's suggestion.

Given a RPS(n) game, we can always extend it to a RPS(n+2) game:
aaavw
aaavw
aaa10
ww001
vv100

where A is the adjacency matrix of the RPS(n) game, V is a column vector of even length n-1 with (n-1)/2 zeros and (n-1)/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 q-1 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.
for the first two blocks, any of the 21 possible automorphisms;
for last block, the 3 automorphisms which keep last element unchanged.

Last fiddled with by 0scar on 2020-10-12 at 03:40

 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 11:15.

Fri May 7 11:15:54 UTC 2021 up 29 days, 5:56, 0 users, load averages: 2.98, 2.86, 2.96