1997 Putnam problems and unofficial solutions

As usual, first come the problems, then the problems with solutions. Comments and criticism at the end.

Send any followup remarks to the USENET newsgroup sci.math.

Problems

Problem A1

A rectangle, HOMF, has sides HO = 11 and OM = 5. A triangle ABC has H as the intersection of the altitudes, O the center of the circumscribed circle, M the midpoint of BC, and F the foot of the altitude from A. What is the length of BC?

H  O

5

F  11  M

Problem A2

Players 1, 2, 3, …, n are seated around a table and each has a single penny. Player 1 passes a penny to Player 2, who then passes two pennies to Player 3. Player 3 then passes one penny to Player 4, who passes two pennies to Player 5, and so on, players alternately passing one penny or two to the next player who still has some pennies. A player who runs out of pennies drops out of the game and leaves the table. Find an infinite set of numbers n for which some player ends up with all n pennies.

Problem A3

Evaluate

∫_{0}^{∞} (x − \frac{x^{3}}{2} + \frac{x^{5}}{2 · 4} − \frac{x^{7}}{2 · 4 · 6} + ⋯) (1 + \frac{x^{2}}{2^{2}} + \frac{x^{4}}{2^{2} · 4^{2}} + \frac{x^{6}}{2^{2} · 4^{2} · 6^{2}} + ⋯) dx.

Problem A4

Let G be a group with identity e and ϕ : G → G a function such that

ϕ(g_{1})ϕ(g_{2})ϕ(g_{3}) = ϕ(h_{1})ϕ(h_{2})ϕ(h_{3})

whenever g_{1}g_{2}g_{3} = e = h_{1}h_{2}h_{3}. Prove that there exists an element a in G such that ψ(x) = aϕ(x) is a homomorphism (that is, ψ(xy) = ψ(x)ψ(y) for all x and y in G). Problem A5 Let N_{n} denote the number of ordered n-tuples of positive integers (a_{1}, a_{2}, …, a_{n}) such that 1/a_{1} + 1/a_{2} + ⋯ + 1/a_{n} = 1. Determine whether N_{10} is even or odd. Problem A6 For a positive integer n and any real number c, define x_{k} recursively by x_{0} = 0, x_{1} = 1, and for k ≥ 0,

x_{k+2} = \frac{cx_{k+1} − (n − k)x_{k}}{k + 1} .

Fix n and then take c to be the largest value for which x_{n+1} = 0. Find x_{k} in terms of n and k, 1 ≤ k ≤ n. Problem B1 Let {x} denote the distance between the real number x and the nearest integer. For each positive integer n, evaluate

S_{n} = ∑_{m=1}^{6n−1} min (\{\frac{m}{6n}\} , \{\frac{m}{3n}\}) .

(Here, min(a, b) denotes the minimum of a and b.) Problem B2 Let f be a twice-differentiable real-valued function satisfying

f(x) + f′′(x) = −xg(x)f′(x),

where g(x) ≥ 0 for all real x. Prove that |f(x)| is bounded. Problem B3

For each positive integer n write the sum ∑_{m=1}^{n} \frac{1}{m} in the form \frac{p_{n}}{q_{n}} where p_{n} and q_{n} are relatively prime positive integers. Determine all n such that 5 does not divide q_{n}. Problem B4 Let a_{m,n} denote the coefficient of x^{n} in the expansion of (1 + x + x^{2})^{m}. Prove that for all k ≥ 0,

0 ≤ ∑_{i=0}^{⌊2k/3⌋}(−1)^{i}a_{k−i,i} ≤ 1.

Problem B5

Prove that for n ≥ 2,

2^{2^{·^{·^{·^{2}}}}} }^{n} ≡ 2^{2^{·^{·^{·^{2}}}}} }^{n−1} (mod n).

Problem B6

The dissection of the 3-4-5 triangle shown below has diameter 5/2.

{4 [figure] 5 \atop 3}

Find the least diameter of a dissection of this triangle into four parts. (The diameter of a dissection is the least upper bound of the distances between pairs of points belonging to the same part.)

Unofficial solutions

Problem A1

