November 2018 - Solution

<< October

November 2018 Challenge


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.