Feeds:
Posts

## UT Dallas Computer Scientists Make Progress on Math Puzzle

I thought this recent article was a great demonstration that the creativity, diligence and playfulness that are encouraged in Math Circle can also be a part of a rewarding career.

#### UT Dallas Team’s Approach to an Old Problem is Praised as ‘Elegant’

Oct. 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 card

s 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.”

## AMC 8 Preparation Problem #2

The 16 squares on a piece of paper are numbered as shown in the diagram.  While lying on a table, the paper is folded four times in the following sequence.

1. Fold the top half over the bottom half
2. Fold the bottom half over the top half
3. Fold the right half over the left half
4. Fold the left half over the right half

Which numbered sequence is on top after step 4?

A) 1       B)9      C)10    D)14    E)16

## MC^2 Problem Sets

For those of you who haven’t been fortunate enough to get out to Arlington to visit the Mid-Cities Math Circle,  Dr. Grantcharov has posted the problem sets from his last 3 sessions.

You can find previous session hand out on the Mid Cities Math Circle’s Schedule Page.

## AMC 8 Preparation Problem #1

Dr. Andreescu has allowed me to post some of the problems from his AMC 8 preparation sessions.  Students are welcome to give their answers in the comments section.  Even better would be to use the comments section to defend or extend your answer.

One half of the water is poured out of a full container. Then one third of the remainder is poured out. Continue this process: one fourth of the remainder for the third pouring, one fifth of the remainder for the fourth pouring, etc. After how many pourings does exactly one tenth of the original water remain?

A) 6     B) 7      C) 8    D) 9     E) 10

Students interested in more problems like this one should attend our upcoming session.   I’ll post a couple more problems to the site this week as well.

## October 30 – AMC 8 Preparation Continued!

We had excellent attendance and involvement in last week’s AMC 8 preparation session as Dr. Andreescu shared some of his favorite problems and his unique observations as the former director of the AMC.

Next week Dr. Andreescu will continue his previous lecture with more challenging problems to help prepare our students for success on the up coming contest.

## October 23 – Dr. Andreescu, AMC 8 Preparation

Dr. Titu Andreescu will give the lecture himself next week and focus on helping the students prepare for the upcoming AMC 8 test.  I’ll describe the importance of the AMC 8 below, but even students too old to take this particular test (over 8th grade) will find a great deal of value in this lecture from the former director of the AMC which they can apply to their preparation for the AMC 10 or 12.

AMC 8 is the first in a sequence of contests offered by the Mathematical Association of America.  The results of these tests are ultimately used to select the team that will represent the US at the International Mathematical Olympiad, but the scores are also critical to distinguish a college application from the many perfect SAT math scores received by the elite universities.

Here is information on the AMC 8 for those unfamiliar:

The AMC 8 is a 25 question, 40 minute multiple choice examination in middle school mathematics designed to promote the development and enhancement of problem solving skills. This school year it will be held Tuesday, November 16, 2010. Click here for a current brochure.

The examination provides an opportunity to apply the concepts taught at the junior high level to problems which not only range from easy to difficult but also cover a wide range of applications. Many problems are designed to challenge students and to offer problem solving experiences beyond those provided in most junior high school mathematics classes. Calculators are not allowed starting in 2008. High scoring students are invited to participate in the AMC 10.

A special purpose of the AMC 8 is to demonstrate the broad range of topics available for the junior high school mathematics curriculum. This is done by competencies. The AMC 8 has the potential to increase the perceptions of the importance of problem solving activities in the mathematics curriculum by stimulating these activities both preceding and following the examination —specifically by studying the solutions manual.

Additional purposes of the AMC 8 are to promote excitement, enthusiasm and positive attitudes towards mathematics and to stimulate interest in continuing the study of mathematics beyond the minimum required for high school graduation. Developmentally, junior high school students are at a point where attitudes toward school and learning, and perceptions of themselves as learners of mathematics are solidified. It is important that they be provided opportunities that foster the development of positive attitudes towards mathematics and positive perceptions of themselves as learners of mathematics. The AMC 8 provides one such opportunity.

We encourage all students in grades 6, 7 and 8 to participate in the AMC 8. All USA, USA embassy, Canadian and foreign school students in grade 8 or below are eligible to participate.