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

 2020-09-03, 15:12 #12 Till     "Tilman Neumann" Jan 2016 Germany 13×37 Posts Guys, you are worrying me... Shouldn't the permutation (0 2) lead to the rules Code: 2 -> 0 1 -> 1 0 -> 2 instead of Code: 2 -> 1 1 -> 0 0 -> 2 ??
2020-09-03, 15:34   #13
Dieter

Oct 2017

112 Posts

Quote:
 Originally Posted by Till Guys, you are worrying me... Shouldn't the permutation (0 2) lead to the rules Code: 2 -> 0 1 -> 1 0 -> 2 instead of Code: 2 -> 1 1 -> 0 0 -> 2 ??
2 becomes 0 and 2 becomes 0.
Einfach nur die zweien und die Nullen austauschen!

2020-09-03, 15:38   #14
Dieter

Oct 2017

112 Posts

Quote:
 Originally Posted by Dieter 2 becomes 0 and 2 becomes 0. Einfach nur die zweien und die Nullen austauschen!
I wanted to say:
2 becomes 0 and 0 becomes 2, of course!

2020-09-03, 15:41   #15
Till

"Tilman Neumann"
Jan 2016
Germany

13×37 Posts

Quote:
 Originally Posted by Dieter I wanted to say: 2 becomes 0 and 0 becomes 2, of course!

I see... Compare that to http://www.research.ibm.com/haifa/po...ember2020.html

Just wondering how long it takes...

 2020-09-05, 20:48 #16 Dieter   Oct 2017 112 Posts Has anyone found an RPS(11) game with more than 55 automorphisms?
2020-09-06, 21:03   #17
SmartMersenne

Sep 2017

7·17 Posts

Quote:
 Originally Posted by Dieter Has anyone found an RPS(11) game with more than 55 automorphisms?
Did you find one with 55? I think the question required at least 50.

2020-09-07, 01:23   #18
Dieter

Oct 2017

112 Posts

Quote:
 Originally Posted by SmartMersenne Did you find one with 55? I think the question required at least 50.
There are many games with 5 or 11 and some with 9. I have found three games with 55. Seems again to be the search for the needle ...

2020-09-07, 05:43   #19
Dieter

Oct 2017

12110 Posts

Quote:
 Originally Posted by SmartMersenne Did you find one with 55? I think the question required at least 50.
Needle in a haystack, computing times:

When I fix a0,...e0,a1,...,e1,a2,...,e2, the code is able to make an exhaustive search of a3,...,e10. Usually it finds 40000...50000 valid games, needing 7 hours (one thread). The time is needed for checking the 11! permutations of the games.

One of these a0,...e0,a1,...,e1,a2,...,e2-combinations, chosen at random, yielded three games with 55 automorphisms. Pure luck!

I have tested some of the permutations with pencil and paper, and they were correct. So I hope that the code works correctly.

2020-09-07, 13:19   #20
SmartMersenne

Sep 2017

11910 Posts

Quote:
 Originally Posted by Dieter Needle in a haystack, computing times: When I fix a0,...e0,a1,...,e1,a2,...,e2, the code is able to make an exhaustive search of a3,...,e10. Usually it finds 40000...50000 valid games, needing 7 hours (one thread). The time is needed for checking the 11! permutations of the games. One of these a0,...e0,a1,...,e1,a2,...,e2-combinations, chosen at random, yielded three games with 55 automorphisms. Pure luck! I have tested some of the permutations with pencil and paper, and they were correct. So I hope that the code works correctly.
This is not pure luck. After some point it is a skill, and you have proven yourself to have that problem-solving skill.

 2020-09-10, 12:38 #21 Walter   "Walter S. Gisler" Sep 2020 Switzerland 11 Posts I have some solutions, but it felt way too easy, so I am pretty sure I am missing something and would like to check my understanding of the problem: First of all, for the RPS(5) game, is the "permutation" that changes none of the labels also counted as an automorphism or not? I only found 4 permutations that change at least one of the labels for the given example. I am also confused by how the permutations are defined and what permutations are actually allowed in this case. Let's assume I have a permutation that relabels the numbers as follows: 0 to 1 1 to 2 2 to 0 3 to 4 4 to 3 I can't define this permutation in a single list. If we draw this in a graph, we get a disconnected graph with two cycles. Are we limited to permutations that result in a single cycle?
2020-09-11, 10:10   #22
SmartMersenne

Sep 2017

11101112 Posts

Quote:
 Originally Posted by Walter I have some solutions, but it felt way too easy, so I am pretty sure I am missing something and would like to check my understanding of the problem: First of all, for the RPS(5) game, is the "permutation" that changes none of the labels also counted as an automorphism or not? I only found 4 permutations that change at least one of the labels for the given example. I am also confused by how the permutations are defined and what permutations are actually allowed in this case. Let's assume I have a permutation that relabels the numbers as follows: 0 to 1 1 to 2 2 to 0 3 to 4 4 to 3 I can't define this permutation in a single list. If we draw this in a graph, we get a disconnected graph with two cycles. Are we limited to permutations that result in a single cycle?
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. You just have to be careful in applying this permutation to the game: do not apply one by one otherwise you will mess things up. It has to be applied all at once.

Let's apply your mapping to the game given in the problem:

0 -> 1, 3
1 -> 2, 4
2 -> 0, 3
3 -> 1, 4
4 -> 0, 2

Here is the result:

1 -> 2, 4
2 -> 0, 3
0 -> 1, 4
4 -> 2, 3
3 -> 1, 0

when sorted by the left hand side this yields the game in canonical form:

0 -> 1, 4
1 -> 2, 4
2 -> 0, 3
3 -> 1, 0
4 -> 2, 3

I hope that it is clear now.

 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 16:44.

Mon Dec 6 16:44:46 UTC 2021 up 136 days, 11:13, 0 users, load averages: 1.77, 1.70, 1.77