Problem Set 7
 37.

Let f(x) = x^{3} + ax^{2} + bx + b. Determine all integer
pairs (a, b) for which f(x) is the product of three linear
factors with integer coefficients.
View solution
 38.

Assume that a face S of a convex polyhedron P
has a common edge with every other face of P. Show that there
exists a simple (nonintersecting) closed (not necessarily planar)
polygon that consists of edges of P and passes through all the
vertices.
View solution
 39.

Let A_{n} be the set of mappings f : { 1, 2, 3, ¼, n } ® { 1, 2, 3, ¼, n } such that, if
f(k) = i for some i, then f also assumes all the values
1, 2, ¼, i1. Prove that the number of elements of
A_{n} is å_{k = 0}^{¥} k^{n} 2^{(k+1)}.
View solution
 40.

Let x, y be positive real numbers.
Find all solutions of the equation

2xy x + y

+ 
æ ú
Ö


= 
 __ Öxy

+ 
x+y 2

. 

(Note: This is Problem 2268 in CM+MM, October, 1997.)
View solution
 41.

Consider the sequence of positive integers { 1, 12, 123,1234, 12345, ¼} where the next term is constructed by
lengthening the previous term at the righthand end by appending the
next positive integer. Note that this next integer occupies only
one place, with ``carrying''occurring as in addition. Thus, the ninth
and tenth terms of the sequence are 123456789 and 1234567900
respectively. Determine which terms of the sequence are divisible by
7. (Note: This is Problem 2273 in CM+MM,
October, 1997.)
View solution
 42.

ABC is an isosceles triangle with AB = AC. Let D be
the point on the side AC for which CD = 2AD. Let P be the point
on the segment BD such that ÐAPC = 90^{°}. Prove that
ÐABP = ÐPCB. (Note: This is Problem 2254 in
CM+MM, September, 1997.)
View solution
Solutions to Problem Set 7
37.
 37.

First solution. If b = 0, then the polynomial
becomes x^{2}(x + a), which satisfies the condition for all values of
a. This covers the situation for which x is a factor of the
polynomial. Since the leading coefficient of f(x) is 1, the same
must be true (up to sign) of its factors. Assume that
f(x) = (x + u)(x + v)(x + w) for integers u, v and
w with uvw ¹ 0. Since
uvw = uv + vw + wu = b,
It is clearly not possible for all of u, v and w to be negative.
Nor can it occur that two of them, say v and w can be negative,
for then the left side would be less than 1/u £ 1.
Suppose that u and v are positive, while w is negative.
One possibility is that u = 1 and v = w
in which case f(x) = (x + 1)(x^{2}  v^{2}) = x^{3} + x^{2}  v^{2}x  v^{2}. If neither u nor
v is equal to 1, then 1/u + 1/v + 1/w < 1/u + 1/v £ 1,
and this case is not possible. Finally, suppose that u, v and
w are all positive, with u £ v £ w. Then 1 £ 3/u,
so that u £ 3. A little trial and error leads to the
possibilities (u, v, w) = (3, 3, 3), (2, 4, 4) and (2, 3, 6).
Thus the possibilities for (a, b) are (u, 0), (1, v^{2}),
(9, 27), (10, 32) and (11, 36). Indeed, x^{3} + 9x^{2} + 27x + 27 = (x+3)^{3}, x^{3} + 10x^{2} + 32x + 32 = (x + 2)(x + 4)^{2} and
x^{3} + 11x^{2} + 36x + 36 = (x + 2)(x + 3)(x + 6).
38.
 38.

First solution. Suppose that the face S has
m vertices A_{1}, A_{2}, ¼, A_{m} listed in order, and
that there are n vertices of P not contained in S.
We prove the result by induction on n. If n = 1, then every
face abutting S is a triangle. Let X be the vertex off S;
then A_{1} ¼A_{m} X A_{1} is a polygonal path of the desired
type. Suppose that the result holds for any number of vertices
m of S and for n vertices off S where 1 £ n £ k.
Consider the case n = k + 1.


Consider the graph G of all vertices of P and
those edges of P not bounding S. Since there are no
faces bounded solely by these edges, the graph must be a tree
(i.e., it contains no loops and there is a unique path joining
any pair of points). We show that there is at least one vertex
X not in S for which every edge but one must connect X to a
vertex of S. Suppose otherwise. Then, let us start with such a
vertex X and form a sequence X_{1}, X_{2}, ¼ of vertices not in
S such that X_{i} X_{i+1} are edges of P. Since the number
of vertices off S is finite, there must be i < j for which
X_{i} = X_{j} so that X_{i} X_{i+1} ¼X_{j1}X_{j} is a loop in G.
But this contradicts the fact that G is a tree.


