Science An anonymous 4chan post could help solve a 25-year-old math mystery with the help of an anime series

[tom_mai78101]

A 4chan poster may have solved part of a very tricky math problem that mathematicians have been working on for at least 25 years. The user was just trying to figure out the most efficient way to watch episodes of a nonlinear anime series, but the result has generated considerable interest from mathematicians around the world who have no way to identify the anonymous user.

Yesterday, Robin Houston, a computer scientist and mathematician tweeted about the bizarre intersection of 4chan and mathematics, inadvertently setting off a wave of public interest in the story. Within hours of his tweet, his phone was vibrating constantly. “It started to go mad,” he says. “My phone started going crazy.”

The 4chan part of this saga began on September 17th, 2011, when a poster posed a question: if you wanted to watch 14 episodes of the anime The Melancholy of Haruhi Suzumiya in every possible order, what’s the shortest string of episodes you’d need to watch?

There are 14 episodes in the first season of Haruhi, a 2006 anime based on a series of Japanese light novels. The episodes, which feature time travel and are otherwise chronologically challenging for the viewer, originally aired in a nonlinear order. When the series went to DVD, the episodes were rearranged, and it’s become something of an obsession for fans to rewatch the series over and over again, going through as many chronologies as possible

An anonymous 4chan post could help solve a 25-year-old math mystery

An anime math problem

www.theverge.com

Math problem is given below:

The Haruhi Problem

What is the smallest string containing all permutations of a set of n elements for n=14?

More formally, "what is the shortest string containing all permutations of a set of n elements?"


The Problem:


You have an n episode tv series.
You want to watch the episodes in every order possible.
What is the least number of episodes that you would have to watch?

• Over lapping is allowed. For example, in the case of n=2, watching episode 1, then 2, then 1 again, would fit the criteria.
• The orders must be continuous. For example, (1,2,1,3) does NOT contain the sequence (1,2,3).

Algorithm and Bounds:

Credit: Anonymous (/sci/)


4 permutations are contained within each n-cycle. So the goal of this algorithm is to systematically generate the sequence, and show that any other method would give a less efficient method. In the long run, I'd like to create some axioms/theorems for the proof, such as more overlap=more efficiency. I think this will call for some modular arithmetic to generalize it for all n but I'm not sure how to do so.

*by follow, I mean use it as a "rule" to tell you the next number in the sequence*

Start with 1 and follow (1 2 3 4) 6 times. We do this by convention. 1,[2,3,4,1,2,3]

Follow (1 4 2 3) 5 times. This group must be chosen, as (23) is in it. 1,2,3,4,1,2,3,[1,4,2,3,1]

Follow (1 2 4 3) 5 times. This is the last group with (3 1) in it. 1,2,3,4,1,2,3,1,4,2,3,1,[2,4,3,1,2]

Since no remaining groups have (1 2) in them, we have to choose one

A): Following (1 4 3 2) 6 times would end the sequence in wrong: 1,2,3,4,1,2,3,1,4,2,3,1,2,4,3,1,2[1,4,3,2,1,4] No group left has (1 4) in it, so this option looses efficiency

B): Following (1 3 2 4) 6 times would end the sequence in wrong: 1,2,3,4,1,2,3,1,4,2,3,1,2,4,3,1,2[1,3,2,4,3,2] No group left has (3 2) in it, so this option looses efficiency

C): Following (1 3 4 2) 6 times works: 1,2,3,4,1,2,3,1,4,2,3,1,2,4,3,1,2[1,3,4,2,1,3]

Follow (1 3 2 4) 5 times. This is the last group with (1 3) in it. 1,2,3,4,1,2,3,1,4,2,3,1,2,4,3,1,2,1,3,4,2,1,3,[2,4,1,3,2] Follow the last group (1 4 3 2) 5 times, to complete the sequence. 1,2,3,4,1,2,3,1,4,2,3,1,2,4,3,1,2,1,3,4,2,1,3,2,4,1,3,2,1,4,3,2,1

The Lower Bound

-Written by Anonymous

