Page 122 - Discrete Mathematics and Its Applications

1.8 Proof Methods and Strategy 101

√
(x + y)/2 > xy. We conclude that if x and y are distinct positive real numbers, then their
√
arithmetic mean (x + y)/2 is greater than their geometric mean xy. ▲

EXAMPLE 15 Suppose that two people play a game taking turns removing one, two, or three stones at a time
from a pile that begins with 15 stones. The person who removes the last stone wins the game.
Show that the first player can win the game no matter what the second player does.

Solution: To prove that the first player can always win the game, we work backward. At the
last step, the first player can win if this player is left with a pile containing one, two, or three
stones. The second player will be forced to leave one, two, or three stones if this player has to
remove stones from a pile containing four stones. Consequently, one way for the first person to
win is to leave four stones for the second player on the next-to-last move. The first person can
leave four stones when there are five, six, or seven stones left at the beginning of this player’s
move, which happens when the second player has to remove stones from a pile with eight stones.
Consequently, to force the second player to leave five, six, or seven stones, the first player should
leave eight stones for the second player at the second-to-last move for the first player. This means
that there are nine, ten, or eleven stones when the first player makes this move. Similarly, the
first player should leave twelve stones when this player makes the first move. We can reverse
this argument to show that the first player can always make moves so that this player wins the
game no matter what the second player does. These moves successively leave twelve, eight, and
four stones for the second player. ▲

ADAPTING EXISTING PROOFS An excellent way to look for possible approaches that can
be used to prove a statement is to take advantage of existing proofs of similar results. Often
an existing proof can be adapted to prove other facts. Even when this is not the case, some of
the ideas used in existing proofs may be helpful. Because existing proofs provide clues for new
proofs, you should read and understand the proofs you encounter in your studies. This process
is illustrated in Example 16.
√ √
EXAMPLE 16 In Example 10 of Section 1.7 we proved that 2 is irrational. We now conjecture that 3is
√
irrational. Can we adapt the proof in Example 10 in Section 1.7 to show that 3 is irrational?

Solution: To adapt the proof in Example 10 in Section 1.7, we begin by mimicking the steps in
√ √ √
that proof, but with 2 replaced with 3. First, we suppose that 3 = d/c where the fraction
2
2
2
2
c/d is in lowest terms. Squaring both sides tells us that 3 = c /d , so that 3d = c . Can we
use this equation to show that 3 must be a factor of both c and d, similar to how we used the
2
2
equation 2b = a in Example 10 in Section 1.7 to show that 2 must be a factor of both a
and b? (Recall that an integer s is a factor of the integer t if t/s is an integer.An integer n is even
if and only if 2 is a factor of n.) In turns out that we can, but we need some ammunition from
number theory, which we will develop in Chapter 4. We sketch out the remainder of the proof,
2
but leave the justification of these steps until Chapter 4. Because 3 is a factor of c , it must also
2
be a factor of c. Furthermore, because 3 is a factor of c, 9 is a factor of c , which means that 9
2
2
is a factor of 3d . This implies that 3 is a factor of d , which means that 3 is a factor of that d.
This makes3afactor of both c and d, which contradicts the assumption that c/d is in lowest
√
terms. After we have filled in the justification for these steps, we will have shown that 3is
√
irrational by adapting the proof that 2 is irrational. Note that this proof can be extended to
√
show that n is irrational whenever n is a positive integer that is not a perfect square. We leave
the details of this to Chapter 4. ▲
A good tip is to look for existing proofs that you might adapt when you are confronted
with proving a new theorem, particularly when the new theorem seems similar to one you have
already proved.