Ponder This Challenge - January 2013 - 13 permutation on 18 letters

Ponder This Challenge:

The following six permutations of the letters EISH

    EISH
    HESI
    IEHS
    HISE
    SEHI
    SIHE

satisfy that for every three letters, and every order, there exists a permutation in which these three letters appear in this order. For example, SHE appears in the last line and HIS appears in the fourth line.

Find 13 permutations of the letters ABCEFHIJLMNPQTVXYZ which satisfy the same condition: for every three letters and every one of their six possible orders, there exists at least one permutation in which the letters appear in this order.

A bonus question: What is special about this set of letters?

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

Solution

• Click here to view the solution

  Many of you used various kind of searches, like genetic algorithms.

  Liubing Yu solved it using a clever combination of our example of six permutations covering four elements and a similar solution with five elements and seven permutations to get a solution for 4*5=20 letters with 6+7=13 permutations (we added xy to make the alphabet 20 letters long):

   ABCEF   MLJIH   VTQPN  XYZxy
   XYZxy    FECBA  VTQPN  HIJLM
   HIJLM    FECBA   yxZYX   NPQTV
   XYZxy    MLJIH    VTQPN  ABCEF
   NPQTV  FECBA   yxZYX   HIJLM
   NPQTV  MLJIH     yxZYX   ABCEF

  AHNX    YPIB   ZQJC   xTLE   FMVy
  FMVy    XNHA  ZQJC   YPIB   ELTx
  BIPY     XNHA  yVMF   xTLE  CJQZ
  ELTx     yVMF  YPIB    ZQJC  AHNX
  CJQZ    XNHA   yVMF  xTLE   BIPY
  CJQZ    YPIB    yVMF  xTLE   AHNX
  ELTx     XNHA   ZQJC  YPIB   FMVy

  Mark Mammel used simulated annealing to get a solution with only 11 permutations:

  TLCMBYXZJHFAVIEQNP
  JVFMBNLQYTPIXEZCAH
  ICYBMPLNQZHAVFJEXT
  ZYILPENXFVJAHQCBMT
  AFVHJEXPLIYZTMBCNQ
  AJCNZBITQELPXMYHFV
  QXLMNEITBVJHAFCZYP
  HVATQBZNYMCIXLPEJF
  XQPBYCTENFHAJVIMZL
  HFNZPTCMEYQBLXIJVA
  EMCTPQZIJVFAHXNYLB

  Here's the answer to the bonus question: The lengths of all the 18 letters, in Morse code, are powers of 2. The example was a hint: EISH are all dots in Morse code (E=. I=.. S=... and H=....).

Solvers

• *Mark Mammel (01/02/2013 05:22 PM EDT)
• Deane Stewart (01/02/2013 07:01 PM EDT)
• *Tobias Philipp (01/03/2013 04:21 PM EDT)
• Donald Dodson (01/03/2013 07:28 PM EDT)
• Markus von Rimscha (01/03/2013 07:50 PM EDT)
• Jason Lee, Brandon Leonhardt & Jacob Woolcutt (01/03/2013 11:53 PM EDT)
• * (01/04/2013 09:15 AM EDT)
• Johannes Waldmann (01/04/2013 09:15 AM EDT)
• Joaquim Neves Carrapa (01/05/2013 09:58 AM EDT)
• Deron Stewart (01/05/2013 06:44 PM EDT)
• Alex Wagner (01/08/2013 02:48 PM EDT)
• Alex Fleischer & (01/09/2013 03:47 AM EDT)
• Philippe Laborie (01/09/2013 03:47 AM EDT)
• Peter Gerritson (01/09/2013 04:40 PM EDT)
• Liubing Yu (01/10/2013 01:15 AM EDT)
• Jamie Jorgensen (01/10/2013 04:55 AM EDT)
• *Martin Husar (01/11/2013 10:00 AM EDT)
• Javier Rodriguez (01/11/2013 01:28 PM EDT)
• Klaus Müller (01/11/2013 01:59 PM EDT)
• Olivier Mercier (01/13/2013 05:16 PM EDT)
• Sebastian Will (01/14/2013 10:28 AM EDT)
• Peter Holdsworth (01/15/2013 12:40 PM EDT)
• Lorenzo Gianferrari Pini (01/15/2013 02:23 PM EDT)
• Todd Will (01/17/2013 12:48 PM EDT)
• Florian Fischer (01/18/2013 06:20 PM EDT)
• Sandeep Navada (01/21/2013 07:22 AM EDT)
• *Christian Pape (01/21/2013 07:35 PM EDT)
• * (01/22/2013 05:17 AM EDT)
• S (01/22/2013 05:17 AM EDT)
• téphane Higueret (01/22/2013 05:17 AM EDT)
• Lewei Weng (01/23/2013 04:54 AM EDT)
• Radu-Alexandru Todor (01/23/2013 05:12 PM EDT)
• Masoud Alipour (01/25/2013 08:39 AM EDT)
• *Nyles Heise (01/25/2013 09:27 AM EDT)
• Øyvind Grotmol (01/26/2013 07:49 AM EDT)
• Kevin Bauer (01/28/2013 02:57 PM EDT)