This month's challenge is based on a question from Michael Brand. (Thanks!)
Given 9 letters A,B,C,...I , there are 9! = 362,880 different ways to sort them.
Imposing some restrictions, like B>C, C>D, and E>G makes the space smaller (30,240 in this case).
Under a restriction, some of the 36 pairs are determined (B>D, in the example above), and some could be valid in both directions (A>G and G>A are both possible).
In this example we can choose two permutations A<D<C<B<F<G<E<H<I and I<H<G<E<F<D<C<B<A) that cover all the possibilities for the undetermined pairs.
Your challenge, this month, is to find restrictions on 9 letters that is feasible (there exists an order consistent with all restrictions) and no three permutations cover all the pairs.
Supply your answer in the format "B>C, C>D, E>G" and explain why it solves the problem.
Update (12/8): Following many clarification requests, here is an equivalent way of asking the same question:
Remember January 2013's challenge? We asked there to find permutations of N=18 letters that cover all possible orders of K=3 letters.
Asking for all possible orders of pairs (K=2) has a trivial solution. For N=9 it is ABCDEFGHI and IHGFEDCBA.
Our challenge this month is to find constraints on the permutations (E>G means that E must appear after G in each permutation) that will force using at least four permutations to solve (i.e. cover all unrestricted pairs) for K=2 and N=9.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the email@example.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to:firstname.lastname@example.org
29/07/2019 @ 12:00 PM EST Solution:
03/09/2019 @ 12:00 PM EST List Updated:
12/08/2019 @ 12:00 PM EST
People who answered correctly:
John Tromp (29/07/2019 11:15 AM IDT) Lorenz Reichel (29/07/2019 02:36 PM IDT) Thomas Huet (29/07/2019 04:48 PM IDT) Louis D & Paul M (30/07/2019 12:31 AM IDT) Jingran Lin (30/07/2019 02:04 AM IDT) Florian Fischer (30/07/2019 02:08 AM IDT) Uoti Urpala (30/07/2019 06:42 AM IDT) Guillaume Escamocher (31/07/2019 06:23 PM IDT) Vladimir Volevich (31/08/2019 07:23 AM IDT) Luke Pebody (02/08/2019 01:02 PM IDT) James Dow Allen (02/08/2019 10:50 PM IDT) Bert Dobbelaere (04/08/2019 07:01 AM IDT) Paul Revenant (04/08/2019 07:26 AM IDT) Jens Leskinen (04/08/2019 04:17 PM IDT) Alper Halbutogullari (04/08/2019 06:22 PM IDT) Andreas Stiller (05/08/2019 05:47 PM IDT) Eden Saig (06/08/2019 02:11 AM IDT) Louis Faucon (07/08/2019 01:33 AM IDT) Keith Kaplan (07/08/2019 04:14 AM IDT) JJ Rabeyrin (07/08/2019 11:37 PM IDT) Daniel Oliveira (08/08/2019 01:00 AM IDT) Daniel Bitin (08/08/2019 01:22 PM IDT) Aaron Zolnai-Lucas (10/08/2019 09:29 PM IDT) Jacoby Jaeger (12/08/2019 02:11 AM IDT)