Mystery Math Whiz and Novelist Advance Permutation Problem (quantamagazine.org) 108
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."
Explanation (Score:5, Interesting)
Would someone please explain why it wouldn't just be 14! for all permutations?
Re:Explanation (Score:5, Informative)
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: (Score:1)
Thanks. That is a reasonable way of viewing the orders. And thanks also to the others' explanations.
Re:Explanation (Score:5, Informative)
Re: (Score:2)
Re: (Score:2)
THANK YOU ... Such a simple and clear explanation. I was so happy to understand it properly.
I wish I had mod points so that everyone would get the concept clearly.
( may many of these opportunities happen to you again )
Re:Explanation (Score:4, Funny)
I don't think that mod points are quite as powerful as you imagine.
Re: (Score:2)
I know but I got a clear answer and I was overjoyed ... silly I know, but if you can recall wiring an s-100 bus and making it play a tune then you'll understand the happiness of it.
Re: (Score:2)
Thankyou from me too, I was also thinking 'why not 14x13x12x... etc'
Re: (Score:2)
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).
Re:Explanation (Score:5, Informative)
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: (Score:3, Informative)
For example 123 should be followed by 231 resulting in 1231. Follow that with 312 for 12312. Next
Re:Explanation (Score:5, Interesting)
There's a related idea in math: De Bruijn sequences. [wikipedia.org] 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: (Score:2)
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.
123121321 is the shortest way, containing only extraneous (invalid) combinations 313 and 131.
Re: (Score:1)
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.
Re: (Score:3)
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: (Score:3)
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: (Score:2)
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?
No, I can no more prove my axioms than the problem can do so (the problem itself just assumes that they are the same) :)
Re: (Score:1)
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
It would be if you have anterograde amnesia [wikipedia.org].
Re: (Score:1)
There indeed are 14! possible orderings, but that's not the length of a watching list.
Let's make things simpler with n=3:
Obviously, you could just watch every possible order one after the other, as in 123132213231312321, for a length of 3 * 3! = 18, but that's too long. The idea is you can be starting a new permutation before finishing the previous one. For example, starting with 12312 gets you 3 different permutations in just 5 episodes
That's where the subtlety in the problem comes from.
Re: (Score:2, Informative)
You already fail at n=2: just watch 1,2,1.
Re: (Score:2)
For a simple example, consider the set (1,2,3).
There are of course six (3!) permutations: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)
However, those are all contained in the sequence (1,2,3,1,2,1,3,2,1), which is 9 elements long. The question is whether 9 is actually the shortest sequence, and how that extends to sets beyond three elements.
Re: (Score:2)
The math question is concerned with a variation of a permutation known as a super permutation. Basically you could string together all of the x episodes in such a way that the individual x! permutations would be embedded within a larger string permuation.
For example, 2 episodes could be viewed as separate permutations 12 or 21 (four episodes). But you could also watch them as 121.
Similarly 3 episodes could be 123, 132, 213, 231, 312 and 321 (18 episodes). But you could also view them as a shorter string tha
Re: (Score:1)
The question isn't the number of permutations, but the length of the shortest string containing all permutations as substrings. So say you have 3 episodes A,B,C. There are 6 permutations. You could watch all 6 permutations in a row, this would emply watching 18 episodes (3 * 6).
But you could also do it differently:
ABCABACBA
By watching these 9 episodes you have now watched all 6 permutations, in the following order:
- ABC
- BCA
- CAB
- BAC
- ACB
- CBA
Re: (Score:1)
You're not looking for all possible permutations of a set of n elements.
You're looking at the minimum size of a string of N elements that has to contains all permutations of a set of m elements.
So take for instance the set S = {1,2,3).
All possible permutations is a set of 6 element. But that is not what you're looking for. You want amid the infinity of strings made of up of 1,2 and 3 the minimum length one that contains all permutations of {1,2,3}. So 1,2,3,1,2,3,1,3,2,1,3,2,1 gives you a string of length 1
Re: (Score:2)
Would someone please explain why it wouldn't just be 14! for all permutations?
I believe the puzzle requires not calculating all permutations, but figuring out the shortest common supersequence [geeksforgeeks.org].
N! (Score:1)
Isn't this just N!?
If I have N things, the number of possible orderings are N * N-1 * N-2 * N-3 ... * 1. No? Am I misunderstanding what they are computing?
Re: (Score:1)
Yes, you are. The question is how short can a list be and contain every one of those permutations?
Re:N! (Score:5, Insightful)
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: (Score:1)
I guess reading the article and not just the summary clarifies things. Derp!
Amazeballs (Score:1)
Math proofs, urination dossiers...is there anything 4chan can't do?
4 chan is turing complete (Score:3)
It can do anything But no one can prove if a conversation will end. The halting condition is Hitler.
Re: (Score:1)
halting condition? half the time that's the STARTING condition...
Re: (Score:2)
It can't keep the /pol/tards in their containment forum and it can't keep the philosophags out of /lit/.
What's the actual "problem"? (Score:1)
It sounds like it's just a permutation problem from the description. Can someone describe better why this is actually interesting?
Re: (Score:2)
What’s the actual problem? Besides the fact that someone is way too addicted to anime?
Re: (Score:2)
Why is this interesting...
I am in real estate by trade but this problem ( solution ) has some wonderful idea's that might benefit everyone
This is something crazy BUT taking medicine ( this was my first thought )
SIDE NOTES: Sadly my Grand Mother was a huge pill popper back when she was alive to the point that I dislike any medicine until I read it entirely, and ask lots of questions. to this day I can name every prescription I've ever had since childhood ( I'm 51 )
I think the average older person take 5 to 1
Re: (Score:1)
Re: !14 is smaller than 93,884,313,611 (Score:5, Informative)
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.
Re: (Score:3)
It's not 14! you want to compare the lower bound with, it's 14! * 14.
Re: (Score:3)
14! is the number of PERMUTATIONS, so you would watch ALL 14 episones in 87178291200 different orders.
Re: (Score:2)
Here's the funny part.
If each Episode was 30 mins, then it would take you 4,975,929 years to watch them all....
Re: (Score:2)
How is 93,884,313,611 the lower bound? 14! is 87,178,291,200
Because its not 14!, its 14! * 14 which is much larger than 14! * 13! * 12! * 11 which is the lower bound (93,884,313,611).
Re: (Score:2)
How is 93,884,313,611 the lower bound? 14! is 87,178,291,200
Because its not 14!, its 14! * 14 which is much larger than 14! * 13! * 12! * 11 which is the lower bound (93,884,313,611).
Oops, that should read 14! + 13! + 12! + 11
Obvious lower bound (Score:1)
If you're watching only 2 episodes, 2! is not enough, you need at least 3 (either 121 or 212 will do). Basically, you're overlapping n! lists each n episodes long - but the last list has to add the other n - 1 episodes to get a full list.
In all the small cases that I've tried this lower bound is the actual minimum number needed
Re: (Score:1)
An obvious lower bound is n! + n - 1
Only for very small values of n. Things get a bit more complex when n > 3.
The anonymous 4chan poster’s lower bound from TFA is n! + (n – 1)! + (n – 2)! + n – 3.
Re: (Score:2)
An upper bound is (2n-1)(n-1)!
1234123 (or 2341234 or 3412341 or 4123412)
1243124
1324132
1342134
1423142
1432143
There are 4 different 4-element lists in each row, so that includes all 24 possibilities. But trivially you can overlap them onto each other by at last 1 element (except the last one) so instead of 42 we can reduce it to 37
Re:De Bruijn sequence (Score:5, Informative)
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.
So whats the answer? (Score:1)
Is the anime good or not?
Re: (Score:1, Funny)
It depends on what order you watch the episodes in.
Re: (Score:1)
Kyon-kun, denwa!
Re: So whats the answer? (Score:1)
Watch Endless Eight. Realize they had the motherfuxking balls to do what they did.
Realize it doesn't matter how good the series is, give them props for being hung like Donkeys.
Then watch the movie.
Re: (Score:2)
Re: (Score:2)
Is the anime good or not?
The anime is very good and some episodes could get an excellent or even masterpiece rating. However I would not recommend it to a viewer that is new to anime. They would miss a lot of the significance of some features.
Best points: Surprisingly thoughtful premise combined with strong performances. This is true of both the original Japanese sound track (Aya Hirano as Haruhi is brilliant and do not miss her singing) and also the English dubs (Wendee Lee is also great as Harhui but her singing isn't
Come on, man! (Score:2)
Season one of the show, which involves time travel, had originally aired in nonchronological order
Which isn't actually a problem for time travellers, give me a break editors!
Don't know if want (Score:2)
2011 on 4chan
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.
He was too busy studying the Kim K. photos; this was before the third hip siliconization expansion.
Erdos number (Score:4, Interesting)
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.
Re: (Score:2)
Is this Slashdot? (Score:5, Funny)
Ah! Complexity!! (Score:2)
Think on this: What if the order you watched the episodes changed the content of the subsequent episodes? Would you have to start over again and make different choices in your order?
What if the order you watched the episodes changed the content of the episodes you already watched?
These questions are important to many different disciplines such as Biology, Economics, Mathematics, Robotics, and many, many more.
I usually recommend two books that touch on the subject: For Economics I recommend, "The Origin of W
Greg Egan's science fiction stories are damn good (Score:2)
I first stumbled across Greg Egan's work about ten years ago via another slashdot poster... he writes really good hard science fiction.
My favorite is probably Diaspora [gregegan.net]. Things start off with a mass extinction event due to a nearby gamma ray burst. Things ramp up from there as the robotic and electronic survivors set out to explore the universe, in a bid to find other potential dangers and ensure survival. Their journey takes them on a grand exploration of the galaxy, simulated virtual universes, and para
Re: (Score:1)
Only to people who don't know what it means.
Combinatorics is an entire field of mathematics. As much as it is geekily applied to an Anime series, the utility of the maths to other fields is very real.
Your lack of understanding has no bearing whatsoever on the real, actual mathematics which is being advanced here. That's all you, not what is being discussed in the article.
Re: (Score:2)
How do you know that if you don't even know "WTF" it is?