A rectangle, HOMF, has sides HO = 11 and OM = 5. A triangle ABC has H as the intersection of the altitudes, O the center of the circumscribed circle, M the midpoint of BC, and F the foot of the altitude from A. What is the length of BC?

H  O

5

F  11  M

Solution: Put the rectangle into R^{2} with vertices F = (0, 0), M = (11, 0), H = (0, 5), and O = (11, 5).

By hypothesis, both H and F are on the A altitude, and both M and F are on BC, so A is on the y-axis, while B and C are on the x-axis. Say A = (0, a) and B = (11 + t, 0); then C = M − (B − M) = (11 − t, 0).

The squared distance from O to A is 11^{2} + (a − 5)^{2}. The squared distance from O to B is t^{2} + 5^{2}. Hence a^{2} − 10a = t^{2} − 11^{2}.

The altitude from B passes through H, so B − H = (t + 11, −5) is perpendicular to A − C = (t − 11, a). Hence 5a = t^{2} − 11^{2} = a^{2} − 10a; so a = 0, which is absurd, or a = 15, which implies t^{2} = 5 · 15 + 11^{2} = 14^{2}.

Finally the length is 2 |t| = 28.

Problem A2

Players 1, 2, 3, …, n are seated around a table and each has a single penny. Player 1 passes a penny to Player 2, who then passes two pennies to Player 3. Player 3 then passes one penny to Player 4, who passes two pennies to Player 5, and so on, players alternately passing one penny or two to the next player who still has some pennies. A player who runs out of pennies drops out of the game and leaves the table. Find an infinite set of numbers n for which some player ends up with all n pennies.

Solution: Any number n of the form 2^{m} + 2 will work. After 2 steps, there are 2^{m} players; Player 3 has 3 pennies and is about to pass 1; all the other players have 1. By Lemma 1, Player 3 will win, i.e., end up with all n pennies.

Lemma 1: Assume that there are 2^{m} players; that the current player has k pennies and is about to pass 1; and that all other players have j pennies. If k ≥ 2 then the current player will win.

Proof: If m = 0 then there are no other players. Otherwise, after 2^{m}j steps, there are 2^{m−1} players left; the original player has k + j pennies and is about to pass 1; and all other players have 2j pennies. Induct on m.

Problem A3

Evaluate

∫_{0}^{∞} (x − \frac{x^{3}}{2} + \frac{x^{5}}{2 · 4} − \frac{x^{7}}{2 · 4 · 6} + ⋯) (1 + \frac{x^{2}}{2^{2}} + \frac{x^{4}}{2^{2} · 4^{2}} + \frac{x^{6}}{2^{2} · 4^{2} · 6^{2}} + ⋯) dx.

Solution: Substitute u = x^{2}/2:

∫_{0}^{∞} (x − \frac{x^{3}}{2} + \frac{x^{5}}{2 · 4} − \frac{x^{7}}{2 · 4 · 6} + ⋯) (1 + \frac{x^{2}}{2^{2}} + \frac{x^{4}}{2^{2} · 4^{2}} + \frac{x^{6}}{2^{2} · 4^{2} · 6^{2}} + ⋯) dx

= ∫_{0}^{∞} xe^{−x^{2}/2} ∑_{n≥0} \frac{x^{2n}}{n!^{2}4^{n}} dx = ∫_{0}^{∞} e^{−u} ∑_{n≥0} \frac{u^{n}}{n!^{2}2^{n}} du

= ∑_{n≥0} \frac{1}{n!^{2}2^{n}} ∫_{0}^{∞} e^{−u}u^{n} du = ∑_{n≥0} \frac{1}{n!2^{n}} = e^{1/2}.

The interchange of sum and integral is justified since all terms are nonnegative.

Problem A4

Let G be a group with identity e and ϕ : G → G a function such that

ϕ(g_{1})ϕ(g_{2})ϕ(g_{3}) = ϕ(h_{1})ϕ(h_{2})ϕ(h_{3})

whenever g_{1}g_{2}g_{3} = e = h_{1}h_{2}h_{3}. Prove that there exists an element a in G such that ψ(x) = aϕ(x) is a homomorphism (that is, ψ(xy) = ψ(x)ψ(y) for all x and y in G).

