GENWiki

From: brnstnd@ocf.berkeley.edu (Dan Bernstein) Newsgroups: sci.math Subject: 1992 Putnam problems and unofficial solutions Date: 7 Dec 1992 20:20:44 GMT Message-ID: 1g0bmsINNh22@agate.berkeley.edu Organization: IR Lines: 513

As usual, first come the problems, then the problems with solutions. Send any followup remarks to the USENET newsgroup sci.math.

Problem A1

Prove that f(n) = 1 - n is the only integer-valued function defined on the integers that satisfies the following conditions. (i) f(f(n)) = n, for all integers n; (ii) f(f(n + 2) + 2) = n for all integers n; (iii) f(0) = 1.

Problem A2

Define C(alpha) to be the coefficient of x^1992 in the power series expansion about x = 0 of (1 + x)^alpha. Evaluate

\int_0^1 C(-y-1) ( 1/(y+1) + 1/(y+2) + 1/(y+3) + … + 1/(y+1992) ) dy.

Problem A3

For a given positive integer m, find all triples (n,x,y) of positive integers, with n relatively prime to m, which satisfy (x^2 + y^2)^m = (xy)^n.

Problem A4

Let f be an infinitely differentiable real-valued function defined on the real numbers. If

f(1/n) = n^2/(n^2 + 1), n = 1,2,3,…,

compute the values of the derivatives f^(k)(0), k = 1,2,3,… .

Problem A5

For each positive integer n, let

