The Art and Craft of Problem Solving

68 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS

While the other students slowly added the numbers, little Carl disc overed a short­

cut and immediately arrived at the answer of 5,050. He was the only student to find the

correct sum. His insight was to notice that 1 could be paired with 100, 2 with 99, 3 with

98, etc. to produce 50 identical sums of 101. Hence the answer of (^101) · 50 = 5050.
Another, more formal way of doing this is to write the sum in question twice, first
forward, then backward :
S = 1 + (^2) + ... + (^99) + 100,
S = 100 + (^99) + ... + (^2) + (^1).

Then, of course, 2S = 100 · 101. The advantage of this method is that it does not

matter whether the number of terms was even or odd (notice that this is an issue with

the original pairing method).

This is a pretty good trick, especially for a lO-year-old, and it has many appli­

cations. Don't be restricted to sums. Look for any kind of symmetry in a problem

and then investigate whether a clever pairing of items can simplify things. First, let's

tackle the "Locker problem," which we first encountered in Example 2.2.3 on page 29.

Recall that we reduced this problem to

Prove that d (n) is odd if and only if n is a perfe ct square,

where d(n) denotes the number of divisors of n, including 1 and n. Now we can

use the Gaussian pairing tool. The symmetry here is that one can always pair a di­

visor d of n with njd. For example, if n = 28, it is "natural" to pair the divisor 2

with the divisor 14. Thus, as we go through the list of divisors of n, each divisor

will have a unique "mate" unless n is a perfe ct square, in which case Vn is paired

with itself. For example, the divisors of 28 are 1,2,4,7, 14,28, which can be rear­

ranged into the pairs ( 1 ,28), (2, 14), (4,7), so clearly d(28) is even. On the other

hand, the divisors of the perfect square 36 are 1 , 2,3,4,6,9 , 12, 18,36, which pair into

(1,36), (2, 18), (3,12), (4,9), (6,6). Notice that 6 is paired with itself, so the actual

count of divisors is odd (several true pairs plus the 6, which can only be counted once).

We can conclude that d(n) is odd if and only if n is a perfect square.^2 •

The argument used can be repeated almost identically, yet in a radically different

context, to prove a well-known theorem in number theory.

Example 3.1.9 Wilson's Theorem. Prove that for all primes p,

(p- l)! == - 1 (modp).

Solution: First try an example. Let p = 13. Then the product in question is

1 ·2· 3 · 4 · (^5) · 6 · 7. (^8) · (^9) · (^10) · 11. 12. One way to evaluate this product modulo 13 would
be to multiply it all out, but that is not the problem solver's way! We should look
for smaller subproducts that are easy to compute modulo p. The easiest numbers to

compute with are 0, 1 and -1. Since p is a prime, none of the factors 1 ,2, 3, ... p - 1

are congruent to 0 modulo p. Likewise, no subproducts can be congruent to O. On

the other hand, the primality of p implies that every non-zero number has a unique

2 A completely different argument uses basic counting methods and parity. See Problem 6. 1 .2 1 on page 195.