Hence there is a vertex X with at most one adjacent edge not
connecting it to S. If there were no such edge, then X would be
the only vertex not in S, contradicting k + 1 ³ 2.
Hence there is a vertex Y not in S such that XY is an edge of
P. We may assume that Y is further from the plane of
S than S. (If not, suppose that S is in the plane z = 0
and that P lies in the quadrant z > 0, y > 0 with Y
further than X from the plane y = 0. We can transform P
by a mapping of the type (x, y, z) ® (x, y, z + ly)
for suitable positive l. This will not alter the configuration
of vertices and edges.) Extend YX to a point Z in the plane of S.
Let Q be the convex hull of (smallest closed convex set
containing) Z and P. This will have a side T containing
S of the form A_{1} A_{2} ¼A_{r} Z A_{s} ¼A_{m} where r < s.
The triangles XZA_{r} and XZA_{s} will be coplanar with faces of
P, and the convex hull will have at most k vertices
not on T. Every face of Q will abut T. By the induction
hypothesis, we can construct a polygon containing each vertex of
Q. If an edge of this polygon is YZ and so includes X,
and if one edge is say ZA_{r}, then we can replace these two edges
by YXA_{s}A_{s1} ¼A_{r+1}A_{r}. If YZ is not an edge of this
polygon, but A_{r}Z and ZA_{s} are, then we can replace these edges
by A_{r} X A_{r+1} ¼A_{s}. In both cases, we obtain a polygon of
the required type for P.
39.
 39.

First solution. Let u_{0} = 1 and,
for n ³ 1, let u_{n} be the
number of elements in A_{n}. Let 1 £ r £ n. Consider the set
of mappings in A_{n} for which the value 1 is assumed exactly r
times. Then 1 £ r £ n. Then each such mapping takes a set
of n  r points onto a set of the form { 2, 3, ¼, s }
where s  1 £ n  r £ n  1. Hence, there are u_{nr}
such mappings. Since there are ((n)  (r)) possible sets
on which a mapping may assume the value 1 r times,
u_{n} = 
n å
r = 1


æ ç
è

n
r

ö ÷
ø

u_{nr} = 
n1 å
r = 0


æ ç
è

n
r

ö ÷
ø

u_{r} . 

Now u_{0} = 1 = å_{k = 0}^{¥}1/2^{k+1}. Assume, as an induction
hypothesis, that u_{r} = å_{k = 0}^{¥} k^{r}/2^{k+1}. Then


= 
n1 å
r = 0


æ ç
è

n
r

ö ÷
ø

u_{r} = 
n1 å
r = 0


æ ç
è

n
r

ö ÷
ø


¥ å
k = 0


k^{r} 2^{k+1}


 
= 
¥ å
k = 0


1 2^{k+1}


n1 å
r = 0


æ ç
è

n
r

ö ÷
ø

k^{r} = 
¥ å
k = 0


1 2^{k+1}

[(1 + k)^{n}  k^{n}] 
 
= 
¥ å
k = 0


(1 + k)^{n} 2^{k+1}

 
¥ å
k = 0


k^{n} 2^{k+1}

= 
¥ å
k = 1


k^{n} 2^{k}

 
¥ å
k = 1


k^{n} 2^{k+1}


 

 

and the result follows. (The interchange of the order of summation
and rearrangement of terms in the infinite sum can be justified by
the absolute convergence of the series.)
 39.

Second solution. For 1 £ i, let v_{i} be the
number of mappings of { 1, 2, ¼, n } onto a set of
exactly i elements. Observe that v_{i} = 0 when i ³ n+1.
There are k^{n} mappings of { 1, 2, ¼, n } into
{ 1, 2, ¼, k }, of which v_{k} belong to A_{n}. The
other k^{n}  v_{k} mappings will leave out i numbers in the range
for some 1 £ i £ k1, and the i numbers not found can
be selected in ((k)  (i)) ways. Thus
k^{n} = 
k å
i = 1


æ ç
è

k
i

ö ÷
ø

v_{i} . 

Hence


= 
¥ å
k = 0


k å
i = 1


2^{k+1}

= 
¥ å
k = 0


n å
i = 1


2^{k+1}


 
= 
n å
i = 1


æ ç
è


¥ å
k = 0


2^{k+1}


ö ÷
ø

v_{i} = 
n å
i = 1


æ ç
è


¥ å
k = i


2^{k+1}


ö ÷
ø

v_{i} . 

 

We evaluate the inner sum. Fix the positive integer i. Suppose that
we flip a fair coin an indefinite number of times, and consider the
event that the (i + 1)th head occurs on the (k+1)th toss.
Then the previous i heads could have occurred in ((k)  (i))
posible positions, so that the probability of the event is
((k)  (i))2^{(k+1)}. Since the (i + 1)th head must occur
on some toss with probability 1,
å_{k = i}^{¥} ((k)  (i)) 2^{(k+1)} = 1. Hence

¥ å
k = 0


k^{n} 2^{k+1}