a_n = { 0 if the number of 1's in the binary representation of n is even,

       1 if the number of 1's in the binary representation of n is odd.

Show that there do not exist positive integers k and m such that

a_{k+j} = a_{k+m+j} = a_{k+2m+j}, for 0 ⇐ j ⇐ m - 1.

Problem A6

Four points are chosen at random on the surface of a sphere. What is the probability that the center of the sphere lies inside the tetrahedron whose vertices are at the four points? (It is understood that each point is independently chosen relative to a uniform distribution on the sphere.)

Problem B1

Let S be a set of n distinct real numbers. Let A_S be the set of numbers that occur as averages of two distinct elements of S. For a given n >= 2, what is the smallest possible number of distinct elements in A_S?

Problem B2

For nonnegative integers n and k, define Q(n,k) to be the coefficient of x^k in the expansion of (1+x+x^2+x^3)^n. Prove that

Q(n,k) = \sum_{j=0}^n {n \choose j} {n \choose k - 2j},

where {a \choose b} is the standard binomial coefficient. (Reminder: For integers a and b with a >= 0, {a \choose b} = a!/b!(a-b)! for 0 ⇐ b ⇐ a, and {a \choose b} = 0 otherwise.)

Problem B3

For any pair (x,y) of real numbers, a sequence (a_n(x,y))_{n>=0} is defined as follows:

a_0(x,y) = x a_{n+1}(x,y) = ( (a_n(x,y))^2 + y^2 ) / 2, for all n >= 0.

Find the area of the region { (x,y) | (a_n(x,y))_{n>=0} converges }.

Problem B4

Let p(x) be a nonzero polynomial of degree less than 1992 having no nonconstant factor in common with x^3 - x. Let

( d^1992 / dx^1992 ) ( p(x) / x^3 - x ) = f(x) / g(x)

for polynomials f(x) and g(x). Find the smallest possible degree of f(x).

Problem B5

Let D_n denote the value of the (n-1) by (n-1) determinant

Is the set {D_n/n!}_{n >= 2} bounded?

Problem B6

Let M be a set of real n by n matrices such that (i) I \in M, where I is the n by n identity matrix; (ii) if A \in M and B \in M, then either AB \in M or -AB \in M, but not both; (iii) if A \in M and B \in M, then either AB = BA or AB = -BA; (iv) if A \in M and A \noteq I, there is at least one B \in M such that

   AB = -BA.

Prove that M contains at most n^2 matrices.

Now the unofficial solutions. Thanks to Noam Elkies for the B6 solution; thanks also to Peter Akemann, Greg John, and Peter Montgomery.

The Putnam exam deserves criticism this year for an exceptional number of typos and poorly worded problems. How can someone taking the Putnam be sure that his solutions will be graded carefully, if the exam itself shows sloppy typography, grammar, and style?

Problem A1

Prove that f(n) = 1 - n is the only integer-valued function defined on the integers that satisfies the following conditions. (i) f(f(n)) = n, for all integers n; (ii) f(f(n + 2) + 2) = n for all integers n; (iii) f(0) = 1.

(The comma in (i) is wrong. Either ``conditions. should be ``conditions: or the semicolons should be periods. Little things…)

Solution: Certainly if f(n) = 1 - n then (i), (ii), and (iii) hold. Conversely, say (i), (ii), and (iii) hold. We show that f(k) = 1 - k and f(1 - k) = k for every k >= 0. For k = 0 and 1 we have f(0) = 1 and f(1) = f(f(0)) = 0. For k >= 2, by induction we have f(k - 2) = 3 - k and f(3 - k) = k - 2. Note that f(n + 2) + 2 = f(f(f(n + 2) + 2)) = f(n). So f(k) = f(k - 2) - 2 = 1 - k and f(1 - k) = f(3 - k) + 2 = k as desired. As k and 1 - k for k >= 1 cover the integers, we are done.

Problem A2

Define C(alpha) to be the coefficient of x^1992 in the power series expansion about x = 0 of (1 + x)^alpha. Evaluate

\int_0^1 C(-y-1) ( 1/(y+1) + 1/(y+2) + 1/(y+3) + … + 1/(y+1992) ) dy.

Solution: C(alpha) is given by the usual binomial coefficient formula {alpha \choose 1992} = \alpha (\alpha - 1) … (\alpha - 1991) / 1992!. Hence C(-y-1) = (-y-1)(-y-2)…(-y-1992)/1992! = (y+1)…(y+1992)/1992!. Set f(y) = (y+1)(y+2)…(y+1992). Now f has logarithmic derivative f'/f = ( 1/(y+1) + 1/(y+2) + … + 1/(y+1992) ). Hence our integral equals \int_0^1 f(y)/1992! f'(y)/f(y) dy = \int_0^1 f'(y) dy/1992! = (f(1) - f(0))/1992! = (1993! - 1992!)/1992! = 1993 - 1 = 1992.

Problem A3

For a given positive integer m, find all triples (n,x,y) of positive integers, with n relatively prime to m, which satisfy (x^2 + y^2)^m = (xy)^n.

Solution: Certainly xy < x^2 + y^2 so m < n. Put n = m + k, k > 0. Let d be the greatest common divisor of x and y. Say x = ds, y = dt. Now d^{2m}(s^2 + t^2)^m = d^{2n}(st)^n, so (s^2 + t^2)^m = d^{2k}(st)^n. If a prime p divides s then p divides d^{2k}(st)^n = (s^2 + t^2)^m, so p must divide t. But s and t are relatively prime. Hence s = 1. Similarly t = 1. So d^{2k} = 2^m. Hence d is a power of 2, say d = 2^j, and m = 2jk. As n = m + k = 2jk + k we see that k is a common factor of m and n. Thus k = 1. So m = 2j, n = 2j + 1, x = y = d = 2^j. If m is odd then there are no solutions; if m is even then the only possible solution is (m + 1,2^{m/2},2^{m/2}). This does satisfy the given conditions.

Problem A4

Let f be an infinitely differentiable real-valued function defined on the real numbers. If

f(1/n) = n^2/(n^2 + 1), n = 1,2,3,…,

compute the values of the derivatives f^(k)(0), k = 1,2,3,… .

(``Let f be a foo. If bar, compute blah. Does this mean that one need only answer the question if ``bar happens to be true? May one choose his favorite f, such as f(x) = x, observe that it does not satisfy ``bar, and [successfully] answer the question without computing anything? ``If …, compute should be ``Assume … . Compute.) Solution: We first observe that the function g(x) = 1/(1 + x^2) satisfies all the known properties of f: it is infinitely differentiable, and g(1/n) = n^2/(n^2 + 1). From the Taylor expansion of g around 0, g(x) = 1 - x^2 + x^4 - x^6 + …, we see that g^(k)(0) is 0 for k odd, (-1)^{k/2}k! for k even. Can f differ from g in its derivatives at 0? The difference h = f - g is an infinitely differentiable function with roots at 1/n for every positive n. We show that any such function has all derivatives 0 at 0. Suppose not. Take the least k >= 0 for which h^(k)(0) is nonzero. Without loss of generality say it is positive. By continuity h^(k) is positive in an open interval U around 0. Let S be the set of positive elements of U. Now h^(k-1) is increasing on S, and by minimality of k we have h^(k-1)(0) = 0, so h^(k-1) is positive on S. Then h^(k-2) is increasing on S, and h^(k-2)(0) = 0, so h^(k-2) is positive on S. In general h^j is positive on S for j down from k to 0 by induction. In particular h is positive on S, but this is impossible, as 1/n is in S for n sufficiently large. Thus f has all the same derivatives as g: f^(k)(0) is 0 for k odd, (-1)^{k/2}k! for k even. Problem A5 For each positive integer n, let a_n = { 0 if the number of 1's in the binary representation of n is even, 1 if the number of 1's in the binary representation of n is odd. Show that there do not exist positive integers k and m such that a_{k+j} = a_{k+m+j} = a_{k+2m+j}, for 0 ⇐ j ⇐ m - 1. (Is every student supposed to know what the writer means by ``the binary representation of n? Anyway, this problem is well known in some circles. I don't think Putnam writers should copy problems.)

Solution: Let us suppose the opposite. Pick m minimal such that, for some k, a_{k+j} = a_{k+m+j} for every 0 ⇐ j ⇐ 2m - 1. The minimality guarantees that m is odd. (Indeed, say m = 2m'. If k = 2k' is even, then put j = 2j' for 0 ⇐ j' ⇐ m - 1 = 2m' - 1. Now a_n = a_{2n} so a_{k'+j'} = a_{k+j} = a_{k+m+j} = a_{k'+m'+j'} as desired. If on the other hand k = 2k' - 1 is odd, then put j = 2j' + 1 for 0 ⇐ j' ⇐ 2m' - 1. Now a_{k'+j'} = a_{k+j} = a_{k+m+j} = a_{k'+m'+j'} as desired.)

We cannot have m = 1. Indeed, if a_k = a_{k+1} = a_{k+2}, then we have a_{2n} = a_{2n+1} for n = k/2 if k is even or n = (k+1)/2 if k is odd. But a_{2n} + a_{2n+1} = 1 always. Hence m is an odd number greater than 1.

Define b_n = (a_n + a_{n-1}) mod 2. For 1 ⇐ j ⇐ 2m - 1 we have b_{k+j} = b_{k+m+j}. This range of j covers at least 5 values; we can certainly choose j so as to make k+j equal to 2 mod 4. Then k+m+j is odd. But b_n is 0 when n is 2 mod 4, and b_n is 1 when n is odd, so we have a contradiction.

Problem A6

Four points are chosen at random on the surface of a sphere. What is the probability that the center of the sphere lies inside the tetrahedron whose vertices are at the four points? (It is understood that each point is independently chosen relative to a uniform distribution on the sphere.)

Solution: Pick three points A, B, C, and consider the spherical triangle T defined by those points. The center of the sphere lies in the convex hull of A, B, C, and another point P if and only if it lies in the convex hull of T and P. This happens if and only if P is antipodal to T. So the desired probability is the expected fraction of the sphere's surface area which is covered by T.

Denote the antipode to a point P by P'. We consider the eight spherical triangles ABC, A'BC, AB'C, A'B'C, ABC', A'BC', AB'C', A'B'C'. Denote these by T_0, T_1, T_2, T_3, T_4, T_5, T_6, T_7; we regard each T_i as a function of the random variables A, B, C. There is an automorphism of our probability space defined by (A,B,C) → (A,B,C'). Hence T_0 and T_4 have the same distribution, and similarly T_1 and T_5, T_2 and T_6, and T_3 and T_7. Of course the same applies to B, so that T_0 and T_2, T_1 and T_3, T_4 and T_6, and T_5 and T_7 all have the same distribution. Finally T_0 and T_1, T_2 and T_3, T_4 and T_5, and T_6 and T_7 all have the same distribution. We conclude that all the T_i have exactly the same distribution. In particular the fractional area A_i of T_i has the same distribution for all i.

On the other hand the total fractional area of all the T_i is exactly 1: the eight triangles cover the sphere exactly once. Hence each T_i has expected fractional area 1/8. In particular, T_0, the probability we wanted, has expected value 1/8.

Note that this proof does not require the full strength of uniform distribution in the usual measure; nor does it require independence between all the variables. It requires only certain automorphisms of the probability space.

Problem B1

Let S be a set of n distinct real numbers. Let A_S be the set of numbers that occur as averages of two distinct elements of S. For a given n >= 2, what is the smallest possible number of distinct elements in A_S?

(``Smallest possible number of distinct elements in A_S? Who talks about ``the number of _distinct_ elements of a set? How about just ``the number of elements? Or ``the size? Aargh. The quantifiers here are completely out of whack: n has to be fixed [not ``given] before anything else, and it's not immediately clear that ``smallest possible refers to ``the minimum over all S. Proposed rewrite: ``Fix n >= 2. For any set S of n real numbers, let A_S be the set of averages of two distinct elements of S. What is the minimum, over all S, of the size of A_S?)

Solution: We put the elements of S in order: s_1 < s_2 < … < s_n. We have s_1 + s_2 < s_1 + s_3 < … < s_1 + s_{n-1} < s_1 + s_n < s_2 + s_n < s_3 + s_n < … < s_{n-1} + s_n. Hence the 2n - 3 averages (s_i + s_j)/2, i < j, with i = 1 or j = n, are all distinct. So A_S has size at least 2n - 3. This is achieved if, for instance, S = {1,2,…,n}.

Problem B2

For nonnegative integers n and k, define Q(n,k) to be the coefficient of x^k in the expansion of (1+x+x^2+x^3)^n. Prove that

Q(n,k) = \sum_{j=0}^n {n \choose j} {n \choose k - 2j},

where {a \choose b} is the standard binomial coefficient. (Reminder: For integers a and b with a >= 0, {a \choose b} = a!/b!(a-b)! for 0 ⇐ b ⇐ a, and {a \choose b} = 0 otherwise.)

Solution: (1+x^2)(1+x) = 1+x+x^2+x^3, so (1+x^2)^n(1+x)^n = (1+x+x^2+x^3)^n, so (\sum {n\choose j} x^{2j}) (\sum {n\choose m} x^m) = \sum Q(n,k)x^k. The coefficient of x^k on the left is the sum of {n\choose j}{n\choose m} over all j,m with m + 2j = k, i.e., \sum_j {n\choose j}{n\choose k-2j}.

Problem B3

For any pair (x,y) of real numbers, a sequence (a_n(x,y))_{n>=0} is defined as follows:

a_0(x,y) = x a_{n+1}(x,y) = ( (a_n(x,y))^2 + y^2 ) / 2, for all n >= 0.

Find the area of the region { (x,y) | (a_n(x,y))_{n>=0} converges }.

(The parentheses in (a_n(x,y))^2 are confusing, as the writer also uses parentheses to denote the entire sequence of a_n.)

Solution: Note that (x,y) and (x,-y) produce the same sequence, and (-x,y) and (x,y) produce the same sequence after the first step. So we will restrict attention to nonnegative x and y and quadruple our final answer.

Fix x and y. Set f(z) = ( z^2 + y^2 ) / 2, so that a_n(x,y) = f(a_{n-1}(x,y)). Now f'(z) = z, so f is increasing on the positive reals. So (a_n(x,y))_n is monotone—either increasing, decreasing, or constant. We consider several (non-exclusive) possibilities.

Case 1. Say y > 1. Then f(z) > (1 + z^2)/2 + (y - 1) >= z + (y - 1), so a_n(x,y) increases by at least y - 1 at each step.

Case 2. Say f(x) < x. Then we have 0 < a_n(x,y) < a_{n-1}(x,y) ⇐ x for every n. (Indeed, for n = 1 we have 0 < f(x) < x. For n >= 2 we have a_{n-1}(x,y) < a_{n-2}(x,y) by induction. So a_n(x,y) < a_{n-1}(x,y), as f is increasing.) As (a_n(x,y))_n is decreasing and bounded below, it converges.

Case 3. Say f(x) > x > 1. Define g(z) = f(z) - z, so that g(x) > 0. We have g'(z) = z - 1, so g is increasing past 1. Now a_n(x,y) >= x + ng(x). (Indeed, for n = 1 we have a_1(x,y) = f(x) = x + g(x). For n >= 2 set a = a_{n-1}(x,y). We have a >= x + (n-1)g(x) > x by induction. So g(a) > g(x), and a_n(x,y) = f(a) = a + g(a) > a + g(x) >= x + ng(x) as desired.) So a_n increases without bound.

Case 4. Say x < 1, y < 1. Then f(x) < f(1) < (1 + 1)/2 = 1. Similarly a_n(x,y) < 1 for every n. As (a_n(x,y))_n is bounded and monotone, it converges.

Let's put this all together. For y > 1 the sequence diverges. For y < 1 and x < 1 the sequence does converge. For y < 1 and x > 1, the sequence converges if f(x) < x, and diverges if f(x) > x. The points we miss in this tally—y = 1, x = 1, f(x) = x—have zero total area.

The condition f(x) < x is equivalent to (x-1)^2 + y^2 < 1, which describes a quarter-circle of radius 1 in the region y > 0, x > 1. Thus the total area for positive x and y is 1 (for the square y < 1, x < 1) plus pi/4 (for the quarter-circle). The final answer is quadruple this, or 4 + pi.

Problem B4

Let p(x) be a nonzero polynomial of degree less than 1992 having no nonconstant factor in common with x^3 - x. Let

( d^1992 / dx^1992 ) ( p(x) / (x^3 - x) ) = f(x) / g(x)

for polynomials f(x) and g(x). Find the smallest possible degree of f(x).

(The second sentence is backwards—``let should be followed immediately by the variable being introduced. Would you say ``Let 2 equal x + y for integers x and y?)

Solution: First divide p(x) by x^3 - x: p(x) = (x^3 - x)q(x) + r(x), with r of degree at most 2. Now f(x)/g(x) = D^1992 (q(x) + r(x)/(x^3-x)) = D^1992 (r(x)/(x^3-x)), as q has degree less than 1992; here we write D for d/dx. We expand r(x)/(x^3-x) in partial fractions as -r(0)/x + r(1)/2(x-1) + r(-1)/2(x+1). Now the 1992nd derivative of this is Cr(0)/x^1993 + Cr(1)/(x-1)^1993 + Cr(-1)/(x+1)^1993 for a certain nonzero constant C which we don't care about. This then equals (Cr(0)(x^2-1)^1993 + Cr(1)(x^2+x)^1993 + Cr(-1)(x^2-x)^1993)/(x^3-x)^1993.

The numerator and denominator here are coprime, for none of x, x-1, x+1 divide the numerator. (If, for instance, x divided the numerator, then r(0) would have to be 0, but then p(x) would have a factor of x in common with x^3-x, contrary to hypothesis.) So f(x) is a multiple of the numerator and g(x) is a multiple of the denominator. Our question is thus ``What is the smallest possible degree of the polynomial P = U(x^2-1)^1993 + V(x^2+x)^1993 + W(x^2-x)^1993, over all U, V, W which can arise as U=Cr(0), V=Cr(1), W=Cr(-1)? P has degree at most 2.1993. Its 2.1993 coefficient is U + V + W. Its 2.1993-1 coefficient is 1993V - 1993W. Its 2.1993-2 coefficient is -1993U + 1993.(1992/2)V + 1993.(1992/2)W. If all three of these are zero then by linear algebra all of U, V, W are zero, which is not possible. Hence P, and thus also f, has degree at least 2.1993-2, or double 1992. This is achieved if, for instance, p(x) = r(x) = 3x^2 - 2, so that r(0)+r(1)+r(-1)=-2+1+1=0 and r(1)=r(-1). (The degree restriction on p in this problem seems somewhat strange, though it simplifies the solution slightly. Noam Elkies notes that the ``nonzero constant C above will be zero—so that f will be 0— if we're working over a field with characteristic dividing 1992!. Should the problem have explicitly identified the ground field as the reals?)

Problem B5

Let D_n denote the value of the (n-1) by (n-1) determinant

Is the set {D_n/n!}_{n >= 2} bounded?

(``The value of the determinant? Why not just ``the determinant? Why talk about ``the set when it's much more common to talk about ``the sequence? And where's the period on the first sentence?)

Solution: No, it is the harmonic series.

We subtract the first row from each of the other rows, to get a matrix 3 1 1 1 … 1, -2 3 0 0 … 0, -2 0 4 0 … 0, …, -2 0 0 0 … n. Then we subtract 1/3 of the new second row from the first, 1/4 of the new third row from the first, and so on, to kill all the 1's along the top. We are left with a triangular matrix, with diagonal X 3 4 … n, where X equals 3 - (-2)/3 - (-2)/4 - … - (-2)/n = 3 + 2/3 + 2/4 + … + 2/n = 2(1 + 1/2 + 1/3 + 1/4 + … + 1/n). Thus the determinant is n! times 1 + 1/2 + 1/3 + … + 1/n. Q. E. D.

Problem B6

Let M be a set of real n by n matrices such that (i) I \in M, where I is the n by n identity matrix; (ii) if A \in M and B \in M, then either AB \in M or -AB \in M, but not both; (iii) if A \in M and B \in M, then either AB = BA or AB = -BA; (iv) if A \in M and A \noteq I, there is at least one B \in M such that

   AB = -BA.

Prove that M contains at most n^2 matrices.

Solution (courtesy Noam Elkies): Fix A in M. By (iii) AB = eBA, where e is either +1 or -1, for any B in M. Then AAB = AeBA = eABA = e^2BAA = BAA. So A^2 commutes with any B in M. Of course the same is true of -A^2. On the other hand by (ii) A^2 or -A^2 is in M. Pick C = A^2 or C = -A^2 so that C is in M.

If C is not I, then by (iv) we can find a B in M such that CB = -BC. But we know CB = BC for any B in M. Thus CB = 0, which is impossible, as by (ii) no two elements of M can multiply to 0.

We conclude that C must be I. In other words, for any A in M, either A^2 or -A^2 must be I.

Now suppose M has more than n^2 matrices. The space of real n by n matrices has dimension n^2, so we can find a nontrivial linear relation \sum_{D in M} x_D D = 0. Pick such a relation with the smallest possible number of nonzero x_D. We will construct a smaller relation, obtaining a contradiction and finishing the proof.

Pick an A with x_A nonzero, and multiply by it: \sum_{D in M} x_D DA = 0. In light of (ii) the matrices DA run over M modulo sign. Hence we have a new relation \sum_{E in M} y_E E = 0. The point of this transformation is that now the coefficient y_I of I is +- x_A, which is nonzero.

Pick any C other than I such that y_C is nonzero. By (iv) pick B in M such that CB = -BC. Multiply \sum_{E in M} y_E E = 0 by B on both the left and the right, and add: \sum_{E in M} y_E (BE + EB) = 0. Now by (iii) we have BE + EB = (1 + e_{BE})BE, where e_{BE} is either +1 or -1. In particular e_{BI} = 1 (clear) and e_{BC} = -1 (by construction of B). So we get \sum_{E in M} y_E (1 + e_{BE}) BE = 0, where at least one term does not disappear and at least one term does disappear. As before the matrices BE run over M modulo sign. So we have a relation with fewer terms as desired.

—Dan Bernstein, brnstnd@ocf.berkeley.edu, 7 December 1992