Putnam Mathematical Competition, 1 December 2001

Problem A1 Consider a set S and a binary operation ∗ on S (that is, for each a, b in S, a ∗ b is in S). Assume that (a ∗ b) ∗ a = b for all a, b in S. Prove that a ∗ (b ∗ a) = b for all a, b in S. Problem A2 You have coins C_{1}, C_{2}, …, C_{n}. For each k, coin C_{k} is biased so that, when tossed, it has probability \frac{1}{2k + 1} of falling heads. If the n coins are tossed, what is the probability that the number of heads is odd? Express the answer as a rational function of n. Problem A3 For each integer m, consider the polynomial

P_{m}(x) = x^{4} − (2m + 4)x^{2} + (m − 2)^{2}.

For what values of m is P_{m}(x) the product of two nonconstant polynomials with integer coefficients? Problem A4 Triangle ABC has area 1. Points E, F, G lie, respectively, on sides BC, CA, AB such that AE bisects BF at point R, BF bisects CG at point S, and CG bisects AE at point T. Find the area of triangle RST.

[figure: A; B; C; E; F; G; R; S; T]

Problem A5 Prove that there are unique positive integers a, n such that

a^{n+1} − (a + 1)^{n} = 2001.

Problem A6 Can an arc of a parabola inside a circle of radius 1 have length greater than 4?

Problem B1 Let n be an even positive integer. Write the numbers 1, 2, …, n^{2} in the squares of an n × n grid so that the kth row, from left to right, is

(k − 1)n + 1, (k − 1)n + 2, …, (k − 1)n + n.

Color the squares of the grid so that half of the squares in each row and in each column are red and the other half are black (a checkerboard coloring is one possibility). Prove that for each such coloring, the sum of the numbers on the red squares is equal to the sum of the numbers on the black squares. Problem B2 Find all pairs of real numbers (x, y) satisfying the system of equations

\begin{aligned}\frac{1}{x} + \frac{1}{2y} & = (x^{2} + 3y^{2})(3x^{2} + y^{2}) \\ \frac{1}{x} − \frac{1}{2y} & = 2(y^{4} − x^{4}). \end{aligned}

Problem B3 For any positive integer n let ⟨n⟩ denote the closest integer to \sqrt{n}. Evaluate

∑_{n=1}^{∞} \frac{2^{⟨n⟩} + 2^{−⟨n⟩}}{2^{n}} .

Problem B4 Let S denote the set of rational numbers different from −1, 0 and 1. Define f : S → S by f(x) = x − \frac{1}{x}. Prove or disprove that

⋂_{n=1}^{∞} f^{(n)}(S) = ∅,

where f^{(n)} = \underbrace{f ∘ f ∘ ⋯ ∘ f}_{n times}.

(Note: f(S) denotes the set of all values f(s) for s ∈ S.)

Problem B5 Let a and b be real numbers in the interval (0, \frac{1}{2}) and let g be a continuous real-valued function such that g(g(x)) = ag(x) + bx for all real x. Prove that g(x) = cx for some constant c. Problem B6 Assume that (a_{n})_{n≥1} is an increasing sequence of positive real numbers such that lim_{n→∞} \frac{a_{n}}{n} = 0. Must there exist infinitely many positive integers n such that

a_{n−i} + a_{n+i} < 2a_{n} for i = 1, 2, …, n − 1?

Solutions

D. J. Bernstein, 2 December 2001

Problem A1 Consider a set S and a binary operation ∗ on S (that is, for each a, b in S, a ∗ b is in S). Assume that (a ∗ b) ∗ a = b for all a, b in S. Prove that a ∗ (b ∗ a) = b for all a, b in S. Solution: a ∗ (b ∗ a) = ((b ∗ a) ∗ b) ∗ (b ∗ a) = b. Problem A2 You have coins C_{1}, C_{2}, …, C_{n}. For each k, coin C_{k} is biased so that, when tossed, it has probability \frac{1}{2k + 1} of falling heads. If the n coins are tossed, what is the probability that the number of heads is odd? Express the answer as a rational function of n. Solution: The answer is n/(2n + 1). For n = 0: There are no coins, so there are no heads. The probability of an odd number of heads is 0 = n/(2n + 1). For n ≥ 1: By induction, the probability of an odd number of heads among the first n − 1 coins is (n − 1)/(2n − 1). Hence the probability of an odd number of heads among the first n coins is

