Slashdot Mirror

← Back to Stories (view on slashdot.org)

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

Posted by msmash on from the marching-forward dept.

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."

61 of 108 comments (clear)

  1. Explanation by Mikkeles · · Score: 5, Interesting

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

    --
    Great minds think alike; fools seldom differ.
    1. Re:Explanation by Anonymous Coward · · 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.

    2. Re:Explanation by john83 · · 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. 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.

      --
      Strange women lying in ponds distributing swords is no basis for a system of government.
    3. Re:Explanation by Anonymous Coward · · 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.

    4. Re:Explanation by Anonymous Coward · · 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.

    5. Re:Explanation by Sarten-X · · Score: 1

      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.

      --
      You do not have a moral or legal right to do absolutely anything you want.
    6. Re:Explanation by jfdavis668 · · Score: 1

      I would mark this up, but I don't have any points right now.

    7. Re:Explanation by Moblaster · · Score: 1

      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 that includes all permutations: 123121321.

      The interesting mathematical issues is that the pattern to compute the length of the permutation that holds for permutation lengths 1 through 5 breaks down at length 6 (and for all others). So these proofs give a better answer for arbitrary length permutations beyond 5.

    8. Re:Explanation by Anonymous Coward · · 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

    9. Re:Explanation by Anonymous Coward · · 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 13 that contains all the possible permutations of (123). And 13 is diffrent from 3! = 6.

    10. Re:Explanation by cascadingstylesheet · · Score: 2

      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

    11. Re:Explanation by Anonymous Coward · · Score: 2, Informative

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

    12. Re:Explanation by onepoint · · Score: 1

      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 )

      --
      if you see me, smile and say hello.
    13. Re:Explanation by famebait · · 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?

      --
      sudo ergo sum
    14. Re:Explanation by spiny · · Score: 1

      Thankyou from me too, I was also thinking 'why not 14x13x12x... etc'

      --

      Fry: heh, Yakov Smirnoff said it
      Leela: No he didn't.
    15. Re:Explanation by Snotnose · · Score: 1

      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).

    16. Re:Explanation by sfcat · · Score: 4, 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.

      --
      "Those that start by burning books, will end by burning men."
    17. Re:Explanation by Mikkeles · · Score: 1

      Thanks. That is a reasonable way of viewing the orders. And thanks also to the others' explanations.

      --
      Great minds think alike; fools seldom differ.
    18. Re:Explanation by dmomo · · Score: 1

      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.

    19. Re:Explanation by cascadingstylesheet · · 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

      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) :)

    20. Re:Explanation by randm.ca · · Score: 3, Informative

      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.

    21. Re:Explanation by lgw · · Score: 4, Interesting

      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.

      --
      Socialism: a lie told by totalitarians and believed by fools.
    22. Re:Explanation by Paradise+Pete · · Score: 4, Funny

      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.

    23. Re:Explanation by null+etc. · · Score: 1

      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.

    24. Re:Explanation by onepoint · · Score: 1

      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.

      --
      if you see me, smile and say hello.
  2. N! by gerald.edward.butler · · 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?

    1. Re:N! by Anonymous Coward · · Score: 1

      Yes, you are. The question is how short can a list be and contain every one of those permutations?

    2. Re:N! by famebait · · 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.

      --
      sudo ergo sum
    3. Re:N! by gerald.edward.butler · · Score: 1

      I guess reading the article and not just the summary clarifies things. Derp!

  3. Amazeballs by Anonymous Coward · · Score: 1

    Math proofs, urination dossiers...is there anything 4chan can't do?

    1. Re:Amazeballs by sheramil · · Score: 1

      It can't keep the /pol/tards in their containment forum and it can't keep the philosophags out of /lit/.

  4. What's the actual "problem"? by Anonymous Coward · · Score: 1

    It sounds like it's just a permutation problem from the description. Can someone describe better why this is actually interesting?

    1. Re:What's the actual "problem"? by 93+Escort+Wagon · · Score: 1

      What’s the actual problem? Besides the fact that someone is way too addicted to anime?

      --
      #DeleteChrome
    2. Re:What's the actual "problem"? by onepoint · · Score: 1

      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 10 different pills a day. two or three times in the day
      what if we could discover an order in which they could take the pills that reduced the number of pills but had the same effects and outcomes.
      this could change the world or even better, discover something that would advance the worlds health.

      My grandma lived to 96 years of age. last 4 years were the worst. tough old lady with a steal trap mind.

      --
      if you see me, smile and say hello.
  5. 4 chan is turing complete by goombah99 · · Score: 2

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

    --
    Some drink at the fountain of knowledge. Others just gargle.
    1. Re:4 chan is turing complete by Anonymous Coward · · Score: 1

      halting condition? half the time that's the STARTING condition...

  6. Re:!14 is smaller than 93,884,313,611 by axlash · · Score: 2

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

    --
    Deal with reality - the world as it is - rather than ideality - the world as you would like it to be.
  7. Re:!14 is smaller than 93,884,313,611 by spiny · · Score: 2

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

    --

    Fry: heh, Yakov Smirnoff said it
    Leela: No he didn't.
  8. Re:Search for Mr Goodbar. by Anonymous Coward · · Score: 1

    obviously it was Satoshi Nakamoto

  9. Re:!14 is smaller than 93,884,313,611 by sfcat · · Score: 1

    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).

    --
    "Those that start by burning books, will end by burning men."
  10. Re:!14 is smaller than 93,884,313,611 by sfcat · · Score: 1

    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

    --
    "Those that start by burning books, will end by burning men."
  11. So whats the answer? by Mes · · Score: 1

    Is the anime good or not?

    1. Re:So whats the answer? by Anonymous Coward · · Score: 1, Funny

      It depends on what order you watch the episodes in.

    2. Re:So whats the answer? by Anonymous Coward · · Score: 1

      Kyon-kun, denwa!

    3. Re: So whats the answer? by Anonymous Coward · · 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.

    4. Re:So whats the answer? by ukoda · · Score: 1

      It was ok but not great. The 'Time travel' was just a time loop, think Groundhog Day but for many episodes they did basically the same thing every time, unlike Groundhog Day where the main character often did radically different things. As a result it made for boring viewing for quite a while. I almost got to the point of skipping episodes and certainly paid a lot less attention after the third loop.

    5. Re:So whats the answer? by AlanObject · · Score: 1

      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 as good as Hirano -- Crispin Freeman might have just been born for his role as Kyon). On top of that we now have most of a generation of boys and girls who worship Yuuki Nagato, a supporting character.

      Worst points: Haruhi's personality can get genuinely tiresome. Her domineering sexual abuse of Mikuru comes to mind. That is actually a feature not a bug but it doesn't change that it gets tiresome.

      If you do watch anime this can be considered a must.

  12. Re:WTF is this by Anonymous Coward · · Score: 1

    This article diminishes the credibility of all of Slashdot

    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.

  13. Re:De Bruijn sequence by Dahan · · Score: 4, 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.

  14. Re:WTF is this by wonkey_monkey · · Score: 1

    How do you know that if you don't even know "WTF" it is?

    --
    systemd is Roko's Basilisk.
  15. Re: !14 is smaller than 93,884,313,611 by wonkey_monkey · · 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.

    --
    systemd is Roko's Basilisk.
  16. Come on, man! by Impy+the+Impiuos+Imp · · Score: 1

    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!

    --
    (-1: Post disagrees with my already-settled worldview) is not a valid mod option.
  17. Don't know if want by Impy+the+Impiuos+Imp · · Score: 1

    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.

    --
    (-1: Post disagrees with my already-settled worldview) is not a valid mod option.
  18. Erdos number by jspey · · Score: 3, 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.

    --
    Cover your butt. Bernard is watching.
    1. Re:Erdos number by Binestar · · Score: 1

      Sounds like we need to create a new number. Anonymous 4chan Poster number. He's a 0 of course. Everyone else works outward from him.

      --
      Do you Gentoo!?
  19. Is this Slashdot? by SinGunner · · Score: 5, Funny

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

  20. Ah! Complexity!! by meburke · · Score: 1

    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 Wealth" by Beinhocker https://www.amazon.com/dp/B077... . It is very readable and will stretch the mind. For Technology I recommend, "Out of Control" by Kevin Kelly. It is also very readable, and will also stretch your mind https://kk.org/kevinkelly/out-... . I recommend the PDF version because Kelly added more illustrations, annotations and footnotes.

    In Economics, Frederich Hayek proved, back in about 1929, that this type of complexity made true command and control Economics implausible, and probably impossible. Marxists, Socialists and Stafford Beer (before he bankrupted Chile) https://en.wikipedia.org/wiki/... , should have taken notice.

    --
    "The mind works quicker than you think!"
  21. Greg Egan's science fiction stories are damn good by jheath314 · · Score: 1

    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. 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 parallel dimensions. Through it all, Egan throws in plenty of real math to make things interesting.

    --
    Procrastination Man strikes again!
  22. Re:Obvious lower bound by Pow · · 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.

  23. Re:!14 is smaller than 93,884,313,611 by neoRUR · · Score: 1

    Here's the funny part.
    If each Episode was 30 mins, then it would take you 4,975,929 years to watch them all....

  24. Re:Obvious lower bound by sgunhouse · · Score: 1

    I was coming up with this issue today.

    An upper bound is (2n-1)(n-1)! ... but that's easy to improve on. That particular number can be see as the following (for n = 4):

    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 ... but that's still not optimal as you could sometimes overlap 2 items.

    Let's see... 1234123142312431213421324132143214 for 33

    Mind you, a correct answer can't involve (n-2)! if it is going to apply to n = 1, maybe sum(k!, k = 1 to n)?