The Art and Craft of Problem Solving

130 CHAPTER 4 THREE IMPORTANT CROSSOVER TACTICS

Then there is a triangle with side lengths a, b, c.

2. Let 00 = e^2 7r:i/^3. Without loss of generality, let 0 = 0 (i.e., let the center of the

circle be placed at the complex origin), and set A = 1, B = 00, C = 002 , and

p = z, where z is an arbitrary point in the complex plane satisfying Izl < 1.

3. Use (1) to verify that there is a triangle with the indicated side lengths. You

will need to pick your a, f3 carefully, but you should use the playwright Anton

Chekhov's famous quote for inspiration: "If a gun is on the fireplace mantle in

the first act, it must go off in the third."

4. Finally, compute the area of the triangle, using the simple formula you derived

on page 124, and show that this area depends only on Izl, the distance from P

to O.

Example 4.2. 16 Let m and n be integers such that each can be expressed as the sum of

two perfect squares. Show that mn has this property as well. For example, 17 = 44 + 1

and 13 = 22 + 3^2 and, sure enough,

17·13 = 221 = 142 +5^2. (1)

Solution: Let m = a^2 + b^2 , n = c^2 + d^2 , where a, b, c, d are integers. Now con­

sider the product

z:= (a+ bi)(c+di).

Note that

Izl = l(a+bi)llc+dil = V(a^2 +b^2 )(c^2 +d^2 ).

Therefore mn = Iz 12. But Izl^2 will be a sum of squares of integers, since Rez and Imz

are integers. Not only does this prove what we were looking for; it gives us an algo­

rithm for computing the values in the right-hand side of equations such as (1). •

Our final example is a surprising problem that shows how roots of unity can be

used to create an invariant.

Example 4.2. 17 (Jim Propp) Given a circle of n lights, exactly one of which is initially

on, it is permitted to change the state of a bulb provided one also changes the state of

every dth bulb after it (where d is a a divisor of n strictly less than n), provided that all

n/d bulbs were originally in the same state as one another. For what values of n is it

possible to tum all the bulbs on by making a sequence of moves of this kind?

Solution: The insight here is to realize that this is not a problem about lights, but

about roots of unity

1 , S, S^2 , ... , Sn-l ,

where S = cos^2 :: + i sin^2 ::. Place each light on the unit circle located at a root of

unity and, without loss of generality, let the light at 1 be on initially. Now, if d < n is

a divisor of n and the lights at

Sa, Sa+d, Sa+^2 d, ... , Sa+(�-l)d