37.

Let f(x) = x³ + ax² + bx + b. Determine all integer pairs (a, b) for which f(x) is the product of three linear factors with integer coefficients.

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.

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, ¼, i-1. Prove that the number of elements of A_n is å_{k = 0}^¥ kⁿ 2^-(k+1).

40.

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

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 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.)

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.)

37.

First solution. If b = 0, then the polynomial becomes x²(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,

38.

First solution. Suppose that the face S has m vertices A₁, A₂, ¼, 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₁ ¼A_m X A₁ 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₁, X₂, ¼ 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_j-1X_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₁ A₂ ¼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_sA_s-1 ¼A_r+1A_r. If YZ is not an edge of this polygon, but A_rZ 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.

First solution. Let u₀ = 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_n-r such mappings. Since there are ((n) || (r)) possible sets on which a mapping may assume the value 1 r times,

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ⁿ mappings of { 1, 2, ¼, n } into { 1, 2, ¼, k }, of which v_k belong to A_n. The other kⁿ - v_k 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

40.

Let h = 2xy/(x+y), g = Ö[(xy)], a = ¹/₂(x + y) and r = Ö{¹/₂(x² + y²)}.

40.

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

40.

Second solution. [A. Corduneanu] Observe that

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² - 1)]. The equation becomes

41.

First solution. For positive integer n, let x_n be the nth term of the sequence, and let x₀ = 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

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₀ º x₄₂ º x₈₄ º ¼. 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.

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 ~ (¹/₃, [(2a)/3]). Let P ~ (p, q). Then, since P lies on the lines y = ^a/₂(x + 1), q = ^a/₂(p+1). The relation AP ^PC implies that