I think I have a proof of the lower bound n! + (n-1)! + (n-2)! + n-3 (for n

As in other posts, let n (lowercase) = the number of symbols; there are n! permutations to iterate through.

The obvious lower bound is n! + n-1. We can obtain this as follows:

Let L = the running length of the string N0 = the number of permutations visited X0=L−N0

When you write down the first permutation, X0 is already n-1. For each new permutation you visit, the length of the string must increase by at least 1. So X0 can never decrease. At the end, N0=n!, giving us L

I'll use similar methods to go further, but first I'll need to explain my terminology... Edges:

I'm picturing the ways to get from one permutation to the next as a directed graph where the nodes correspond to permutations and the edges to ways to get from one to the next. A k-edge is an edge in which you move k symbols from the beginning of the permutation to the end; for example,

1234567 -> 4567321

would be a 3-edge. Note that I don't include edges like

12345 -> 34512

in which you pass through through a permutation in the middle (in this case 23451). This example would be considered two edges:

12345 -> 23451 23451 -> 34512

From every node there is exactly one 1-edge, e.g.:

12345 -> 23451

These take you around in a cycle of length n. A 2-edge moves the first two symbols to the end. A priori, it could either reverse or maintain the order of those two symbols:

12345 -> 34521 12345 -> 34512

But the second, as already stated, is not counted as a 2-edge because it is a composition of two 1-edges. So there is exactly one 2-edge from every node. 1-loops:

I call the set of n permutations connected by a cyclic path of 1-edges a 1-loop. There are (n-1)! 1-loops.

The concept of 1-loops is enough to get the next easiest lower bound of n! + (n-1)! + n-2. That's because to pass from one 1-loop to another, it is necessary to take a 2-edge or higher. Let us define:

N1 = the number of 1-cycles completed or that we are currently in X1=L−N1−N2

The definition of N1 is a bit more complicated than we need for this proof, but we'll need it later. You might ask, isn't N1 just one more than the number of completed 1-cycles? No! When we have just completed a 1-cycle, it is equal to the number of completed 1-cycles.

In order to increment N1, we have to take a 2-edge, which increases L by 2 instead of 1. Therefore X1 can never decrease. Since X1 starts out with the value n-2, and we have to complete all (n-1)! 1-loops, we get the lower bound n! + (n-1)! + n-2.

2-loops:

Suppose we enter a 1-loop, iterate through all n nodes (as is done in the greedy palindrome algorithm), and then take a 2-edge out. The edge we exit by is determined by the entry point. The permutation that the 2-edge takes us to is determined by taking the entry point and rotating the first n-1 characters, e.g.:

12345 is taken by n-1 1-edges to 51234 which is taken by a 2-edge to 23415

If we repeat this process, it takes us around in a larger loop passing through n(n-1) permutations. I call this greater loop a 2-loop.

The greedy palindrome algorithm uses ever-larger loops; it connects (n-k+1) k-loops via (k+1)-edges to make (k+1)-loops. But I haven't been able to prove anything about these larger loops yet.

The tricky thing about 2-loops is that which 2-loop you're in depends on the point at which you entered the current 1-loop. Each of the n possible entry points to a 1-loop gives you a different 2-loop, so there are n*(n-2)! 2-loops, which overlap. And now for the proof of the n! + (n-1)! + (n-2)! lower bound...

To review: n = alphabet length L = running string length N0 = number of permutations visited X0=L−N0 N1 = number of 1-cycles completed or that we are currently in X1=L−N1−N2

In order to increase N1, you must jump to a new 1-cycle -- having completed the one you are leaving. That means the next permutation P' in the 1-cycle (following your exit point P) is one you have already visited. Either you have at some point entered the 1-cycle at P', or this is the second or greater time you've visited P. If you have ever entered the 1-cycle at P', leaving at P by a 2-edge will not take you to a new 2-cycle; you will be in the same 2-cycle you were in when you entered at P'.

So these are the available ways to enter a 2-cycle you've never been in before: * take a 3-edge or higher * take a 2-edge but don't increase N1 * take a 2-edge from a permutation P that you were visiting for the second or greater time

In the first two cases, X1 increases by 1 in the step under consideration. In the third case, X1 must have increased by 1 in the previous step. Because of this third case, it is convenient to regard any series of edge traversals that takes you through permutations you've already visited as a single step. Then if we define

N2 = number of 2-cycles visited X2=L−N0−N1−N2

the quantity X2 does not decrease in any step. Since 2-cycles are n(n-1) long, you must visit at least (n-2)! 2-cycles. X2 is initially n-3, giving us the lower bound

L >= n!+(n−1)!+(n−2)!+n−3.