Page 119 - Discrete Mathematics and Its Applications

98 1 / The Foundations: Logic and Proofs

Nonconstructive existence proofs often are quite subtle, as Example 12 illustrates.
EXAMPLE 12 Chomp is a game played by two players. In this game, cookies are laid out on a rectangular grid.
The cookie in the top left position is poisoned, as shown in Figure 1(a). The two players take
turns making moves; at each move, a player is required to eat a remaining cookie, together with
all cookies to the right and/or below it (see Figure 1(b), for example). The loser is the player
who has no choice but to eat the poisoned cookie. We ask whether one of the two players has a
winning strategy. That is, can one of the players always make moves that are guaranteed to lead
to a win?

Solution: We will give a nonconstructive existence proof of a winning strategy for the first
player. That is, we will show that the first player always has a winning strategy without explicitly
describing the moves this player must follow.
First, note that the game ends and cannot finish in a draw because with each move at least
one cookie is eaten, so after no more than m × n moves the game ends, where the initial grid
is m × n. Now, suppose that the first player begins the game by eating just the cookie in the
bottom right corner. There are two possibilities, this is the first move of a winning strategy for
the first player, or the second player can make a move that is the first move of a winning strategy
for the second player. In this second case, instead of eating just the cookie in the bottom right
corner, the first player could have made the same move that the second player made as the first

SRINIVASA RAMANUJAN (1887–1920) The famous mathematical prodigy Ramanujan was born and raised
in southern India near the city of Madras (now called Chennai). His father was a clerk in a cloth shop. His mother
contributed to the family income by singing at a local temple. Ramanujan studied at the local English language
school, displaying his talent and interest for mathematics. At the age of 13 he mastered a textbook used by
college students. When he was 15, a university student lent him a copy of Synopsis of Pure Mathematics.
Ramanujan decided to work out the over 6000 results in this book, stated without proof or explanation, writing
on sheets later collected to form notebooks. He graduated from high school in 1904, winning a scholarship to the
University of Madras. Enrolling in a fine arts curriculum, he neglected his subjects other than mathematics and
lost his scholarship. He failed to pass examinations at the university four times from 1904 to 1907, doing well
only in mathematics. During this time he filled his notebooks with original writings, sometimes rediscovering already published
work and at other times making new discoveries.
Without a university degree, it was difficult for Ramanujan to find a decent job. To survive, he had to depend on the goodwill of
his friends. He tutored students in mathematics, but his unconventional ways of thinking and failure to stick to the syllabus caused
problems. He was married in 1909 in an arranged marriage to a young woman nine years his junior. Needing to support himself and
his wife, he moved to Madras and sought a job. He showed his notebooks of mathematical writings to his potential employers, but
the books bewildered them. However, a professor at the Presidency College recognized his genius and supported him, and in 1912
he found work as an accounts clerk, earning a small salary.
Ramanujan continued his mathematical work during this time and published his first paper in 1910 in an Indian journal. He
realized that his work was beyond that of Indian mathematicians and decided to write to leading English mathematicians. The first
mathematicians he wrote to turned down his request for help. But in January 1913 he wrote to G. H. Hardy, who was inclined
to turn Ramanujan down, but the mathematical statements in the letter, although stated without proof, puzzled Hardy. He decided
to examine them closely with the help of his colleague and collaborator J. E. Littlewood. They decided, after careful study, that
Ramanujan was probably a genius, because his statements “could only be written down by a mathematician of the highest class;
they must be true, because if they were not true, no one would have the imagination to invent them.”
Hardy arranged a scholarship for Ramanujan, bringing him to England in 1914. Hardy personally tutored him in mathematical
analysis, and they collaborated for five years, proving significant theorems about the number of partitions of integers. During this
time, Ramanujan made important contributions to number theory and also worked on continued fractions, infinite series, and elliptic
functions. Ramanujan had amazing insight involving certain types of functions and series, but his purported theorems on prime
numbers were often wrong, illustrating his vague idea of what constitutes a correct proof. He was one of the youngest members ever
appointed a Fellow of the Royal Society. Unfortunately, in 1917 Ramanujan became extremely ill. At the time, it was thought that he
had trouble with the English climate and had contracted tuberculosis. It is now thought that he suffered from a vitamin deficiency,
brought on by Ramanujan’s strict vegetarianism and shortages in wartime England. He returned to India in 1919, continuing to
do mathematics even when confined to his bed. He was religious and thought his mathematical talent came from his family deity,
Namagiri. He considered mathematics and religion to be linked. He said that “an equation for me has no meaning unless it expresses
a thought of God.” His short life came to an end in April 1920, when he was 32 years old. Ramanujan left several notebooks of
unpublished results. The writings in these notebooks illustrate Ramanujan’s insights but are quite sketchy. Several mathematicians
have devoted many years of study to explaining and justifying the results in these notebooks.