About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
November 2018 - 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.