mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2020-10-12, 03:06   #34
0scar
 
Jan 2020

2·11 Posts
Default

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

Last fiddled with by 0scar on 2020-10-12 at 03:40
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 01:29.

Sat Oct 31 01:29:55 UTC 2020 up 50 days, 22:40, 2 users, load averages: 1.61, 1.73, 1.82

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.