20190806, 14:49  #12 
Romulan Interpreter
Jun 2011
Thailand
21067_{8} Posts 
Please ignore this message. That is me playing stupid without reading all the posts.
Last fiddled with by LaurV on 20190806 at 14:54 
20190806, 16:34  #13 
Oct 2017
89_{10} Posts 
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.

20190807, 09:48  #14 
Aug 2019
Marseille
4_{8} Posts 
Thank you for the explanation, now it is clearer.

20190815, 01:15  #15 
"Kebbaj Reda"
May 2018
Casablanca, Morocco
110111_{2} Posts 
Can help someone
I have modeled the question in excel format, so can help someone.
https://drive.google.com/open?id=1xM...zc2nUxiWSt1Un 
20190904, 11:20  #16 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2×13×73 Posts 
Am I the only one who is concerned that there is no September challenge as of yet?

20190904, 11:53  #17 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·2,861 Posts 

20190904, 18:17  #18  
Oct 2017
89 Posts 
Quote:
They will update in "early September"  whatever this will say. 

20190908, 13:15  #19 
Oct 2017
1011001_{2} Posts 
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...

20190908, 20:19  #20 
Oct 2017
89 Posts 

20190909, 09:40  #21  
Romulan Interpreter
Jun 2011
Thailand
10001000110111_{2} Posts 
Quote:
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 20190909 at 09:48 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
August 2018  Xyzzy  Puzzles  5  20180905 02:11 
August 2017  Batalov  Puzzles  15  20170905 03:47 
August 2015  R. Gerbicz  Puzzles  7  20150904 13:18 
August 2014  Xyzzy  Puzzles  2  20141102 19:04 
August Progress  Wacky  NFSNET Discussion  0  20070809 02:32 