Computer Scientists Make Progress on Math Puzzle
UT Dallas Team’s Approach to an Old Problem is Praised as ‘Elegant’
Two UT Dallas computer scientists have made progress on a nearly 4-decade-old mathematical puzzle, producing a proof that renowned Stanford computer scientist Don Knuth called “amazing” in his communication back to them.
Created by the mathematician John Conway and known as Topswops, the puzzle starts like this: Begin with a randomly ordered deck of cards numbered 1 to n, with n being however high a number you choose. Now count out the number of cards represented by whatever card is the top card, and turn that block of cards over on top of the remaining cards. Then count out the number of cards represented by the new top card and turn this whole block over on top of the remaining cards. Repeat until the card numbered 1 comes to the top (realizing that we know the card numbered 1 will always eventually come to the top).
Now here’s what needs to be done: Calculate the maximum and minimum number of steps required with n number of cards.
Knuth had previously proved an exponential upper bound on the number of Topswops steps, and conjectured that one might also prove a matching lower bound. What Dr. Hal Sudborough and Dr. Linda Morales did, however, was to prove a quadratic lower bound that is much better than that proposed in Knuth’s conjecture, and Knuth declared their proof technique both “elegant” and “amazing.”
“What I find fascinating about a problem such as bounding the Topswops function is connected to its simplicity, to its fundamental nature, and to the complexity and difficulty of finding an answer,” said Sudborough, the Founders Professor at the Erik Jonsson School of Engineering and Computer Science. “An easily described, easily communicated problem is invaluable for engaging a wide array of participants, from high school students to the most eminent mathematicians.”
He also cited Martin Gardner, a longtime columnist for Scientific American, who wrote of problems such as Topswops, “Let it not be supposed that those Conway card games are trivial. They deal with the theory of set permutations and not only may provide deep theorems but also may have a bearing on practical problems that arise in seemingly unrelated fields.”
And then there’s the sheer mathematical beauty that the problem reveals.
“The Topswops process is a simple one,” said Morales, a senior lecturer in computer science. “The basic algorithm is easily understood by almost anyone, regardless of their training or interests. But the simplicity is deceptive. Hiding behind it is a mathematical world of unexpected richness and beauty. Our research uncovered permutations whose iterate sequences have a fascinating structure, which upon analysis have revealed hitherto unknown lower bounds for the problem. There is much more to learn from the problem. We have tantalizing hints of more revelations just waiting to be uncovered.”
The lower bound result appears as “A Quadratic Lower Bound for Topswops” in the October 2010 issue of the journal Theoretical Computer Science, and is now included in Knuth’s The Art of Computer Programming, Fascicle Two, written as a precursor to the soon-to-appear The Art of Computer Programming, Volume 4.
Dr. Linda Morales and Dr. Hal Sudborough
UT Dallas Researchers ContinueRelated Work on Topswops Problem
In a related issue, Sudborough, Morales and their graduate students have also computed the maximum number of Topswops steps over all permutations of length n for small integers n.
Because there are more than 355 trillion different permutations of length 17, a brute force approach of trying all such permutations, one after the other, would require months of computation time. Knuth, who had previously computed the exact number for n=16, used a new, innovative approach, which allowed much shorter computation times. The UT Dallas group made several additional improvements and was able to determine that permutations of length 17 require at most 159 Topswops steps.
And their new technique required only a few days of computation. They have continued by also showing there is a permutation of length 18 that terminates with all cards in sorted order in 191 Topswops steps and that no such permutation of length 18 takes more than 191 steps. Why is that a noteworthy achievement of computational performance? Because there are more than 6 quadrillion permutations of length 18.
Media Contact: The Office of Media Relations, UT Dallas, (972) 883-2155, [email protected].