mersenneforum.org September 2020
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

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

Jan 2020

22×32 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.
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

 Thread Tools

 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 05:18.

Thu May 26 05:18:43 UTC 2022 up 42 days, 3:20, 0 users, load averages: 0.80, 0.91, 1.05

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