\frac{n − 1}{2n − 1} \frac{2n}{2n + 1} + \frac{n}{2n − 1} \frac{1}{2n + 1} = \frac{2n^{2} − n}{(2n − 1)(2n + 1)} = \frac{n}{2n + 1}

as claimed. Problem A3 For each integer m, consider the polynomial

P_{m}(x) = x^{4} − (2m + 4)x^{2} + (m − 2)^{2}.

For what values of m is P_{m}(x) the product of two nonconstant polynomials with integer coefficients? Solution: Squares, and half squares. If m = k^{2} then (x^{2} − 2kx + m − 2)(x^{2} + 2kx + m − 2) = (x^{2} + m − 2)^{2} − (2kx)^{2} = x^{4} + (2m − 4)x^{2} + (m − 2)^{2} − 4mx^{2} = x^{4} − (2m + 4)x^{2} + (m − 2)^{2}. If 2m = k^{2} then (x^{2} − m − 2k − 2)(x^{2} − m + 2k − 2) = (x^{2} − m − 2)^{2} − (2k)^{2} = x^{4} − (2m + 4)x^{2} + (m + 2)^{2} − 4k^{2} = x^{4} − (2m + 4)x^{2} + (m − 2)^{2}.

Conversely: Assume that f, g are nonconstant integer polynomials with f(x)g(x) = x^{4} − (2m + 4)x^{2} + (m − 2)^{2}.

If f or g has degree 1 then x^{4} − (2m + 4)x^{2} + (m − 2)^{2} has a rational root, say r; so the quadratic y^{2} − (2m + 4)y + (m − 2)^{2} has a rational root, namely r^{2}; so the discriminant (2m + 4)^{2} − 4(m − 2)^{2} = 32m is a rational square; so 2m = 32m/4^{2} is a rational square, hence an integer square.

Otherwise both f and g have degree 2. Write f(x) as ax^{2}+bx+c and g(x) as a′x^{2}+b′x+c′. The coefficient of x^{4} in fg is aa′, so 1 = aa′; both a and a′ are integers, so either a = a′ = 1 or a = a′ = −1. The coefficient of x^{3} in fg is ab′ +a′b, so 0 = ab′ +a′b = ±(b′ +b); hence b′ = −b. The coefficient of x in fg is bc′ + b′c, so 0 = bc′ + b′c = b(c′ − c); hence b = 0 or c′ = c.

If b = 0 then the quadratic y^{2} − (2m + 4)y + (m − 2)^{2} factors as (ay + c)(ay + c′), so 2m is a square as above. Otherwise c′ = c, so the coefficients of x^{2} and x^{0} in fg are 2ac − b^{2} and c^{2} respectively, so 2m + 4 = b^{2} − 2ac and (m − 2)^{2} = c^{2} = a^{2}c^{2}. If ac = −(m − 2) then b^{2} = 2m+4+2ac = 8, contradiction. Thus ac = m−2 and b^{2} = 2m+4+2ac = 4m, so m is a square.

Problem A4

Triangle ABC has area 1. Points E, F, G lie, respectively, on sides BC, CA, AB such that AE bisects BF at point R, BF bisects CG at point S, and CG bisects AE at point T. Find the area of triangle RST.

[figure: A; B; C; E; F; G; R; S; T]

Solution: Put the triangle into the Cartesian plane. Shift the plane so that A = (0, 0). Rotate the triangle so that B is on the positive x axis. Negate y coordinates if necessary so that C has a positive y coordinate. Shear the plane, leaving the x axis alone, so that C is on the y axis. The length of AB is λ for some λ > 0; multiply x coordinates by 2/λ, and multiply y coordinates by λ/2.

