Slashdot Mirror
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."
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."
Would someone please explain why it wouldn't just be 14! for all permutations?
Great minds think alike; fools seldom differ.
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.
sudo ergo sum
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.
systemd is Roko's Basilisk.
This is what I want every Slashdot post to be like. Relevant, interesting article. Informative comments. Math, anime and 4chan, oh my!