Subject: Paulos on problems
Date: Mon, 02 Dec 2002 16:35:53 -0500
From: Scott Williams <sww@buffalo.edu>
Reply-To: sww@buffalo.edu
To: aarms@lists.colorado.edu

Here's an article you might find interesting.

                       Unsolved Math Mysteries
       Math Problems from the Clay Classics to Chomping Cookies

Commentary
By John Allen Paulos
Special to ABCNEWS.com


Dec. 1 - Two years ago the Clay Mathematics Institute near Boston listed seven important questions in mathematics that have never been answered and offered a $1 million reward for the solution of any one of them.

Even the mere statements of these classic unsolved problems, which include the Riemann hypothesis, Poincare conjecture, and the P-NP problem, are difficult to understand. Happily, a just-published book, The Millennium Problems by Keith Devlin, makes them all considerably easier to grasp.

Inspired by this endeavor, I'd like here to briefly describe three unusual problems whose statements are, by contrast, quite elementary. Nevertheless, the problems have all so far resisted solution.

Why Always 4, 2, 1?

To understand the first problem, discovered by Lothar Collatz in 1937, pick any whole number you wish and subject it to the following rule. If the number is even, cut it in half, but if it is odd, multiply it by 3 and add 1. Whatever number results from this, apply the rule to it as well. If you do this over and over again, you'll notice something rather odd about the numbers that you get.

Let's check. Say you pick 13. Since 13 is odd, you multiply it by 3 and add 1 to get the number 40. Since 40 is even, you cut it in half to get 20. Applying the rule now to 20 gives you the number 10. Continuing in this way, you get 5, 16, 8, 4, 2, 1, 4, 2, 1, .... Note that if you get to 1, the 4, 2, 1 will repeat itself indefinitely.

The Collatz Conjecture is that no matter what number you choose, you'll always end up with 4, 2, 1, 4, 2, 1, ....

Sometimes it takes many applications of the rule to get there; even the small number 27, for example, takes 111 steps before it reaches 1. Every number that has been tried does eventually return to 1, but it's never been mathematically proved that every number does.

How Big a Conference?

The next type of problem may be traced to a 1928 paper by British logician Frank Ramsey and has been pursued ever since by many mathematicians. It is sometimes phrased in terms of attendees at a small conference. Let's start with a special case and ask: What is the smallest number of attendees who need to be present so that it is certain that there will be at least 3 who know each other (3 mutual acqaintances) or at least 3 who don't (3 mutual strangers)?

To see that the number is at most 6 imagine that you're one of 6 attendees at a conference. Since you either know or don't know each of the other 5, there are at least 3 of them that you know or at least 3 of them that you don't know. Suppose that you know 3 of them (the argument is similar if there are at least 3 you don't know) and consider what relationships hold among your 3 acquaintances.

If any 2 of them know each other, then these 2 and you constitute a group of 3 mutual acquaintances. On the other hand, if none of your 3 acquaintances know each other, they constitute a group of 3 mutual strangers. Thus 6 attendees are sufficient, and it can be shown that 5 are not. (Can you find an example showing that 5 attendees are not enough?)

Now for harder cases. It's tricky, but it can be shown that a group must contain 18 attendees in order for there always to be at least 4 people in it who are mutually acquainted or at least 4 who are mutual strangers. It is still not known, however, how many people a group must contain in order for there always to be at least 5 people in it who are mutally acquainted or at least 5 who are mutual strangers. (The answer has been shown to lie between 42 and 55.) Despite supercomputers, almost nothing is known about this phenomenon for numbers larger than 5.

How to Avoid the Poisoned Cookie?

The third unsolved problem involves a game called Chomp, invented by mathematician David Gale in 1974. Chomp has very simple rules, but no one has yet found a winning strategy for it that always works. The game requires you to consider a rectangular array of cookies (in rows and columns) in which the cookie in the lower left corner is poisoned. Players A and B must take turns picking any cookie they wish and then eating it as well as any cookies in the region to the right of it and above it. The player who is forced to eat the poisoned cookie loses.

Illustration of the starting position and possible first bites for A and B:

OOOOOOOOOO         OOOO               OO
OOOOOOOOOO         OOOO               OO
OOOOOOOOOO         OOOO               OOOO
OOOOOOOOOO         OOOOOOOOOO         OOOOOOOOOO
POOOOOOOOO         POOOOOOOOO         POOOOOOOOO

It's easy to prove that there exists a winning strategy and that, if he knows it, the first player A can be guaranteed a win. Except in
special cases, however, what that strategy is remains unknown.

One such special case occurs when the cookies are in a square array.  Here A can choose the cookie diagonally up from the corner poisoned cookie and eat it and all cookies to the right and above it. This leaves an L-shaped region with an equal number of cookies in each of its two arms.

A's square strategy:

OOOOO      O
OOOOO      O
OOOOO      O
OOOOO      O
POOOO      POOOO

Then whatever number of cookies B chooses to eat from one arm, A chooses to eat the same number from the other arm. This continues until B is forced to eat the poisoned cookie. Easy in this case, but a general winning strategy that will always work with, for example, 17 rows and 31 columns is not known.

Unfortunately, my $1 million offer for a solution to any of these problems isn't payable until the second Tuesday of the week it's published.