Areas and bisections are preserved by these transformations, so all the hypotheses of the problem still hold, and the area of RST has not changed. The triangle is now fixed in the plane: A = (0, 0), B = (2, 0), and C = (0, 1).

[figure: A; B; C; E; F; G; R; S; T]

Write e for the x-coordinate of E. Then the y-coordinate of E is 1 − e/2, since E is on BC; so T = (A + E)/2 = (e/2, 1/2 − e/4); so G is (2e/(2 + e), 0), since G is on CT; so S = (C + G)/2 = (e/(2 + e), 1/2); so F is (0, (2 + e)/(4 + e)), since F is on BS; so R = (B + F)/2 = (1, (2 + e)/(8 + 2e)). But R is on AE, so 1 − e/2 = e(2 + e)/(8 + 2e), so e = ±\sqrt{5} − 1. Also, E is between B and C, so e ≥ 0, so e = \sqrt{5} − 1.

The differences R − T and S − T are ((2 − e)/2, e/(8 + 2e)) and ((e − 2)/(2 + e), e/4), with determinant (7 − 3\sqrt{5})/2 > 0. Hence the area of RST is (7 − 3\sqrt{5})/4.

Problem A5

Prove that there are unique positive integers a, n such that

a^{n+1} − (a + 1)^{n} = 2001.

Solution: If (a, n) = (13, 2) then a^{n+1} − (a + 1)^{n} = 13^{3} − 14^{2} = 2197 − 196 = 2001.

Conversely, assume that a^{n+1} − (a + 1)^{n} = 2001. Then a divides a^{n+1}, and it divides (a + 1)^{n} − 1, so it divides a^{n+1} − (a + 1)^{n} + 1 = 2002 = 2 · 7 · 11 · 13. Hence a ∈ {1, 2, 7, 11, 13, 14, 22, 26, 77, 91, 143, 154, 182, 286, 1001, 2002}.

Similarly, a+1 divides (a+1)^{n}, and it divides ((a+1)−1)^{n+1} −(−1)^{n+1} = a^{n+1} +(−1)^{n}, so it divides 2001 + (−1)^{n}. Hence a ∈ {1, 7, 13}: neither 2000 nor 2002 is divisible by any of 3, 12, 15, 23, 27, 78, 92, 144, 155, 183, 287, 1002, 2003.

Note also that a^{2} divides a^{n+1}, and it divides (a + 1)^{n} − na − 1, so it divides 2002 + na; in other words, a divides 2002/a + n.

Case 1: a = 1. Then a^{n+1} − (a + 1)^{n} = 1 − 2^{n} < 2001.

Case 2: a = 7. Then 7 divides 286 + n, and n is even since 8 divides 2001 + (−1)^{n}, so n ∈ {8, 22, 36, …}. If n = 8 then a^{n+1}−(a+1)^{n} = 7^{9}−8^{8} = 40353607−16777216 ≠ 2001. If n ≥ 22 then a^{n+1} − (a + 1)^{n} is negative: indeed, (8/7)^{6} = 262144/117649 > 2, so (8/7)^{n} > (8/7)^{18} > 2^{3} > 7, so 7^{n+1} < 8^{n}.

Case 3: a = 13. Then 13 divides 154 + n, so n ∈ {2, 15, 28, 41, …}. If n = 2 then (a, n) = (13, 2) as desired. If n = 15 or n = 28 then 10 divides 13^{n+1} − 14^{n} − 7, so 13^{n+1} − 14^{n} ≠ 2001. If n ≥ 41 then a^{n+1} − (a + 1)^{n} is negative: indeed, (14/13)^{10} = 289254654976/137858491849 > 2, so (14/13)^{n} > (14/13)^{40} > 2^{4} > 13, so 13^{n+1} < 14^{n}.

Problem A6

Can an arc of a parabola inside a circle of radius 1 have length greater than 4?

Solution: Yes.

Define ϵ = 10^{−6} and r = log((8 − 16ϵ)/ϵ). Then ϵ sinh r = 4 − 8ϵ − ϵ^{2}/(16 − 32ϵ) > 4 − 9 · 10^{−6}, and ϵr > ϵ log(1/ϵ) = 10^{−6} log 10^{6} > 9 · 10^{−6}, so ϵ sinh r + ϵr > 4.

