## 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:**
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)