Solution: Define b = ϕ(e), a = b^{−1}, and ψ(x) = aϕ(x). I will show that ψ(xy) = ψ(x)ψ(y). Note that ψ(e) = ab = e.

If h_{1}h_{2}h_{3} = e then by hypothesis b^{3} = ϕ(h_{1})ϕ(h_{2})ϕ(h_{3}), i.e., b^{2} = ψ(h_{1})bψ(h_{2})bψ(h_{3}). In particular b^{2} = ψ(e)bψ(y)bψ(y^{−1}) so b = ψ(y)bψ(y^{−1}); b^{2} = ψ(x^{−1})bψ(x)bψ(e) so b^{2} = ψ(x^{−1})bψ(x)ψ(y)bψ(y^{−1}); finally b^{2} = ψ(x^{−1})bψ(xy)bψ(y^{−1}) so ψ(xy) = ψ(x)ψ(y).

Problem A5

Let N_{n} denote the number of ordered n-tuples of positive integers (a_{1}, a_{2}, …, a_{n}) such that 1/a_{1} + 1/a_{2} + ⋯ + 1/a_{n} = 1. Determine whether N_{10} is even or odd.

Solution: For each vector (b_{1}, b_{2}, …, b_{n}) with b_{1} ≤ b_{2} ≤ ⋯ ≤ b_{n} and 1/b_{1} +1/b_{2} +⋯+ 1/b_{n} = 1, enumerate all distinct permutations of (b_{1}, b_{2}, …, b_{n}). This produces each of the problem’s n-tuples exactly once.

I will show that when n = 10 the number of permutations of (b_{1}, b_{2}, …, b_{n}) is odd in exactly 5 cases: (3, 3, 24, …, 24), (4, 4, 16, …, 16), (6, 6, 12, …, 12), (9, …, 9, 18, 18), and (10, 10, 10, …, 10). Therefore N_{10} is odd.

If an integer b appears exactly k times in (b_{1}, b_{2}, …, b_{n}) then the number of permutations is a multiple of \binom{n}{k}. Indeed, there are \binom{n}{k} choices of places to put b; the number of ways to arrange the remaining integers in the remaining n − k positions is independent of this choice.

Now set n = 10 and assume that the number of permutations is odd. Then b appears exactly k times for some k ∈ \{0, 2, 8, 10\}, since \binom{10}{k} is even for k ∈ \{1, 3, 4, 5, 6, 7, 9\}.

Case 1: Some integer b appears 10 times. Then 10/b = 1 so (b_{1}, …, b_{10}) = (10, …, 10).