For each t in the interval [−r/2, r/2], define x(t) = 2ϵ sinh t, y(t) = ϵ(sinh t)^{2} − 1, and s(t) = (1/2)ϵ sinh 2t + ϵt. Note that 2 |sinh t| ≤ e^{r/2} so (sinh t)^{2} ≤ e^{r}/4 = (2 − 4ϵ)/ϵ. Hence 1−x(t)^{2}−y(t)^{2} = (2ϵ−4ϵ^{2})(sinh t)^{2}−ϵ^{2}(sinh t)^{4} = ϵ(sinh t)^{2}(2−4ϵ−ϵ(sinh t)^{2}) ≥ 0. In other words, (x(t), y(t)) is inside the unit circle.

Now y(t) = x(t)^{2}/4ϵ − 1, so the set of (x(t), y(t)) is an arc of a parabola; x is injective, so the distance travelled by (x(t), y(t)) is the length of the arc; and s′(t)^{2} = ϵ^{2}(cosh 2t+1)^{2} = 4ϵ^{2}(cosh t)^{4} = (2ϵ cosh t)^{2} + (2ϵ sinh t cosh t)^{2} = x′(t)^{2} + y′(t)^{2}, so the distance travelled by (x(t), y(t)) for t ∈ [−r/2, r/2] is s(r/2) − s(−r/2) = 2s(r/2) = ϵ sinh r + ϵr > 4.

I like the content of this problem. However, the wording could have been improved. What is an “arc”? Is it a rectifiable subset? A connected rectifiable subset? Students who interpreted the problem one way would have spent time worrying about the twocomponent case, while students who interpreted the problem another way would not have done so; this is not fair to the first group. “Can the intersection of a parabola with a disk of radius 1 have arc length greater than 4?” would have avoided this ambiguity.

Problem B1

Let n be an even positive integer. Write the numbers 1, 2, …, n^{2} in the squares of an n × n grid so that the kth row, from left to right, is

(k − 1)n + 1, (k − 1)n + 2, …, (k − 1)n + n.

Color the squares of the grid so that half of the squares in each row and in each column are red and the other half are black (a checkerboard coloring is one possibility). Prove that for each such coloring, the sum of the numbers on the red squares is equal to the sum of the numbers on the black squares.

Solution: More generally, fix functions f and g, and consider a matrix whose (k, j) entry is g(k) + f(j). There are n/2 reds for each k, and n/2 blacks for each k, so the sum of g(k) over reds equals the sum of g(k) over blacks. There are n/2 reds for each j, and n/2 blacks for each j, so the sum of f(j) over reds equals the sum of f(j) over blacks. Hence the sum of g(k) + f(j) over reds equals the sum of g(k) + f(j) over blacks.

Problem B2

Find all pairs of real numbers (x, y) satisfying the system of equations

\begin{aligned}\frac{1}{x} + \frac{1}{2y} & = (x^{2} + 3y^{2})(3x^{2} + y^{2}) \\ \frac{1}{x} − \frac{1}{2y} & = 2(y^{4} − x^{4}). \end{aligned}

Solution: Define f(u) = 2u^{5} − 5u^{4} + 20u^{3} − 10u^{2} + 10u − 1. The derivative f′(u) = 10u^{4} − 20u^{3} + 60u^{2} − 20u + 10 = 10(u^{2} − u + 1)^{2} + 30u^{2} is always positive, so there is exactly one real root u_{0} of f. Note that f(0) < 0 and f(1/2) > 0, so u_{0} is strictly between 0 and 1/2.

There is exactly one pair (x, y) satisfying the equations: namely, (x_{0}, u_{0}x_{0}), where x_{0} = ((1 − 2u_{0})/4(u_{0} − u_{0}^{5}))^{1/5}.

