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)

Till 2020-09-03 15:12

Guys, you are worrying me...
Shouldn't the permutation (0 2) lead to the rules
[CODE]
2 -> 0
1 -> 1
0 -> 2
[/CODE]instead of
[CODE]
2 -> 1
1 -> 0
0 -> 2
[/CODE]??

Dieter 2020-09-03 15:34

[QUOTE=Till;555885]Guys, you are worrying me...
Shouldn't the permutation (0 2) lead to the rules
[CODE]
2 -> 0
1 -> 1
0 -> 2
[/CODE]instead of
[CODE]
2 -> 1
1 -> 0
0 -> 2
[/CODE]??[/QUOTE]
2 becomes 0 and 2 becomes 0.
Einfach nur die zweien und die Nullen austauschen!

Dieter 2020-09-03 15:38

[QUOTE=Dieter;555888]2 becomes 0 and 2 becomes 0.
Einfach nur die zweien und die Nullen austauschen![/QUOTE]

I wanted to say:
2 becomes 0 and 0 becomes 2, of course!

Till 2020-09-03 15:41

[QUOTE=Dieter;555890]I wanted to say:
2 becomes 0 and 0 becomes 2, of course![/QUOTE]


I see... Compare that to [url]http://www.research.ibm.com/haifa/ponderthis/challenges/September2020.html[/url]


Just wondering how long it takes...

Dieter 2020-09-05 20:48

Has anyone found an RPS(11) game with more than 55 automorphisms?

SmartMersenne 2020-09-06 21:03

[QUOTE=Dieter;556171]Has anyone found an RPS(11) game with more than 55 automorphisms?[/QUOTE]

Did you find one with 55? I think the question required at least 50.

Dieter 2020-09-07 01:23

[QUOTE=SmartMersenne;556274]Did you find one with 55? I think the question required at least 50.[/QUOTE]

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 2020-09-07 05:43

[QUOTE=SmartMersenne;556274]Did you find one with 55? I think the question required at least 50.[/QUOTE]

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.

SmartMersenne 2020-09-07 13:19

[QUOTE=Dieter;556305]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.[/QUOTE]

This is not pure luck. After some point it is a skill, and you have proven yourself to have that problem-solving skill.

Walter 2020-09-10 12:38

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?

SmartMersenne 2020-09-11 10:10

[QUOTE=Walter;556630]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?[/QUOTE]

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.


All times are UTC. The time now is 18:15.

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