The Art and Craft of Problem Solving

94 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS

Example 3.4.5 Divisibility by Nine. Let s(n) be the sum of the digits of the base-ten

representation of the positive integer n. Then

n - s(n) is always divisible by (^9).
For example, if n = 136, then
n-s(n)= 136 - (1 +3+6)= 126 =9·1 4.
This was an example of a non-numeric invariant, although we could have recast things
in a numeric form by saying, for example, that the remainder upon division by 9 of
n -s( n) is the invariant quantity zero.
Here is another example of a divisibility invariant.
Example 3.4.6 At first, a room is empty. Each minute, either one person enters or two
people leave. After exactly 31999 minutes, could the room contain 31000 + 2 people?
Solution: If there are n people in the room, after one minute, there will be ei­
ther n + 1 or n - 2 people. The difference between these two possible outcomes is 3.
Continuing for longer times, we see that
At any fixed time t, all th e possible values fo r the population of the
room differ fr om one another by multiples of 3.
In 31999 minutes, then, one possible population of the room is just 31999 people
(assuming that one person entered each time). This is a multiple of 3, so all the pos­
sible populations for the room have to also be multiples of 3. Therefore 31000 + 2 will
not be a valid population. _
The simplest divisibility invariant is parity, which we used in Example 2.2.3 on
page 29 and Example 2.2.4 on page 30. Let us explore this concept in more detail.

Parity

Integers are divided into two parity classes: even and odd. The even integers are

divisible by 2, the odds are not. Note that zero is even. The following facts are easy to

prove rigorously (do it!) but should have been known to you since you were little.

• The parity of a sum of a set of integers is odd if and only if the number of odd
  elements is odd.


• The parity of a product of a set of integers is odd if and only if there are no even
  elements in the set.

You may think that parity is a rather crude thing-after all, there are infinitely

many integers yet only two kinds of parity-yet knowledge of parity is sometimes all

that is needed, especially if parity is involved in the statement of the problem. Here

is a fundamental example, a problem that has appeared in many forms. This version

appeared in the 1986 Colorado Springs Mathematical Olympiad.