August 2019

[Xyzzy]

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

[Kebbaj]

Hello everybody.

Understanding the question is always the first difficulty of challange.
B> C Restriction.
Are we talking about variable or alphabetic chain to sort?

[LaurV]

That kind of means "ordered pair", or "totally ordered set", i.e. all the permutations in which B is after C are not accepted. Or viceversa, WLOG. You can read the operator as "after" or "before", or "ascents" or "descents", "B is after (or before) C", etc, or even completely eliminate the operator. I learned (most of) my (related) math without it, and only occasionally seen it in combinatorics or so, I mean you can just write "ABCD" instead of "A<B<C<D", and it is still clear in the context of total ordered sets. The dilemma (my dilemma) of "after" versus "before" comes from the fact that many authors use one or the other, with the meaning defined locally in their own texts. I had two professors in the uni and one of them used to write "A<B<C" and the other "A>B>C" for the same thing, the ordered triplet (A, B, C), or ABC, which was an eternal resource of fun and confusion. If you think deeper, both notations make sense, haha...

[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?

[a1call]

I read this puzzle again everyday and everyday I understand the challenge a bit more than the day before.
At the current rate I should completely understand it in a couple of months, Max.

[Kebbaj]

Originally Posted by a1call

I read this puzzle again everyday and everyday I understand the challenge a bit more than the day before.
At the current rate I should completely understand it in a couple of months, Max.

In two months you will understand Rachid.
I'm joking Rachid.
I do not understand too !!
We're getting old.

[Dieter]

Originally Posted by Kebbaj

In two months you will understand Rachid.
I'm joking Rachid.
I do not understand too !!
We're getting old.

Sometimes it‘s helpful to hear the same in other words:
There are 9! possibilities to write abcdefghi ... ihgfedcba. We can interprete the first permutation as a<b<c...<i. Here is c<g and in the last permutation is g<c.
Counting only the permutations fulfilling B>C, C>D, and E>G (b has to be right of c and so on) we have only 30,240 permutations.
There are 36 pairs ab ac ... ai bc bd...bi...hi. In our exemple we have given relations between b,c and c,d and b,d and e,g. The other 32 relations aren‘t fixed, f.e. a<b and a>b is possible.
The permutations A<D<C<B<F<G<E<H<I and I<H<G<E<F<D<C<B<A are two of the 30240 permutations fulfilling the fixed conditions. Furthermore they contain („cover“) all 2*32 undefined relations, f.e. a<b (the first) and a>b (the second).
We have to search for conditions (restrictions) for which it isn‘t possible to find three permutations covering the fixed and the undetermined pairs. They have to be free of contradictions (feasible). This sentence has been additioned (the challenge has been changed at least one time). I suppose that someone has sent a<b and b<c and c<a to the puzzlemaster.

[Kebbaj]

Originally Posted by Dieter

Sometimes it‘s helpful to hear the same in other words:
There are 9! possibilities to write abcdefghi ... ihgfedcba. We can interprete the first permutation as a<b<c...<i. Here is c<g and in the last permutation is g<c.
Counting only the permutations fulfilling B>C, C>D, and E>G (b has to be right of c and so on) we have only 30,240 permutations.
There are 36 pairs ab ac ... ai bc bd...bi...hi. In our exemple we have given relations between b,c and c,d and b,d and e,g. The other 32 relations aren‘t fixed, f.e. a<b and a>b is possible.
The permutations A<D<C<B<F<G<E<H<I and I<H<G<E<F<D<C<B<A are two of the 30240 permutations fulfilling the fixed conditions. Furthermore they contain („cover“) all 2*32 undefined relations, f.e. a<b (the first) and a>b (the second).
We have to search for conditions (restrictions) for which it isn‘t possible to find three permutations covering the fixed and the undetermined pairs. They have to be free of contradictions (feasible). This sentence has been additioned (the challenge has been changed at least one time). I suppose that someone has sent a<b and b<c and c<a to the puzzlemaster.

Your explanations are very clear.

Thank you dieter,

"The weight carried by a group is a feather".

[Bolero]

I still quite don't get it as from what I understand it shouldn't be an easy problem. Maybe I'm missing something here as I can't see why the simple solution to enforce a specific permutation shouldn't work here. For example

the restrictions A<B, B<C, C<D, D<E, E<F, F<G, G<H, H<I are fulfilled by just one permutation A<B<C<D<E<F<G<H<I

[Dieter]

Originally Posted by Bolero

I still quite don't get it as from what I understand it shouldn't be an easy problem. Maybe I'm missing something here as I can't see why the simple solution to enforce a specific permutation shouldn't work here. For example

the restrictions A<B, B<C, C<D, D<E, E<F, F<G, G<H, H<I are fulfilled by just one permutation A<B<C<D<E<F<G<H<I

... and so it's no solution, because we are searching for restrictions for which the pairs can NOT be covered by one or two or three permutations.

[Bolero]

Originally Posted by Dieter

... and so it's no solution, because we are searching for restrictions for which the pairs can NOT be covered by one or two or three permutations.

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)