24 Oct
2018
24 Oct
'18
9:03 p.m.
At http://mathsci.wikia.com/wiki/The_Haruhi_Problem, we have an intriguing situation. The problem is, what is the shortest string that contains every permutation on N letters as a substring. The problem has been around for a while, but somebody posted it on Wikia, a wiki dedicated to fans of various TV programs, mostly anime. Then an anonymous commenter posted a proof of a lower-bound that had been conjectured earlier, that the shortest string must have length at least n! + (n-1)! + (n-2)! + n - 3, for n > 2. The style is a little bit amateurish but the proof seems correct. Robin Houston, a mathematician who has worked on the problem, has vetted it. Nobody knows who the prover is.