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

**Explore further:**
Simple beauties of math: Harvard professor views nature itself through geometry's clear lens

## Pkunk_

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.

## El_Nose

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.

## El_Nose

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??

## Skeptic_Heretic

## El_Nose

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.

## PinkElephant

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

## Sanescience

Segues into a Ray Kurzweil singularity type discussion.