Case 2: No integer appears 10 times; some integer b appears exactly 8 times. Let c be one of the remaining numbers; then c must appear exactly 2 times, so 8/b + 2/c = 1. If c > 10 and b > 10 then 8/b + 2/c < 10/10, contradiction. Now solve for b when c ∈ {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and for c when b ∈ {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Alternatively observe that if c is odd then c − 2 is coprime to 8c, so b = 8c/(c − 2) is a positive integer only when c = 3; and if c is even then c/2 − 1 is coprime to c/2, so b = 8(c/2)/(c/2 − 1) is a positive integer only when c/2 − 1 divides 8, i.e., when c ∈ {4, 6, 10, 18}. The case c = 10 is excluded since b ≠ c. Hence (c, b) ∈ {(3, 24), (4, 16), (6, 12), (18, 9)}. There are 45 permutations in each case.

Case 3: No integer appears exactly 8 or 10 times. Let b and c be two different integers that appear. Then b and c each appear exactly 2 times. There are \binom{10}{2} choices of places to put b; for each selection there are \binom{8}{2} choices of places to put c; and for each selection there are the same number of ways to arrange the remaining integers in the remaining 6 positions. But \binom{8}{2} is even. Contradiction.

Problem A6

For a positive integer n and any real number c, define x_{k} recursively by x_{0} = 0, x_{1} = 1, and for k ≥ 0,

x_{k+2} = \frac{cx_{k+1} − (n − k)x_{k}}{k + 1} .

Fix n and then take c to be the largest value for which x_{n+1} = 0. Find x_{k} in terms of n and k, 1 ≤ k ≤ n.

Solution: The answer is \binom{n−1}{k−1}.

Define f(t) = ∑_{k≥0} x_{k+1}t^{k}. Then (1 − t^{2})f′(t) = (c − (n − 1)t)f(t) with f(0) = 1. Solve the differential equation: f(t) = (1 + t)^{(n−1+c)/2}(1 − t)^{(n−1−c)/2}.

Evidently f(t) is a polynomial in t of degree n − 1 if n − 1 + c and n − 1 − c are both nonnegative even integers, i.e., if c ∈ {−n + 1, −n + 3, …, n − 3, n − 1}. Thus x_{n+1} = 0 for each of these n values of c. But x_{n+1} is a polynomial in c of degree n; so it has at most n roots. Conclusion: n − 1 is the largest value of c for which x_{n+1} = 0.

Finally f(t) = (1 + t)^{n−1} when c = n − 1.

Problem B1

Let {x} denote the distance between the real number x and the nearest integer. For each positive integer n, evaluate

S_{n} = ∑_{m=1}^{6n−1} min (\{\frac{m}{6n}\} , \{\frac{m}{3n}\}) .

(Here, min(a, b) denotes the minimum of a and b.)

Solution: The answer is n.

Abbreviate m/6n as t. Write c_{m} = min({t} , {2t}). If 0 ≤ m < 2n then {t} = t ≤ min(2t, 1 − 2t) = {2t} so c_{m} = m/6n. If 2n ≤ m < 3n then {2t} = 1 − 2t ≤ t = {t} so c_{m} = 1 − m/3n. If 3n ≤ m < 4n then {2t} = 2t − 1 < 1 − t = {t} so c_{m} = m/3n − 1. If 4n ≤ m < 6n then {t} = 1 − t ≤ min(2t − 1, 2 − 2t) = {2t} so c_{m} = 1 − m/6n.

Thus c_{m} + c_{m+4n} = m/6n + 1 − (m + 4n)/6n = 1/3 for 0 ≤ m < 2n and c_{m} + c_{m+n} = 1 − m/3n + (m + n)/3n − 1 = 1/3 for 2n ≤ m < 3n. Add:

∑_{0≤m<6n} c_{m} = ∑_{0≤m<2n}(c_{m} + c_{m+4n}) + ∑_{2n≤m<3n}(c_{m} + c_{m+n}) = 2n\frac{1}{3} + n\frac{1}{3} = n.

Finally note that c_{0} = 0. Problem B2 Let f be a twice-differentiable real-valued function satisfying

f(x) + f′′(x) = −xg(x)f′(x),

where g(x) ≥ 0 for all real x. Prove that |f(x)| is bounded. Solution: The derivative of f(x)^{2} + f′(x)^{2} is −2xg(x)f′(x)^{2}, which is nonnegative for x ≤ 0 and nonpositive for x ≥ 0. Thus f(x)^{2} + f′(x)^{2} ≤ f(0)^{2} + f′(0)^{2}. Problem B3

For each positive integer n write the sum ∑_{m=1}^{n} \frac{1}{m} in the form \frac{p_{n}}{q_{n}} where p_{n} and q_{n} are relatively prime positive integers. Determine all n such that 5 does not divide q_{n}. Solution: {1, 2, 3, 4, 20, 21, 22, 23, 24, 100, 101, 102, 103, 104, 120, 121, 122, 123, 124}. To simplify the calculations I will work with the 5-adic integers Z_{5}. Recall that a rational number is in Z_{5} iff 5 does not divide its denominator; a rational number is in Z_{5}^{∗} iff 5 divides neither its numerator nor its denominator. Define h_{n} = ∑_{1≤m≤n} 1/m and g_{n} = h_{n} − (1/5)h_{⌊n/5⌋}. By direct calculation h_{1}, h_{2}, h_{3} ∈ Z_{5}^{∗} but h_{4} ∈ 75 + 125Z_{5}. If 5 ≤ n < 20 then g_{n} ∈ Z_{5} by Lemma 3, and h_{⌊n/5⌋} ∈ Z_{5}^{∗}, so h_{n} ∈ 5^{−1}Z_{5}^{∗}. Consequently h_{n} ∉ Z_{5}. If n ∈ {20, 24} then g_{n} ∈ 25Z_{5} by Lemma 1, and h_{⌊n/5⌋} ∈ 75+125Z_{5}, so h_{n} ∈ 15+25Z_{5}. If n ∈ {21, 22, 23} then g_{n} ∈ Z_{5}^{∗} by Lemma 2, and h_{⌊n/5⌋} ∈ 25Z_{5}, so h_{n} ∈ Z_{5}^{∗}. If 25 ≤ n < 100 or 105 ≤ n < 120 then g_{n} ∈ Z_{5} by Lemma 3, and h_{⌊n/5⌋} ∉ 5Z_{5}, so h_{n} ∉ Z_{5}. If n ∈ {100, 120} then g_{n} ∈ 25Z_{5} by Lemma 1, and h_{⌊n/5⌋} ∈ 15 + 25Z_{5}, so h_{n} ∈ 3 + 5Z_{5}. Furthermore h_{n+1} = h_{n} + 1/(n + 1) ∈ 4 + 5Z_{5}, h_{n+2} = h_{n+1} + 1/(n + 2) ∈ 2 + 5Z_{5}, h_{n+3} = h_{n+2} + 1/(n + 3) ∈ 4 + 5Z_{5}, and h_{n+4} = h_{n+3} + 1/(n + 4) ∈ 3 + 5Z_{5}. Therefore h_{n} ∈ Z_{5}^{∗} for 100 ≤ n < 105 and 120 ≤ n < 125.

If n ≥ 125 then g_{n} ∈ Z_{5} by Lemma 3, and h_{⌊n/5⌋} ∉ 5Z_{5}, so h_{n} ∉ Z_{5}. Lemma 1: If n mod 5 ∈ {0, 4} then g_{n} ∈ 25Z_{5}. Proof: If n = 5k + 4 or n = 5k + 5 then

g_{n} − g_{5k} = \frac{1}{5k + 1} + \frac{1}{5k + 2} + \frac{1}{5k + 3} + \frac{1}{5k + 4} = 50\frac{10k^{3} + 15k^{2} + 7k + 1}{(5k + 1)(5k + 2)(5k + 3)(5k + 4)}.

Induct on n, starting from g_{0} = 0 ∈ 25Z_{5}. Lemma 2: If n mod 5 ∈ {1, 2, 3} then g_{n} ∈ Z_{5}^{∗}. Proof: g_{5k+1} = g_{5k} +1/(5k+1) ∈ 1+5Z_{5}, g_{5k+2} = g_{5k+1} + 1/(5k + 2) ∈ 4 + 5Z_{5}, and g_{5k+3} = g_{5k+2} + 1/(5k + 3) ∈ 1 + 5Z_{5}. Lemma 3: g_{n} ∈ Z_{5}. Proof: Lemma 1 and Lemma 2. Problem B4 Let a_{m,n} denote the coefficient of x^{n} in the expansion of (1 + x + x^{2})^{m}. Prove that for all k ≥ 0,

0 ≤ ∑_{i=0}^{⌊2k/3⌋}(−1)^{i}a_{k−i,i} ≤ 1.

Solution: Define f_{k} = ∑_{0≤m≤k}(−1)^{k−m}a_{m,k−m}. If m < k/3 then (1 + x + x^{2})^{m} has degree 2m < k − m so a_{m,k−m} = 0. Thus

f_{k} = ∑_{k−⌊2k/3⌋≤m≤k}(−1)^{k−m}a_{m,k−m} = ∑_{0≤i≤⌊2k/3⌋}(−1)^{i}a_{k−i,i}.

The problem is to prove that f_{k} ∈ {0, 1}. Consider the power series

∑_{k≥0} f_{k}x^{k} = ∑_{k≥0} ∑_{0≤m≤k}(−1)^{k−m}a_{m,k−m}x^{k} = ∑_{m≥0} x^{m} ∑_{k≥m}(−1)^{k−m}a_{m,k−m}x^{k−m}

= ∑_{m≥0} x^{m} ∑_{n≥0}(−1)^{n}a_{m,n}x^{n} = ∑_{m≥0} x^{m}(1 − x + x^{2})^{m} = \frac{1}{1 − x(1 − x + x^{2})}

= \frac{1 + x}{1 − x^{4}} = (1 + x)(1 + x^{4} + x^{8} + x^{12} + ⋯)

= 1 + x + x^{4} + x^{5} + x^{8} + x^{9} + x^{12} + x^{13} + · · · .

Visibly each coefficient is 0 or 1. Problem B5 Prove that for n ≥ 2,

2^{2^{·^{·^{·^{2}}}}} }^{n} ≡ 2^{2^{·^{·^{·^{2}}}}} }^{n−1} (mod n).

