Computer scientists make progress on math puzzle

(PhysOrg.com) -- 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 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 , 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.

Feedback to editors

Oct 28, 2010
Perhaps computers were made for mathematicians ?
There are problems which our puny brains can barely comprehend but which with simple algorithm's and the brute force approach which computers utilize can be solved in unexpected ways.

Oct 28, 2010
@pkunk

but all proofs bypass brute force and lay a claim on all possibilities with in a confined domain thats why math is so powerful. Brute force is the lazy kids way of solving a problem ... and if the problem is interesting brute force would take several lifetimes of the universe to solve using a computer.

Thats why humans and the human brain is so wonderful. We if we apply ourselves can think through terribly abstract information to grasp a very concrete solution that applies to everything.

I am a CS major with a MS... nothing comes close to a well trained brain ... and for the most part I think the world is better off that way.

If we ever made a computer on par with the human brain ... the next generation of said computer would be smarter than the entire planet and able to design its replacement with ease... thats a road that we should tread with caution.

Oct 28, 2010
my comment about the problem however...

this is to the mathematians out there...

isn't this an abstract algebra problem... It seems reminisent of a finite albelian group. We have a clearly defined operation... we have associativity... and an inverse: a(mod n)^-1 ... and an identity... namely card n... so this is by definition a group. And therefor this is a symetry problem... and all finite albelian groups have been solved...

AM I looking at this correctly??

Oct 28, 2010
Brute force is the lazy kids way of solving a problem ... and if the problem is interesting brute force would take several lifetimes of the universe to solve using a computer.
This isn't exactly correct. There are a great many problems that as so far can only be solved by a computer using brute force. The experiment where you need to determine optimum packing placement of round objects in a square box for instance. That required brute force and a computer. No proof could be found, resulting in the problem showing up on the Millenium Award roster of unsolved problems.

Oct 28, 2010
@ myself

This problem set is not a group. It lacks associativity.

Associativity is (ab)c = a(bc) I made the incorrect assumption that if you had (10*8)*18 = 10*(8*18) the flaw is that this operation is somewhat mechanical in nature so flipping 10 may lead to the number 8 and flipping 8 may lead to 18 and flipping 18 may lead to lets say 4 .... but if you flipped 8 first that will not lead to 18 beaing the next top card .. that order was determined by the inital flip of 10.

I apologize for wasting peoples time.

Oct 28, 2010
@Skeptic_Heretic,
There are a great many problems that as so far can only be solved by a computer using brute force.
I'd go even further, and postulate that MOST real-world problems do not have analytical solutions, and CANNOT IN PRINCIPLE have such solutions.

The analytically solvable problems (where you have a nice clean equation describing the entire problem) are actually a *very tiny* subset of all possible problems. The vast majority of all situations, therefore, can only be resolved via approximate, computational methods (i.e. simulation + statistical extrapolation and bounding.)

Oct 29, 2010
@El_Nose: Regarding mechanical brains and treading lightly... in a way it is an arms race, who will make the first and determine it's "goals", benevolent or malevolent.

Segues into a Ray Kurzweil singularity type discussion.