Rechercher
Problem Set 7

37.
Let f(x) = x3 + ax2 + 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 An 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, ¼, i-1. Prove that the number of elements of An is åk = 0¥ kn 2-(k+1).
View solution
40.
Let x, y be positive real numbers. Find all solutions of the equation
2xy
x + y
+   æ
ú
Ö

 x2 + y22

=   __
Öxy

+ x+y
2
.
(Note: This is Problem 2268 in CM+MM, October, 1997.)

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 right-hand 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 x2(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,
 1u + 1v + 1w = 1 .
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)(x2 - v2) = x3 + x2 - v2x - v2. 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, -v2), (9, 27), (10, 32) and (11, 36). Indeed, x3 + 9x2 + 27x + 27 = (x+3)3, x3 + 10x2 + 32x + 32 = (x + 2)(x + 4)2 and x3 + 11x2 + 36x + 36 = (x + 2)(x + 3)(x + 6).

38.

38.
First solution. Suppose that the face S has m vertices A1, A2, ¼, Am 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 A1 ¼Am X A1 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 X1, X2, ¼ of vertices not in S such that Xi Xi+1 are edges of P. Since the number of vertices off S is finite, there must be i < j for which Xi = Xj so that Xi Xi+1 ¼Xj-1Xj 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 A1 A2 ¼Ar Z As ¼Am where r < s. The triangles XZAr and XZAs 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 ZAr, then we can replace these two edges by YXAsAs-1 ¼Ar+1Ar. If YZ is not an edge of this polygon, but ArZ and ZAs are, then we can replace these edges by Ar X Ar+1 ¼As. In both cases, we obtain a polygon of the required type for P.

39.

39.
First solution. Let u0 = 1 and, for n ³ 1, let un be the number of elements in An. Let 1 £ r £ n. Consider the set of mappings in An 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 un-r such mappings. Since there are ((n) || (r)) possible sets on which a mapping may assume the value 1 r times,
 un = n å r = 1 æç è n r ö÷ ø un-r = n-1 å r = 0 æç è n r ö÷ ø ur .
Now u0 = 1 = åk = 0¥1/2k+1. Assume, as an induction hypothesis, that ur = åk = 0¥ kr/2k+1. Then
 un
 = n-1 å r = 0 æç è n r ö÷ ø ur = n-1 å r = 0 æç è n r ö÷ ø ¥ å k = 0 kr2k+1
 = ¥ å k = 0 12k+1 n-1 å r = 0 æç è n r ö÷ ø kr = ¥ å k = 0 12k+1 [(1 + k)n - kn]
 = ¥ å k = 0 (1 + k)n2k+1 - ¥ å k = 0 kn2k+1 = ¥ å k = 1 kn2k - ¥ å k = 1 kn2k+1
 = ¥ å k = 1 kn2k+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 vi be the number of mappings of { 1, 2, ¼, n } onto a set of exactly i elements. Observe that vi = 0 when i ³ n+1. There are kn mappings of { 1, 2, ¼, n } into { 1, 2, ¼, k }, of which vk belong to An. The other kn - vk mappings will leave out i numbers in the range for some 1 £ i £ k-1, and the i numbers not found can be selected in ((k) || (i)) ways. Thus
 kn = k å i = 1 æç è k i ö÷ ø vi   .
Hence
 ¥ å k = 0 kn2k+1
= ¥
å
k = 0
k
å
i = 1
 æç è k i ö÷ ø vi

2k+1
= ¥
å
k = 0
n
å
i = 1
 æç è k i ö÷ ø vi

2k+1
= n
å
i = 1
æ
ç
è
¥
å
k = 0
 æç è k i ö÷ ø

2k+1
ö
÷
ø
vi = n
å
i = 1
æ
ç
è
¥
å
k = i
 æç è k i ö÷ ø

2k+1
ö
÷
ø
vi  .
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 kn2k+1 = n å i = 1 vi = #An .

40.

40.
Let h = 2xy/(x+y), g = Ö[(xy)], a = 1/2(x + y) and r = Ö{1/2(x2 + y2)}.
40.
First solution. It is straightforward to check that 2a2 = r2 + g2 and that g2 = ah. Suppose that h + r = a + g. Then
 r
 = a + g - h
 Þ 2a2 - g2 = r2 = a2 + g2 + h2 - 2ah - 2gh + 2ag
 Þ (a+h)(a - h) = a2 - h2 = 2(g2 - ah) + 2g(a - h) = 0 + 2g(a - h)
 Þ a = h    or    a + h = 2g   .
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
 r2 - g2 = 12 (x - y)2 = (x + y)(a - h) = 2a(a - h) .
Since
 r2 - g2r + g = r - g = a - h ,
it follows that
 a = 12 (r + g) .
However, it can be checked that, in general,
a =   æ
ú
Ö

 r2 + g22

so that a is at once the arithmetic mean and the root-mean-square 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 = Ö[(2a2 - 1)]. The equation becomes
 r + 1a = a + 1
or
 ______Ö2a2 - 1 = 1 + a - 1a .
 0 = a4 - 2a3 + 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 xn be the nth term of the sequence, and let x0 = 0. Then, for n ³ 0, xn+1 = 10xn + (n+1) so that xn+1 º 3xn + (n+1) (mod 7). Suppose that m is a nonnegative integer and that x7m = a. Then
 x7m+1 º 3a+1 x7m+2 º 2a+5 x7m+3 º 6a+4 x7m+4 º 4a+2
 x7m+5 º 5a+4 x7m+6 º a+4 x7m+7 º 3a+5

In particular, we find that, modulo 7, { x7m } is periodic with the values { 0, 5, 6, 2, 4, 3 } repeated, so that 0 º x0 º x42 º x84 º ¼. Hence, modulo 7, x7m+1 º 0 iff a º 2, x7m+2 º 0 iff a º 1, x7m+3 º 0 iff a º 4, x7m+4 º 0 iff a º 3, x7m+5 º 0 iff a º 2 and x7m+6 º 0 iff a º 3. Putting this all together, we find that xn º 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 = æç è q-ap ö÷ ø æç è qp-1 ö÷ ø = éê ë a(p-1)2p ùú û éê ë a(p+1)2(p-1) ùú û = a2 (p + 1)4p = aq2p
whence p = -a2/(a2 + 4) and q = 2a/(a2 + 4). Now
 tanÐABP = a - (a/2)1 + (a2/2) = a2 + a2
while
 tanÐPCB = -qp-1 = -2a-a2 - (a2 + 4) = aa2 + 2 = tanÐABP  .
The result follows.