Proof outline: Write u = y/x. Divide the equations to see that f(u) = 0. Thus u = u_{0}. Substitute y = u_{0}x into 1/x−1/2y = 2(y^{4}−x^{4}) to see that x^{5} = (1−2u_{0})/4(u_{0}−u_{0}^{5}) = x_{0}^{5}. Hence x = x_{0} and y = u_{0}x_{0}. Conversely, (x_{0}, u_{0}x_{0}) does satisfy both equations.

This is a horrible problem. Students around the country must have wasted an incredible amount of time trying to find simpler forms for u_{0} and x_{0}. Apparently the author thought it was acceptable to express an answer in terms of a root of a single-variable polynomial, but the problem doesn’t say that. There are many other Putnam problems where such an expression would not receive full credit. Contestants should not have to guess how their work will be graded.

Problem B3

For any positive integer n let ⟨n⟩ denote the closest integer to \sqrt{n}. Evaluate

∑_{n=1}^{∞} \frac{2^{⟨n⟩} + 2^{−⟨n⟩}}{2^{n}} .

Solution: Consider all possible values q ≥ 1 for ⟨n⟩. Observe that ⟨n⟩ = q if and only if (q − 0.5)^{2} < n < (q + 0.5)^{2}, i.e., n ∈ {q^{2} − q + 1, …, q^{2} + q}. The values of n + q are {q^{2} + 1, …, (q + 1)^{2} − 1}; as q varies, these values cover all positive integers other than squares. The values of n − q are {(q − 1)^{2}, …, q^{2}}; as q varies, these values cover all nonnegative integers, with positive squares covered twice.

Hence the multiset of values of n ± ⟨n⟩ is {0, 1, 1, 2, 2, …}; each positive integer appears exactly twice. The desired sum is 2^{0} + 2^{−1} + 2^{−1} + 2^{−2} + 2^{−2} + … = 1 + 2 = 3.

One can, equivalently, split the sum by q.

Problem B4

Let S denote the set of rational numbers different from −1, 0 and 1. Define f : S → S

by f(x) = x − \frac{1}{x}. Prove or disprove that

⋂_{n=1}^{∞} f^{(n)}(S) = ∅,

where f^{(n)} = \underbrace{f ∘ f ∘ ⋯ ∘ f}_{n times}.

(Note: f(S) denotes the set of all values f(s) for s ∈ S.)

Solution: Define g(x) for x ∈ S as the positive integer |b^{2}x| where b is the smallest positive integer such that bx is an integer; in other words, g(a/b) = |ab| if a and b are coprime.

By Lemma 1, g(f(x)) exceeds g(x), so g(f^{n}(x)) ≥ g(x) + n > n. If f(S) ∩ f^{2}(S) ∩ ⋯ has an element y, then in particular f^{g(y)}(S) contains y, so y = f^{g(y)}(x) for some x, so g(y) = g(f^{g(y)}(x)) > g(y); contradiction. Thus f(S) ∩ f^{2}(S) ∩ ⋯ is empty.

Lemma 1: g(f(x)) > g(x).

Proof: Write x as a/b where a and b are coprime. Then f(x) = x − 1/x = a/b − b/a = (a^{2} −b^{2})/ab. If a prime p divides both ab and a^{2} −b^{2} then it divides a or b, hence a^{2} or b^{2}, hence both a^{2} and b^{2}, hence both a and b, contradiction. Thus ab and a^{2}−b^{2} are coprime, and g(f(x)) = |(a^{2} − b^{2})ab| = |a^{2} − b^{2}| g(x). If g(f(x)) ≤ g(x) then |a^{2} − b^{2}| ≤ 1, so both a and b are in {−1, 0, 1}, so x ∈ {−1, 0, 1}, contradiction.

Problem B5

Let a and b be real numbers in the interval (0, \frac{1}{2}) and let g be a continuous real-valued function such that g(g(x)) = ag(x) + bx for all real x. Prove that g(x) = cx for some constant c.

Solution: Note that g is injective, because if g(x) = g(y) then bx = g(g(x)) − ag(x) = g(g(y)) − ag(y) = by. Thus g is either strictly increasing or strictly decreasing.

