Puzzle
2 minute read

Ponder This Challenge - August 2019 - Three restricted permutations cannot cover

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.

Solution

  • The restrictions A>F, A>G, A>H, B>E, B>G, B>H, C>E, C>F, C>H, D>E, D>F, and D>G leave the four pairs A<E, B<F, C<G, and D<H as possible.
    However, it is easy to show that no two of them can be in the same permutation.
    For example, if A<E, then F<A<E<B yields that B<F cannot hold.
    Therefore, you need at least four permutations to cover all undetermined pairs.

Solvers

  • 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)

Related posts