Johnston read the argument and thought it seemed plausible, but he didn’t invest much effort in checking it carefully. With this setup, the least-expensive path through the cities corresponds directly to the shortest superpermutation. In the n = 3 example, for instance, the path from 231 to 312 costs $1, since we just have to add a 2 to the end of 231 to get 312, while the path from 231 to 132 costs $2, since we have to add a 32. So we declare the cost of each path to be simply the number of digits we have to attach to the end of the first permutation to get the second one. In the superpermutation problem, we want the shortest possible sequence of digits that lists all the permutations, so the goal is to travel through the permutations in a way that adds as few digits to the starting permutation as possible. The translation is simple: Think of each permutation as a “city” and imagine a path from each permutation to each other permutation. More specifically, superpermutations are connected to the “ asymmetric” traveling salesman problem, in which each path between two cities has a cost (which is not necessarily the same in both directions), and the goal is to find the least expensive route through all the cities. Houston’s construction works by translating the superpermutation problem into the famous traveling salesman problem, which looks for the shortest route through a collection of cities.
Both proofs are now being hailed as significant advances on a puzzle mathematicians have been studying for at least 25 years. Egan’s discovery renewed interest in the problem and drew attention to the lower bound posted anonymously in 2011. 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. 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.
“Please look over for any loopholes I might have missed,” the anonymous poster wrote. 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.
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.
0 kommentar(er)
