# Computer scientists make progress on math puzzle

##### October 28, 2010

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

## Related Stories

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

October 4, 2010

Shing-Tung Yau sees a beautiful universe around him, crafted by nature into the shapes and forms we see every day. Mathematics describes those shapes and forms, the discipline of geometry in particular. So, to Yau, it shares ...

#### Research shows workers who begin careers during recession suffer long-term, negative effects on earnings

October 4, 2010

(PhysOrg.com) -- For workers who have managed to land jobs in this tough economy, your employment woes may not be over.

#### 99 year old Skyper shows why aged care facilities should offer internet access

October 5, 2010

(PhysOrg.com) -- Internet access should be mandatory in all aged care facilities, according to a University of Melbourne expert.

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

#### Menominee County shakeup was an earthquake, says researcher

October 12, 2010

That shaking and loud noise experienced recently in Menominee County of Upper Michigan was indeed an earthquake, albeit a small one, according to a Michigan Tech researcher.

#### Reckless betting, losing caused by gamblers' winning streaks

October 22, 2010

"Know when to hold 'em and know when to fold 'em" is an adage that doesn't seem to apply to gamblers who are winning big, according to research conducted at the University of Notre Dame.

## Recommended for you

#### One of the most significant Etruscan discoveries in decades names female goddess Uni

August 24, 2016

Archaeologists translating a very rare inscription on an ancient Etruscan temple stone have discovered the name Uni—an important female goddess.

#### Researchers plumb the secrets of tissue paper

August 24, 2016

Canada's tissue manufacturers are now much closer to producing the perfect paper, thanks to new UBC research.

#### More than a few good men: Study finds counterintuitive outcomes of gender imbalance

August 24, 2016

Contrary to traditional expectations of unbalanced sex ratios, places with more men than women do not typically experience higher rates of family and social instability, according to a University of Utah study. The study, ...

#### Urban sociologists call for expanding concepts of 'livable cities'

August 24, 2016

A commentary in the current issue of the journal Nature, co-written by Hillary Angelo, UC Santa Cruz assistant professor of sociology, argues that while big cities appear to be islands of sustainable living, issues of social ...

#### Paleontologists discover major T. rex fossil (Update)

August 18, 2016

Paleontologists with the Burke Museum of Natural History and Culture and the University of Washington have discovered a Tyrannosaurus rex, including a very complete skull. The find, which paleontologists estimate to be about ...

#### Is divorce seasonal? Study shows biannual spike in divorce filings

August 21, 2016

To everything there is a season—even divorce, new research from University of Washington sociologists concludes.

##### Pkunk_
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.
##### El_Nose
4 / 5 (4) 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.
##### El_Nose
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??
##### Skeptic_Heretic
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.
##### El_Nose
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.
##### PinkElephant
5 / 5 (2) 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.)
##### Sanescience
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.