August 2019

[LaurV]

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

[Dieter]

Originally Posted by Bolero

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.

[Bolero]

Thank you for the explanation, now it is clearer.

[Kebbaj]

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


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

[a1call]

Am I the only one who is concerned that there is no September challenge as of yet?

[henryzz]

Originally Posted by a1call

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.

[Dieter]

Originally Posted by a1call

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]

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]

http://www.research.ibm.com/haifa/po...ugust2019.html

[LaurV]

Originally Posted by henryzz

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.