= 
n å
i = 1

v_{i} = #A_{n} . 

40.
 40.

Let h = 2xy/(x+y), g = Ö[(xy)], a = ^{1}/_{2}(x + y)
and r = Ö{^{1}/_{2}(x^{2} + y^{2})}.
 40.

First solution. It is straightforward
to check that 2a^{2} = r^{2} + g^{2} and that g^{2} = ah. Suppose that
h + r = a + g. Then


 
Þ 2a^{2}  g^{2} = r^{2} = a^{2} + g^{2} + h^{2}  2ah  2gh + 2ag 
 
Þ (a+h)(a  h) = a^{2}  h^{2} = 2(g^{2}  ah) + 2g(a  h) = 0 + 2g(a  h) 
 

 

In the latter case, g = ^{1}/_{2}(a + h) = Ö[(ah)], so both
possibilities entail a = h. But equality of the arithmetic and
harmonic means occurs if and only if x = y.
 40.

Second solution. [A. Corduneanu]
Observe that
r^{2}  g^{2} = 
1 2

(x  y)^{2} = (x + y)(a  h) = 2a(a  h) . 

Since

r^{2}  g^{2} r + g

= r  g = a  h , 

it follows that
However, it can be checked that, in general,
so that a is at once the arithmetic mean and the rootmeansquare
of r and g. But this can occur if and only if r = g = a
if and only if x = y.
 40.

Third solution. [R. O'Donnell] Because of the
homogeneity of the given equation, we can assume without loss of
generality that g = 1 so that y = 1/x. Then h = 1/a and
r = Ö[(2a^{2}  1)]. The equation becomes
or

 ______ Ö2a^{2}  1

= 1 + a  
1 a

. 

Squaring and manipulating leads to
0 = a^{4}  2a^{3} + 2a  1 = (a  1)^{3}(a + 1) 

whence a = 1 = g and so x = y = 1. The main result follows from
this.
41.
 41.

First solution. For positive integer n, let
x_{n} be the nth term of the sequence, and let x_{0} = 0.
Then, for n ³ 0, x_{n+1} = 10x_{n} + (n+1) so that
x_{n+1} º 3x_{n} + (n+1) (mod 7). Suppose that m is a
nonnegative integer and that x_{7m} = a. Then

x_{7m+1} º 3a+1 
x_{7m+2} º 2a+5

x_{7m+3} º 6a+4 
x_{7m+4} º 4a+2 

x_{7m+5} º 5a+4 
x_{7m+6} º a+4

x_{7m+7} º 3a+5 

In particular, we find that, modulo 7, { x_{7m} } is
periodic with the values { 0, 5, 6, 2, 4, 3 } repeated,
so that 0 º x_{0} º x_{42} º x_{84} º ¼.
Hence, modulo 7, x_{7m+1} º 0 iff a º 2,
x_{7m+2} º 0 iff a º 1, x_{7m+3} º 0 iff
a º 4, x_{7m+4} º 0 iff a º 3,
x_{7m+5} º 0 iff a º 2 and x_{7m+6} º 0
iff a º 3. Putting this all together, we find that
x_{n} º 0 (mod 7) if and only if n º 0, 22, 26, 31, 39,41 (mod 42).
42.
 42.

First solution. Produce BA to E so that
BA = AE and join EC. Then D is the centroid of
DBEC and BD produced meets EC at its midpoint
F. Since AE = AC, DCAE is isosceles and so
AF ^EC. Also, since A and F are midpoints of their
respective segments, AF  BC and so ÐAFB = ÐDBC. Because ÐAFC and
ÐAPC are both right, APCF is concyclic so that
ÐAFP = ÐACP.


Hence ÐABP = ÐABC  ÐDBC = ÐABC  ÐAFB = ÐACB  ÐACP = ÐPCB.
 42.

Second solution. Assign coordinates:
A ~ (0, a), B ~ (1, 0), C ~ (1, 0). Then
D ~ (^{1}/_{3}, [(2a)/3]). Let P ~ (p, q).
Then, since P lies on the lines y = ^{a}/_{2}(x + 1),
q = ^{a}/_{2}(p+1). The relation AP ^PC implies that
1 = 
æ ç
è


qa p


ö ÷
ø


æ ç
è


q p1


ö ÷
ø

= 
é ê
ë


a(p1) 2p


ù ú
û


é ê
ë


a(p+1) 2(p1)


ù ú
û

= 
a^{2} (p + 1) 4p

= 
aq 2p



whence p = a^{2}/(a^{2} + 4) and q = 2a/(a^{2} + 4). Now
tanÐABP = 
a  (a/2) 1 + (a^{2}/2)

= 
a 2 + a^{2}



while
tanÐPCB = 
q p1

= 
2a a^{2}  (a^{2} + 4)

= 
a a^{2} + 2

= tanÐABP . 

The result follows.