Solution: Write f_{0}(b) = b, f_{k+1}(b) = 2^{f_{k}(b)}. The problem is to show that f_{n−1}(2) ≡ f_{n−1}(1) (mod n).

Theorem: f_{k}(x) ≡ f_{k}(1) (mod n) if x ≥ 1, n ≥ 1, and k ≥ n − 1.

Proof: Induct on n. If n = 1 then f_{k}(x) ≡ f_{k}(1) (mod 1) as claimed. Otherwise write n = 2^{t}u with u odd.

By induction, f_{k−1}(x) ≡ f_{k−1}(1) (mod φ(u)), since k − 1 ≥ n − 2 ≥ φ(u) − 1. By Euler’s theorem, 2^{φ(u)} ≡ 1 (mod u), so f_{k}(x) ≡ f_{k}(1) (mod u).

Furthermore, 2^{b} ≥ b + 1 for all positive integers b, so f_{k}(b) ≥ b + k. In particular f_{k}(x) ≥ x + k ≥ 1 + (n − 1) = n ≥ 2^{t}. Thus f_{k}(x), being a power of 2 at least as large as 2^{t}, is a multiple of 2^{t}. In particular f_{k}(1) is a multiple of 2^{t}. Thus f_{k}(x) ≡ f_{k}(1) (mod 2^{t}).

