mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2020-09-03, 15:12   #12
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

419 Posts
Default

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
??
Till is offline   Reply With Quote
Old 2020-09-03, 15:34   #13
Dieter
 
Oct 2017

2·72 Posts
Default

Quote:
Originally Posted by Till View Post
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!
Dieter is offline   Reply With Quote
Old 2020-09-03, 15:38   #14
Dieter
 
Oct 2017

6216 Posts
Default

Quote:
Originally Posted by Dieter View Post
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!
Dieter is offline   Reply With Quote
Old 2020-09-03, 15:41   #15
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

419 Posts
Default

Quote:
Originally Posted by Dieter View Post
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...
Till is offline   Reply With Quote
Old 2020-09-05, 20:48   #16
Dieter
 
Oct 2017

2×72 Posts
Default

Has anyone found an RPS(11) game with more than 55 automorphisms?
Dieter is offline   Reply With Quote
Old 2020-09-06, 21:03   #17
SmartMersenne
 
Sep 2017

2×43 Posts
Default

Quote:
Originally Posted by Dieter View Post
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.
SmartMersenne is online now   Reply With Quote
Old 2020-09-07, 01:23   #18
Dieter
 
Oct 2017

2×72 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post
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 ...
Dieter is offline   Reply With Quote
Old 2020-09-07, 05:43   #19
Dieter
 
Oct 2017

9810 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post
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.
Dieter is offline   Reply With Quote
Old 2020-09-07, 13:19   #20
SmartMersenne
 
Sep 2017

10101102 Posts
Default

Quote:
Originally Posted by Dieter View Post
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.
SmartMersenne is online now   Reply With Quote
Old 2020-09-10, 12:38   #21
Walter
 
Sep 2020

1 Posts
Default

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?
Walter is offline   Reply With Quote
Old 2020-09-11, 10:10   #22
SmartMersenne
 
Sep 2017

2·43 Posts
Default

Quote:
Originally Posted by Walter View Post
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.
SmartMersenne is online now   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 07:18.

Wed Dec 2 07:18:27 UTC 2020 up 83 days, 4:29, 1 user, load averages: 1.33, 1.40, 1.46

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.