If g(x) converges as x → ∞, or as x → −∞, then g(g(x)) also converges, so bx = g(g(x)) − ag(x) converges; contradiction. Therefore, if g is increasing, it increases to ∞ as x → ∞, and decreases to −∞ as x → −∞; if g is decreasing, it decreases to −∞ as x → ∞, and increases to ∞ as x → −∞. In short: g is invertible.

Write Δ = a^{2} + 4b, c = (\sqrt{Δ} + a)/2, and d = (\sqrt{Δ} − a)/2. Note that 0 < d < c < 1. A standard induction shows that g^{n}(x)\sqrt{Δ} = c^{n}(g(x) + dx) − (−d)^{n}(g(x) − cx) and g^{−n}(x)\sqrt{Δ} = c^{−n}(g(x) + dx) − (−d)^{−n}(g(x) − cx). In particular, lim_{n→∞} g^{n}(x) = 0. By continuity g(0) = lim_{n→∞} g(g^{n}(x)) = lim_{n→∞} g^{n+1}(x) = 0. Therefore g(x) always has the same sign as x if g is increasing, and g(x) always has the same sign as −x if g is decreasing.

If there is an x for which g(x) ≠ −dx, then (c/d)^{n} ≥ |(g(x) − cx)/(g(x) + dx)| for all sufficiently large n, say n ≥ k. Thus g^{n}(x) has the same sign as c^{n}(g(x)+dx) for all n ≥ k. In particular, g^{k+1}(x) has the same sign as g^{k}(x), so g is increasing. Contrapositive: If g is decreasing, then g(x) = −dx for all x.

Similarly, if there is an x for which g(x) ≠ cx, then g^{−n}(x) has the same sign as (−d)^{−n}(g(x) − cx) for all sufficiently large k, so g is decreasing. Contrapositive: If g is increasing, then g(x) = cx for all x.

Problem B6

Assume that (a_{n})_{n≥1} is an increasing sequence of positive real numbers such that lim_{n→∞} \frac{a_{n}}{n} = 0. Must there exist infinitely many positive integers n such that

a_{n−i} + a_{n+i} < 2a_{n} for i = 1, 2, …, n − 1?

Solution: Yes.

Define f(ϵ) for 0 < ϵ < a_{1} as follows. By hypothesis a_{n}/n < ϵ for all sufficiently large n. Thus there are only finitely many n for which a_{n} − nϵ is positive. There is at least one such n, namely 1, so there is a maximum value of a_{n} − nϵ. Now f(ϵ) is the n that maximizes a_{n} − nϵ; if there are several such n then f(ϵ) is the largest.

I claim that, if n = f(ϵ), then a_{n−i} + a_{n+i} < 2a_{n} for all i ∈ {1, 2, …, n − 1}. Indeed, a_{n−i} −(n−i)ϵ ≤ a_{n} −nϵ and a_{n+i} −(n+i)ϵ ≤ a_{n} −nϵ by definition of f, so a_{n−i} +a_{n+i} ≤ 2a_{n}. The only way to achieve equality is to have both a_{n−i} − (n − i)ϵ = a_{n} − nϵ and a_{n+i} − (n + i)ϵ = a_{n} − nϵ, but this again contradicts the definition of f, since n + i is larger than n.

I also claim that, for every m ≥ 1, there is an ϵ such that f(ϵ) ≥ m. Indeed, define ϵ as the minimum of (a_{m} − a_{m−1})/m and a_{1}/2. By hypothesis a_{1} > 0 and a_{m} > a_{m−1}, so 0 < ϵ < a_{1}. Furthermore a_{m} − mϵ is at least as large as a_{m−1}, hence larger than a_{1} − ϵ, a_{2} − 2ϵ, …, a_{m−1} − (m − 1)ϵ.

Conclusion: There are infinitely many values of f, and each value of f is a qualifying n.

The pairs (n, a_{n}) selected here are the corners of the upper convex hull of all pairs (n, a_{n}). There may be other n’s that work—for example, a_{3} may be below the line from a_{1} to a_{4}, even if it is above the line from a_{1} to a_{5} and the line from a_{2} to a_{4}—but the corners are relatively easy to identify.