Ponder This

November 2018 - Solution

<< October November December >>

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.

References:
• Universal cycles for combinatorial structures, Chung et al. 1992
• Universal cycles of k-subsets and k-permutations, Jackson 1993
• Near-universal cycles for subsets exist, Hurlbert et al. 2008