Mystery Math Whiz and Novelist Advance Permutation Problem (quantamagazine.org)

A new proof from the Australian science fiction writer Greg Egan and a 2011 proof anonymously posted online are now being hailed as significant advances on a puzzle mathematicians have been studying for at least 25 years. Erica Klarreich, writing for Quanta Magazine: On September 16, 2011, an anime fan posted a math question to the online bulletin board 4chan about the cult classic television series The Melancholy of Haruhi Suzumiya . Season one of the show, which involves time travel, had originally aired in nonchronological order, and a re-broadcast and a DVD version had each further rearranged the episodes. Fans were arguing online about the best order to watch the episodes, and the 4chan poster wondered: If viewers wanted to see the series in every possible order, what is the shortest list of episodes they'd have to watch? In less than an hour, an anonymous person offered an answer -- not a complete solution, but a lower bound on the number of episodes required. The argument, which covered series with any number of episodes, showed that for the 14-episode first season of Haruhi, viewers would have to watch at least 93,884,313,611 episodes to see all possible orderings. "Please look over [the proof] for any loopholes I might have missed," the anonymous poster wrote.

The proof slipped under the radar of the mathematics community for seven years -- apparently only one professional mathematician spotted it at the time, and he didn't check it carefully. But in a plot twist last month, the Australian science fiction novelist Greg Egan proved a new upper bound on the number of episodes required. Egan's discovery renewed interest in the problem and drew attention to the lower bound posted anonymously in 2011. Both proofs are now being hailed as significant advances on a puzzle mathematicians have been studying for at least 25 years. Mathematicians quickly verified Egan's upper bound, which, like the lower bound, applies to series of any length. Then Robin Houston, a mathematician at the data visualization firm Kiln, and Jay Pantone of Marquette University in Milwaukee independently verified the work of the anonymous 4chan poster. Now, Houston and Pantone, joined by Vince Vatter of the University of Florida in Gainesville, have written up the formal argument. In their paper, they list the first author as "Anonymous 4chan Poster."

Comments

Explanation

[Mikkeles]

Would someone please explain why it wouldn't just be 14! for all permutations?

Re:Explanation

[Anonymous Coward]

By concatenating the series, additional ones are created, so it's less than 14!. E.g. first watching 1..14, then 1..12,14,13 (the last two switched), you would actually also see 2..14,1, and 3..14,1,2 and 4..15,1..3. So it's definitely less than 14! due to new combinations being creating when concatenating the single series.

Re:Explanation

[john83]

Imagine there are 3 episodes. Possible orders are 123, 132, 213, 231, 312, 321. As you say, 3! = 6 orders. But if I watch the episodes 1231321312 I've covered all six in an overlapping way. Is this the shortest way? I don't know. I'd probably check it exhaustively. That'll work up to some fairly short length where the number of combinations get crazy.

Re:Explanation

[cascadingstylesheet]

Would someone please explain why it wouldn't just be 14! for all permutations?

14! is the total number of permutations. Each permutation contains 14 episodes. So, you would have to watch at least 14 * 14! episodes to watch every permutation. But in actuality, you'd probably have to watch far fewer episodes.

If there were just 3 episodes, you could watch five episodes and you'd capture three of the permutations:

i.e. 1 2 3 1 2

contains the permutations 1, 2, 3 and 2, 3, 1 and 3, 1, 2.

Thanks. Good math problem, but a terrible metaphor.

The experience of watching 1,2,3,1,2 would not be at all the same as watching 1,2,3 ; 2,3,1 ; and 3,1,2

Re:Explanation

[Anonymous Coward]

You already fail at n=2: just watch 1,2,1.

Re:Explanation

[famebait]

The experience of watching 1,2,3,1,2 would not be at all the same as watching 1,2,3 ; 2,3,1 ; and 3,1,2

Ah, but can you prove it?

Re:Explanation

[sfcat]

