mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)
-   -   September 2020 (https://www.mersenneforum.org/showthread.php?t=25890)

0scar 2020-10-12 03:06

[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 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.
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 05:31.

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