Time travel Anime inspires solution to puzzling math problem

Sometimes, the internet is extremely weird and beautiful at the same time — and this is a perfect example.

The problem

Formally, the math problem can be expressed thusly:

“What is the shortest string containing all permutations of a set of n elements?”

In a more “common language”, the problem sounds something like this:

“Say you want to watch a series with n episodes. You want to watch all the episodes in every combination possible. Overlapping is allowed, but the sequence must be continuous. For instance:

for a series with 2 episodes, 1-2-1 is a solution, because it contains both possible combinations (1-2 and 2-1);

for a series with 3 episodes, 1-2-1-3 is NOT a solution, because it does not contain the sequence 1-2-3. The solution is 1-2-3-1-2-1-3-2-1, as it contains all possible sequences (1-2-3, 1-3-2, 2-3-1, 2-1-3, 3-1-2, 3-2-1).

What is the least number of episodes you have to watch?

Anime maths

The problem is surprisingly complex and has remained as a rather obscure mathematical puzzle since 1993, when a demonstration was attempted and subsequently proven incomplete. Recently, Robin Houston, a mathematician and computer scientist, tweeted about finding what seems like a solution to this problem, in the unlikeliest of places: a board on an anime — Haruhi, a 2006 anime based on a series of Japanese light novels.

The reason why Haruhi became linked to this problem is also unusual. The series contains a lot of time travel and is overall very difficult to follow, as the chronology becomes very confusing. To make matters even funkier, when the series went to DVD, the episodes were rearranged, making viewers feel like they were watching a different chronology. Essentially, you can watch episodes in a number of different orders, which has become something of an obsession among fans.

Scientifically, the situation is extremely unusual. The solution seems to work, Houston points out, but mathematicians seem reluctant to address it formally since it’s not presented in a journal. But things get even more interesting.

Houston did a bit of digging and found that the proof was first submitted to 4chan — one of the darker corners of the internet, where threads are only kept for a limited time, though Houston was able to find a permanent mirror. Furthermore, 4chan is entirely anonymous, meaning we don’t know who submitted it, and it’s nigh impossible to verify the author’s identity.

So this anonymous proof posted on 4chan and reposted to an anime board is currently the most elegant solution to the problem. Another mathematician, Jay Pantone, transcribed the proposed solution into a formal layout — and he says it stands up.

Solution

So what is the solution? Well, for Haruhi’s 14 episodes, you’d need to watch at least 93,884,313,611 episodes to be sure you’ve watched all possible combinations. At most, you’d need to watch 93,924,230,411 episodes. Now, mathematicians are working on a more formal version of a formula. The explanation is quite long and difficult to follow, but you can read: