The Haruhi problem
In: Mathematics
It’s a problem of finding the minimum length required for a so-called superpermutation on a number of symbols.
A permutation is the mathematical term for a rearrangement. E.g. the permutations of abc, as a sequence of letters, are abc, acb, bac, bca, cab, cba. In general for n (different) symbols, there are n! (read as, n factorial, n! = 1 x 2 x … x n) of them.
A superpermutation on n symbols is a string (sequence of symbols) that contains all possible permutations of them. You can check that abcabacba contains all 6 of the permutations earlier. The length of this string (the number of symbols) is 9, and this is known to be the minimum needed to form a superpermutation.
The superpermutation problem then is to determine in general what this minimum length is, and if possible to find these superpermutations. It remains an open problem for 6 symbols and above.
There has been work in finding lower and upper bounds for this minimum length, so while we still don’t know what the exact minimum lengths are, we know that they are in a certain range. And this is where the reference to Haruhi comes in.
The superpermutatation problem, in the context of trying to watch 14 episodes of Haruhi, was posted on 4chan, and someone posted a proof of the current best-known lower bound. It only came into prominence some 7 years later, after which it was verified and written into papers.
Latest Answers