Ponder This Challenge - November 2018 - 10-choose-5 short string

There are 10 possible strings of three different letters from the five-letter "alphabet" ABCDE: ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE and CDE.

The 16-letter string "ABECDEABDECADCBA" contains, as consecutive three-letter sub-strings, an anagram of every one of these 10 strings.

There is a shorter string (13 characters long) that satisfies the same condition.

Your challenge, this month, is to find a string of no more than 270 letters that contains, as consecutive five-letter sub-strings, an anagram of all the possible strings of five different letters from the ten-letter "alphabet" PONDERTHIS.

Solution

• Click here to view the solution

  Hermann Jurksch was the first to find a 260-long solution:

  NTEPHRDSOETNIHOREPDSITROSDNTRIODSPHERNTIPHROSETHPOISEDNHISODTHIROSNTIEDRHSTOIEHSNTDEHISTNRHISDTEHRISTPEDRNIHPSTNDIHPSEONRHSPTOERISPOERIDSPNEHIRPSNOTHDPSNOHETRSDPOENRDTPONEHDPONRTDHPNROIDPNETRODHPIEONDTIPONHTRPOISNDRPIENSODHERNSPTIOEDHTPIEDOPTSREINOHDRIPTENSRDH

  Eden Saig sent us some references.

  This month's challenge is related to the problem of finding universal cycles of k-subsets: strings in which each k-subset of a given alphabet appears only once.
  A series of papers by Chung, Jackson, Hulbert et al. (see below) develops the theory and methods for approximating such strings and constructing them efficiently. Using these methods, we constructed a string containing anagrams for 250 of the 252 possible combinations. The final result was obtained by concatenating the two remaining combinations, taking overlaps into account.

  Li Li proved that 260 is the shortest solution: There are 9 choose 4 = 126 strings of five different letters containing a letter X. Each appearance of X can contribute at most 5 such strings so each letter should appear at least 26 (126/5) times. Therefore the shortest solution is at least 26*10=260 letters.

Solvers

• Andreas Stiller (31/10/18 11:25 PM IDT)
• Bert Dobbelaere (01/11/18 10:46 AM IDT)
• George Lasry (02/11/18 09:35 PM IDT)
• Justin Fletcher (03/11/18 03:01 AM IDT)
• *Hermann Jurksch (03/11/18 09:23 PM IDT)
• Michael J Swart (03/11/18 09:26 PM IDT)
• *Eden Saig (04/11/18 12:03 AM IDT)
• Hugo Pfoertner (04/11/18 06:54 PM IDT)
• Florian Fischer (04/11/18 11:48 PM IDT)
• Daniel Bitin (06/11/18 12:45 AM IDT)
• Kang Jin Cho (07/11/18 07:19 PM IDT)
• *Florian Fischer (09/11/18 10:18 PM IDT)
• David Greer (10/11/18 08:42 PM IDT)
• Alper Halbutogullari (13/11/18 08:38 AM IDT)
• Arthur Vause (14/11/18 11:04 AM IDT)
• Alexander Daryin (15/11/18 11:10 PM IDT)
• Mathias Schenker (16/11/18 03:04 PM IDT)
• Anders Kaseorg (18/11/18 10:21 AM IDT)
• David Stevens (21/11/18 10:25 AM IDT)
• Deron Stewart (21/11/18 09:19 PM IDT)
• Nyles Heise (23/11/18 03:13 AM IDT)
• Jingran Lin (24/11/18 03:47 PM IDT)
• Deane Stewart (24/11/18 07:00 PM IDT)
• Boris Rakús (25/11/18 12:58 PM IDT)
• Dario Serino (26/11/18 11:31 AM IDT)
• Thomas Egense (27/11/18 06:35 PM IDT)
• Andreas Knüpfer (28/11/18 02:52 PM IDT)
• Marcel Caria (29/11/18 03:11 AM IDT)
• *Oscar Volpatti (29/11/18 08:34 PM IDT)
• *Li li (30/11/18 09:23 AM IDT)
• Pål Hermunn Johansen (30/11/18 04:46 PM IDT)
• Oleg Vlasii (30/11/18 07:20 PM IDT)
• Radu-Alexandru Todor (01/12/18 02:20 AM IDT)
• JJ Rabeyrin (02/12/18 03:37 PM IDT)