The Art and Craft of Problem Solving

72 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS

3.1.18 A polynomial in several variables is called

symmetric if it is unchanged when the variables are

permuted. For example,

J(x,y, z) := X^2 + i + Z^2 +xyz

is symmetric, since

J(x,y,z) = J(X,z,y) = J(y,x,Z) = J(y,z,X)

= J(Z,x,y) = J(Z,y,X).

A polynomial in several variables is called homoge­

neous of degree r if all of the terms are degree r. For

example, g(x,y) :=x^2 +5xy is homogeneous of degree

2. (The 5xy term is considered to have degree 2, since
   it is the product of two degree-! terms.) In general,
   the k-variable polynomial g(XI ,X 2 , ... ,Xk) is homoge­
   neous of degree r if for all t, we have

g(tx 1 ,tx 2 ,··· ,txk) = t' g(XI ,X 2 ,··· ,Xk)·

Given three variables x,y,z, we define the elementary

symmetric functions

SI :=x+y+z,

S 2 :=xy+yz+zx,

S 3 := xyz.

The elementary symmetric function Sk is symmetric,

homogeneous of degree k, and all its coefficients are

equal to I. Elementary symmetric functions can be

defined for any number of variables. For example, for

four variables x,y,z, w, they are

SI :=x+y+z+w,

S 2 :=xy+xz+xw+yz+yw +zw,

S 3 :=xyz+xyw+xzw+yzw,

S 4 :=xyzw.

(a) Verify that

x^2 + i +z^2 = ( x+y+z)^2 -2(xy+yz+zx)

= si -2S 2 ,

where the Si are the elementary symmetric func­

tions in three variables.

(b) Likewise, express x^3 + y^3 + z^3 as a polynomial

in the elementary symmetric functions.

(c) Do the same for (x+y)(x+z)(y+z).

(d) Do the same for xl + yz4 + zx4 + xz^4 + yx4 +

zl·

(e) Can any symmetric polynomial in three vari­

ables be written as a polynomial in the elemen­

tary symmetric functions?

(f) Can any polynomial (not necessarily symmet­

ric) in three variables be written as a polynomial

in the elementary symmetric functions?

(g) Generalize to more variables. If you are con­

fused, look at the two-variable case (SI := x +

y, S 2 :=xy).

(h) What is the relationship, if any, between cyclic

sums and elementary symmetric functions?

3.1.19 Consider Example 3.1 .6, the Four Bugs prob­

lem. As the bugs travel, they "turn." For example, if

one bug starts out facing due north, but then gradually

comes to face due west, it will have turned 90°. It may

even be that the bugs turn more than 360°. How much

does each bug turn (in degrees) before they crash into

each other?

3.1.20 Consider the following two-player game. Each

player takes turns placing a penny on the surface of a

rectangular table. No penny can touch a penny that is

already on the table. The table starts out with no pen­

nies. The last player who makes a legal move wins.

Does the first player have a winning strategy?

3.1.21 A billiard ball (of infinitesimal diameter)

strikes ray Be at point e, with angle of incidence a

as shown. The billiard ball continues its path, bounc­

ing off line segments AB and Be according to the

rule "angle of incidence equals angle of reflection." If

AB = Be, determine the number of times the ball will

bounce off the two line segments (including the first

bounce, at e). Your answer will be a function of a and

/3.

B c

3.1.22 A projectile is launched from the very center

of the floor of a rectangular room that is 40 feet wide

with a very high ceiling. The projectile hits the wall

at a height exactly 10 feet above the floor, reflects off

this wall (obeying the "angle of incidence equals an­

gle of reflection" rule), hits the opposite wall, and re­

flects again, finally landing back exactly where it was