Imagine there are 3 episodes. Possible orders are 123, 132, 213, 231, 312, 321. As you say, 3! = 6 orders. But if I watch the episodes 1231321312 I've covered all six in an overlapping way.

If memory serves (it's been 30 years) these are called tuples, and can be handy as hell. I had a friend who forgot her answering machines login, took me 5-10 minutes to break into it (3 digits).

They are called permutations and the shortened sequence is a superpermutation. The superpermutations are constructed via an asymmetric version of the Traveling Salesman Problem. Basically the tails of some permutation can do double duty by serving also as the head of the next permutation. Tuples are simply typed lists of data e.g. a database row. A fixed size list of integers is a tuple but so is 121 which isn't a permutation.

Re:Explanation

[randm.ca]

Excellent explanation. To answer the question you only sort of asked, it's not the shortest way. No matter which of the 6 possible orders you start with, the best you can get is a list 9 elements long. Optimal would be 8 elements (the initial 3 you decide to start with, then 1 more from each of the other 5) but no matter which order you start with it wants to repeat that initial order on the 3rd addition.

For example 123 should be followed by 231 resulting in 1231. Follow that with 312 for 12312. Next should be 123, but you started with that, so next-best-thing would be 213 for 1231213. Then 132 followed by 321 to get 123121321, one of the 9 element solutions.

Re:Explanation

[lgw]

There's a related idea in math: De Bruijn sequences. Like many basic ideas in math, they show up in surprising places. De Bruijn sequences are more strict than the problem statement in TFA, as they're cyclic and have no duplicates, but it's very close to the same problem.

I'd think finding the length of a De Bruijn sequence for an alphabet of 14 and a substring length of 14 would be a quick way to set an upper bound very close to the minimal sequence.

Re:Explanation

[Paradise Pete]

I wish I had mod points so that everyone would get the concept clearly.

I don't think that mod points are quite as powerful as you imagine.

4 chan is turing complete

[goombah99]

It can do anything But no one can prove if a conversation will end. The halting condition is Hitler.

Re:N!

[famebait]

Isn't this just N!?

That would have to be N! * N (permutations * episodes in each).
But no.

Am I misunderstanding what they are computing?

Yes.

Given a series of length n = 3, if you watch this sequence:
    1, 2, 3, 1, 2
you have also watched all the following complete sequences:
    1, 2, 3
    2, 3, 1
    3, 1, 2
while having only watched 5 episodes, not 9.

Re:!14 is smaller than 93,884,313,611

[axlash]

It's not 14! you want to compare the lower bound with, it's 14! * 14.

Re:!14 is smaller than 93,884,313,611

[spiny]

14! is the number of PERMUTATIONS, so you would watch ALL 14 episones in 87178291200 different orders.

Re:De Bruijn sequence

[Dahan]

Sorta related, but not the same. De Bruijn sequences contain all possible strings of length n using an alphabet of size k, whereas this is about the shortest string that contains all possible permutations of the string 123...n

E.g., if n = 2 and the alphabet contains "1" and "2" (k = 2), a De Bruijn sequence would be 1122, which contains 11, 12, 22, and 21 (it wraps around. 11221 if you want to make it explicit.).

But for this problem, if n = 2, the shortest sequence is 121, which contains 12 and 21. It doesn't need to contain 11 or 22, because those aren't permutations of 12.

Re: !14 is smaller than 93,884,313,611

[wonkey_monkey]

Or, altenatively, you're an idiot.

Not because you misunderstood, but because you didn't even consider that you might have misunderstood.

14! is the total number of permutations, but each permutation contains 14 items, so you should be comparing the new lower bound - 93,884,313,611 - with 14 * 14!, which is 1,220,496,076,800.

Erdos number

[jspey]

One of the paper authors, Jay Pantone, has an Erdos number of 3. That means Anonymous 4chan Poster has an Erdos number of 4. Pretty good for an anonymous 4chan poster.

Is this Slashdot?

[SinGunner]

This is what I want every Slashdot post to be like. Relevant, interesting article. Informative comments. Math, anime and 4chan, oh my!