Since f_{k}(x) − f_{k}(1) is divisible by both u and 2^{t} it is divisible by n.

Problem B6

The dissection of the 3-4-5 triangle shown below has diameter 5/2.

{4 [figure] 5 \atop 3}

Find the least diameter of a dissection of this triangle into four parts. (The diameter of a dissection is the least upper bound of the distances between pairs of points belonging to the same part.)

Solution: The answer is 25/13.

Put the triangle into R^{2} with vertices A = (0, 0), B = (3, 0), and C = (0, 4). Also define D = (0, 1), E = (0, 27/13), F = (15/13, 32/13), G = (24/13, 20/13), H = (41/26, 1), and M = (14/13, 0).

Every dissection must have diameter at least 25/13. Indeed, at least two of the points A, B, C, E, G must be in the same part; but the distances between those points are all 25/13 or larger.

Now dissect the triangle into the polygons ADHM, BMG, CF E, and DEF GH. Each of these polygons has diameter 25/13 or smaller, by a tedious computation, so this dissection has diameter 25/13.

Comments

In B6, what is a “dissection”? Are the parts required to be simply connected sets with rectifiable edges? Do the edges have to be line segments? Do the ends of the line segments have to be on the edges of the triangle? The first time this problem appeared on the Putnam (1958.B3) it was stated clearly enough; the second time (1994.A3) it did a poor job of describing the set being colored; this time it doesn’t even say what types of partitions are allowed. Is the 1998 Putnam exam going to ask for the “biggest width” of “chunks” obtained by “slicing a knife” through “a figure similar to the one displayed”?

A2 should have included some examples of the game, perhaps n = 6 and n = 7. A5 should have omitted n: “Let N be the number of vectors of positive integers (a_{1}, a_{2}, …, a_{10}) such that 1/a_{1} + 1/a_{2} + ⋯ + 1/a_{10} = 1. Is N even?” A6 should have explicitly stated the dependence on c: “Fix a positive integer n. Define polynomials f_{k}(x) recursively by f_{0}(x) = 0, f_{1}(x) = 1, and f_{k+2}(x) = (xf_{k+1}(x) − (n − k)f_{k}(x))/(k + 1) for k ≥ 0. Find the largest real number r such that f_{n+1}(r) = 0.”

I wonder how A5 will be graded. Is a contestant permitted to use well-known facts about multisets and multinomial coefficients?

B5 is an old problem.

—Daniel J. Bernstein, djb@cr.yp.to, 7 December 1997