August 2019 - Challenge
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 ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
29/07/2019 @ 12:00 PM EST
Solution:
03/09/2019 @ 12:00 PM EST
List Updated:
04/09/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)
Robert Lang (12/08/2019 04:55 PM IDT)
Motty Porat (12/08/2019 11:39 PM IDT)
Chuck Carroll (13/08/2019 02:39 PM IDT)
Arash Yazdani (13/08/2019 10:04 PM IDT)
Todd Will (15/08/2019 11:55 PM IDT)
David Friedman (18/08/2019 04:51 AM IDT)
Kang Jin Cho (20/08/2019 11:24 AM IDT)
Daniel Chong Jyh Tar (26/08/2019 07:45 AM IDT)
David Greer (27/08/2019 12:58 AM IDT)
Daniel Blazewicz (28/08/2019 09:38 AM IDT)
Oscar Volpatti (31/08/2019 04:16 PM IDT)
Vincent Beaud (31-08/2019 11:41 PM IDT)
Radu-Alexandru Todor (01/09/2019 12:24 PM IDT)
Doug Miller (01/09/2019 06:14 AM IDT)
Li Li (01/09/2019 04:38 AM IDT)