mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2019-08-06, 14:49   #12
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

210678 Posts
Default

Please ignore this message. That is me playing stupid without reading all the posts.

Last fiddled with by LaurV on 2019-08-06 at 14:54
LaurV is offline   Reply With Quote
Old 2019-08-06, 16:34   #13
Dieter
 
Oct 2017

8910 Posts
Default

Quote:
Originally Posted by Bolero View Post
ok, so "no three permutations" means "more than three permutations"? (sorry, I'm not a native speaker and the problem is very strangely worded for me)
No. Suppose that we have restrictions which allow 30000 permutations. Then there are 30000*29999*29998/(1*2*3) possibilities to choose three permutations. We want that no three permutations of these cover the pairs- no matter which three permutations we are choosing.
Dieter is offline   Reply With Quote
Old 2019-08-07, 09:48   #14
Bolero
 
Aug 2019
Marseille

48 Posts
Default

Thank you for the explanation, now it is clearer.
Bolero is offline   Reply With Quote
Old 2019-08-15, 01:15   #15
Kebbaj
 
Kebbaj's Avatar
 
"Kebbaj Reda"
May 2018
Casablanca, Morocco

1101112 Posts
Thumbs up Can help someone

I have modeled the question in excel format, so can help someone.


https://drive.google.com/open?id=1xM...zc2nUxiWSt-1Un

Kebbaj is offline   Reply With Quote
Old 2019-09-04, 11:20   #16
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2×13×73 Posts
Default

Am I the only one who is concerned that there is no September challenge as of yet?
a1call is offline   Reply With Quote
Old 2019-09-04, 11:53   #17
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·2,861 Posts
Default

Quote:
Originally Posted by a1call View Post
Am I the only one who is concerned that there is no September challenge as of yet?
I would be more concerned if the previous month's solution was up. Updates to the website have always been sporadic.
henryzz is offline   Reply With Quote
Old 2019-09-04, 18:17   #18
Dieter
 
Oct 2017

89 Posts
Default

Quote:
Originally Posted by a1call View Post
Am I the only one who is concerned that there is no September challenge as of yet?
http://www.research.ibm.com/haifa/po...is/index.shtml


They will update in "early September" - whatever this will say.
Dieter is offline   Reply With Quote
Old 2019-09-08, 13:15   #19
Dieter
 
Oct 2017

10110012 Posts
Default

I have found a solution with brute force, but I cannot explain it. My only explanation is that my code doesn‘t find a covering triple of permutations. Nevertheless I have sent it to the puzzlemaster hoping it‘s not too late...
Dieter is offline   Reply With Quote
Old 2019-09-08, 20:19   #20
Dieter
 
Oct 2017

89 Posts
Default

http://www.research.ibm.com/haifa/po...ugust2019.html
Dieter is offline   Reply With Quote
Old 2019-09-09, 09:40   #21
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

100010001101112 Posts
Default

Quote:
Originally Posted by henryzz View Post
I am struggling to come up with a small example that requires 3 permutations never mind 4 or more (4 may be easier as 2*2=4). Is this puzzle solvable with pen and paper?
Yes, and not so complicate either. But you can't find what you want for a "small" example. There is a reason why they chose 9 symbols. Imagine you have permutations of 3. Your all possible conditions "allowed" conditions (in the initial phase, when you have all permutations) are a<b, a<c, b<a, b<c, c<a, c<b. The permutations are "abc, acb, bac, bca, cab, cba".

They are also 6, but this is just a coincidence because the number of pairs is 2*comb(n,2) (because you have each pair in both directions), and when n=3, we have 2*comb(n,2)=perm(n)=6; if you would have 4, there would be 12 possible pairs, but 24 permutations, for 5 there would be 20 and 120, etc). So you see that as n goes higher, there are "much more" permutations than pairs. Each permutation that you select covers comb(n,2) pairs, and for higher n, it becomes trivial to find permutations with "common" pairs.

Obviously, for n=3, if you take the first and the last permutations, "abc", and "cba", these two cover all the possible pairs. Therefore, let's interdict the last one. To interdict the last one, we will cut from the allowed set the pair "c<b". This automatically interdict the permutations 2, 5, and 6. Therefore, the condition you put is "c>b", and under this condition, your base of allowed pairs becomes "a<b, a<c, b<a, b<c, c<a" and the remaining permutations "abc, bac, bca".

In this case, if you choose first and second permutations, you do not cover c<a, and if you chose second and third, you do not cover a<b. Unfortunately, choosing first and the third covers all pairs, you have a<b, a<c, b<c from the first, and b<a, c<a, and (again) b<c, from the third. But this happens because you do not have enough permutations to chose from.

You can pick another interdiction, instead of c<b, and you will WLOG run in the same situation, and you can't pick _additional_ restrictions, because you do not have enough permutations (every additional restriction will reduce the permutation count below 3, where the problem doesn't make sense anymore).

You have to go with a higher n.

Puzzle: What would be the lowest n that (with convenient restrictions) requires 3 permutations?

As n grows, even if the number of required permutations stays constant or increase linear, or even polynomial, this puzzle becomes easier and easier, in spite of the fact that (or more exactly because) the searching space increases exponential. In fact, this is more like a graph problem, working on the graph of restrictions, you do not really need to make any permutations. I wanted to post this for a long time, but didn't want to spoil it. The numbers of symbols n=9 and permutations=4 is chosen wisely so the puzzle is not too hard, and not too easy.

Last fiddled with by LaurV on 2019-09-09 at 09:48
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
August 2018 Xyzzy Puzzles 5 2018-09-05 02:11
August 2017 Batalov Puzzles 15 2017-09-05 03:47
August 2015 R. Gerbicz Puzzles 7 2015-09-04 13:18
August 2014 Xyzzy Puzzles 2 2014-11-02 19:04
August Progress Wacky NFSNET Discussion 0 2007-08-09 02:32

All times are UTC. The time now is 14:57.

Wed Sep 30 14:57:27 UTC 2020 up 20 days, 12:08, 0 users, load averages: 1.78, 1.73, 1.64

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.