Page 120 - Discrete Mathematics and Its Applications

1.8 Proof Methods and Strategy 99

(a) (b)

FIGURE 1 (a) Chomp (Top Left Cookie Poisoned). (b) Three Possible Moves.

move of a winning strategy (and then continued to follow that winning strategy). This would
guarantee a win for the first player.
Note that we showed that a winning strategy exists, but we did not specify an actual winning
strategy. Consequently, the proof is a nonconstructive existence proof. In fact, no one has been
able to describe a winning strategy for that Chomp that applies for all rectangular grids by
describing the moves that the first player should follow. However, winning strategies can be
described for certain special cases, such as when the grid is square and when the grid only has
two rows of cookies (see Exercises 15 and 16 in Section 5.2). ▲

Uniqueness Proofs

Some theorems assert the existence of a unique element with a particular property. In other
words, these theorems assert that there is exactly one element with this property. To prove a
statement of this type we need to show that an element with this property exists and that no
other element has this property. The two parts of a uniqueness proof are:

Existence: We show that an element x with the desired property exists.
Uniqueness: We show that if y = x, then y does not have the desired property.
Equivalently, we can show that if x and y both have the desired property, then x = y.

Remark: Showing that there is a unique element x such that P(x) is the same as proving the
statement ∃x(P (x) ∧∀y(y = x →¬P (y))).

We illustrate the elements of a uniqueness proof in Example 13.

EXAMPLE 13 Show that if a and b are real numbers and a = 0, then there is a unique real number r such that
ar + b = 0.

Solution: First, note that the real number r =−b/a is a solution of ar + b = 0 because
a(−b/a) + b =−b + b = 0. Consequently, a real number r exists for which ar + b = 0. This
is the existence part of the proof.
Second, suppose that s is a real number such that as + b = 0. Then ar + b = as + b, where
r =−b/a. Subtracting b from both sides, we find that ar = as. Dividing both sides of this last
equation by a, which is nonzero, we see that r = s. This means that if s = r, then as + b = 0.
This establishes the uniqueness part of the proof. ▲