Computer scientists make progress on math puzzle

October 28, 2010

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

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

Related Stories

Making decisions is the third way we learn, research shows

October 11, 2010

Experts have long believed there are two main ways our brains work: cognition, which is thinking or processing information, and affect, which is feeling or emotion. However, a new breakthrough was just made in regard to a ...

Recommended for you

The dark side of Nobel prizewinning research

October 4, 2015

Think of the Nobel prizes and you think of groundbreaking research bettering mankind, but the awards have also honoured some quite unhumanitarian inventions such as chemical weapons, DDT and lobotomies.

How much for that Nobel prize in the window?

October 3, 2015

No need to make peace in the Middle East, resolve one of science's great mysteries or pen a masterpiece: the easiest way to get yourself a Nobel prize may be to buy one.

Search for Egypt's Nefertiti gains new momentum (Update)

September 29, 2015

The search for ancient Egypt's Queen Nefertiti in an alleged hidden chamber in King Tut's tomb gained new momentum as Egypt's Antiquities Minister said Tuesday he is now more convinced a queen's tomb may lay hidden behind ...


Adjust slider to filter visible comments by rank

Display comments: newest first

not rated yet 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.
4 / 5 (4) Oct 28, 2010

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.
not rated yet 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??
not rated yet 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.
not rated yet 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.
5 / 5 (2) Oct 28, 2010
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.)
not rated yet 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.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.