|
"The Man Who Loves Only Numbers" by Paul Hoffman
from THE ATLANTIC MONTHLY, Volume 260 Number 5, November 1987
If anyone would appreciate a copy of this very engaging article
I'd be happy to provide one if they send a request including
their name and mailstop to SYZYGY::SOPKA.
re: the dinner guest problem, here's an extract from the article:
"The classic Ramsey problem involves guests at a party. What is
the minimum number of guests that need to be invited so that either
at least three guests will know each other or at least three won't?
... assume that the relation of knowing someone is symmetric ...
<< an informal proof that the number is six is presented >>
"Suppose we want not a threesome but a foursome who either all
know each other or are strangers. How large must the party be?
Erdos and Graham and their fellow Ramsey theorists can prove that
eighteen guests are necessary. But raise the ante again, to a
fivesome, and no one knows how many guests are required. The
answer is known to lie between forty-two and fifty-five. That
much has been known for two decades, and Graham suspects that the
precise number won't be found for at least a hundred years. The
case of a sixsome is even more daunting, with the answer known to
lie between 102 and 169. The ranges grow wider still for higher
numbers.
"Erdos likes to tell the story of an evil spirit that can ask you
anything it wants. If you answer incorrectly, it will destroy
humanity. "Suppose," Erdos says, "it decides to ask you the
Ramsey party problem for the case of a fivesome. Your best tactic,
I think, is to get all the computers in the world to drop what
they're doing and work on the problem, the brute-force approach
of trying all the specific cases" -- of which there are more
than 10 to the 200th power. "But if the spirit asks about a
sixsome, your best tactic would be to attack the spirit before
it attacks you. There are too many cases even for computers."
|