Putnam Mathematical Competition, 4 December 2004

Problem A1

Basketball star Shanille O’Keal’s team statistician keeps track of the number, S(N), of successful free throws she has made in her first N attempts of the season. Early in the season, S(N) was less than 80% of N, but by the end of the season, S(N) was more than 80% of N. Was there necessarily a moment in between when S(N) was exactly 80% of N?

Problem A2

For i = 1, 2, let T_{i} be a triangle with side lengths a_{i}, b_{i}, c_{i}, and area A_{i}. Suppose that a_{1} ≤ a_{2}, b_{1} ≤ b_{2}, c_{1} ≤ c_{2}, and that T_{2} is an acute triangle. Does it follow that A_{1} ≤ A_{2}?

Problem A3

Define a sequence {u_{n}}_{n=0}^{∞} by u_{0} = u_{1} = u_{2} = 1, and thereafter by the condition that

det ( \begin{matrix}u_{n} & u_{n+1} \\ u_{n+2} & u_{n+3} \end{matrix} ) = n!

for all n ≥ 0. Show that u_{n} is an integer for all n. (By convention, 0! = 1.)

Problem A4

Show that for any positive integer n there is an integer N such that the product x_{1}x_{2} ⋯ x_{n} can be expressed identically in the form

x_{1}x_{2} ⋯ x_{n} = ∑_{i=1}^{N} c_{i}(a_{i1}x_{1} + a_{i2}x_{2} + ⋯ + a_{in}x_{n})^{n}

where the c_{i} are rational numbers and each a_{ij} is one of the numbers, −1, 0, 1.

Problem A5

An m×n checkerboard is colored randomly: each square is independently assigned red or black with probability 1/2.We say that two squares, p and q, are in the same connected monochromatic region if there is a sequence of squares, all of the same color, starting at p and ending at q, in which successive squares in the sequence share a common side. Show that the expected number of connected monochromatic regions is greater than mn/8.

Problem A6 Suppose that f(x, y) is a continuous real-valued function on the unit square 0 ≤ x ≤ 1, 0 ≤ y ≤ 1. Show that

\begin{matrix}∫_{0}^{1} (∫_{0}^{1} f(x, y) dx)^{2} dy + ∫_{0}^{1} (∫_{0}^{1} f(x, y) dy)^{2} dx \\ ≤ (∫_{0}^{1} ∫_{0}^{1} f(x, y) dx dy)^{2} + ∫_{0}^{1} ∫_{0}^{1}[f(x, y)]^{2} dx dy. \end{matrix}

Problem B1

Let P (x) = c_{n}x^{n} +c_{n−1}x^{n−1} +⋯+c_{0} be a polynomial with integer coefficients. Suppose that r is a rational number such that P (r) = 0. Show that the n numbers

c_{n}r, c_{n}r^{2} + c_{n−1}r, c_{n}r^{3} + c_{n−1}r^{2} + c_{n−2}r, …, c_{n}r^{n} + c_{n−1}r^{n−1} + ⋯ + c_{1}r

are integers.

Problem B2

Let m and n be positive integers. Show that

\frac{(m + n)!}{(m + n)^{m+n}} < \frac{m!}{m^{m}} · \frac{n!}{n^{n}} .

Problem B3

Determine all real numbers a > 0 for which there exists a nonnegative continuous function f(x) defined on [0, a] with the property that the region

R = {(x, y) : 0 ≤ x ≤ a, 0 ≤ y ≤ f(x)}

has perimeter k units and area k square units for some real number k.

Problem B4

Let n be a positive integer, n ≥ 2, and put θ = 2π/n. Define points P_{k} = (k, 0) in the xy-plane, for k = 1, 2, …, n. Let R_{k} be the map that rotates the plane counterclockwise by the angle θ about the point P_{k}. Let R denote the map obtained by applying, in order, R_{1}, then R_{2}, …, then R_{n}. For an arbitrary point (x, y), find, and simplify, the coordinates of R(x, y).

Problem B5

Evaluate

lim_{x→1^{−}} ∏_{n=0}^{∞} (\frac{1 + x^{n+1}}{1 + x^{n}} )^{x^{n}} .

Problem B6

Let A be a non-empty set of positive integers, and let N(x) denote the number of elements of A not exceeding x. Let B denote the set of positive integers b that can be written in the form b = a − a′ with a ∈ A and a′ ∈ A. Let b_{1} < b_{2} < ⋯ be the members of B, listed in increasing order. Show that if the sequence b_{i+1} − b_{i} is unbounded, then lim_{x→∞} N(x)/x = 0.

Solutions

D. J. Bernstein, 6 December 2004

Problem A1

Basketball star Shanille O’Keal’s team statistician keeps track of the number, S(N), of successful free throws she has made in her first N attempts of the season. Early in the season, S(N) was less than 80% of N, but by the end of the season, S(N) was more than 80% of N. Was there necessarily a moment in between when S(N) was exactly 80% of N?

Solution: Yes.

By hypothesis S(N_{1}) < 0.8N_{1} for some N_{1} but S(N_{2}) > 0.8N_{2} for some N_{2} > N_{1}. Find the smallest N ≥ N_{1} such that S(N) ≥ 0.8N. Then N ≠ N_{1}, so S(N − 1) < 0.8(N − 1). If she does not make her Nth free throw then S(N) = S(N − 1) < 0.8(N − 1) < 0.8N ≤ S(N), contradiction. If she makes her Nth free throw then S(N) = S(N − 1) + 1 so

0 ≤ 5S(N) − 4N = 5S(N − 1) + 5 − 4N < 4(N − 1) + 5 − 4N = 1.

The quantity 5S(N) − 4N is an integer, so it must be 0; i.e., S(N) = 0.8N as claimed.

Problem A2

For i = 1, 2, let T_{i} be a triangle with side lengths a_{i}, b_{i}, c_{i}, and area A_{i}. Suppose that a_{1} ≤ a_{2}, b_{1} ≤ b_{2}, c_{1} ≤ c_{2}, and that T_{2} is an acute triangle. Does it follow that A_{1} ≤ A_{2}?

Solution: Yes.

Recall Heron’s formula (4A)^{2} = 4a^{2}b^{2} − (a^{2} + b^{2} − c^{2})^{2} for the area A of a triangle with side lengths a, b, c. The derivative of (4A)^{2} with respect to c is 4c(a^{2} + b^{2} − c^{2}), which is positive if c^{2} < a^{2} + b^{2}, i.e., if the angle opposite c is acute. By symmetry, the derivative of (4A)^{2} with respect to a is positive if the angle opposite a is acute, and the derivative of (4A)^{2} with respect to b is positive if the angle opposite b is acute.

Find (a, b, c) in the compact set [a_{1}, a_{2}] × [b_{1}, b_{2}] × [c_{1}, c_{2}] to maximize A. It is not possible to have exactly one of a, b, c smaller than a_{2}, b_{2}, c_{2} respectively: for example, if a < a_{2} and b = b_{2} and c = c_{2}, then a^{2} < a_{2}^{2} < b_{2}^{2} + c_{2}^{2} = b^{2} + c^{2} since T_{2} is acute, so the angle opposite a is acute, so increasing a increases A, contradiction. Similarly, it is not possible to have two or three of a, b, c smaller than a_{2}, b_{2}, c_{2} respectively: for example, if a < a_{2} and b < b_{2}, then at least one angle opposite a or b must be acute, so increasing a or b increases A, contradiction.

Thus (a, b, c) = (a_{2}, b_{2}, c_{2}). In particular, A_{1} ≤ A_{2}.

Problem A3 Define a sequence {u_{n}}_{n=0}^{∞} by u_{0} = u_{1} = u_{2} = 1, and thereafter by the condition that

det ( \begin{matrix}u_{n} & u_{n+1} \\ u_{n+2} & u_{n+3} \end{matrix} ) = n!

for all n ≥ 0. Show that u_{n} is an integer for all n. (By convention, 0! = 1.) Solution: Define v_{0} = 1, v_{1} = 1, and v_{n} = (n − 1)v_{n−2} for all n ≥ 2. Then v_{n} is an integer. I claim that v_{n}v_{n+1} = n! for all n ≥ 0. Proof: If n = 0 then v_{n}v_{n+1} = v_{0}v_{1} = 1 = 0! = n! as claimed. If n ≥ 1 then assume inductively that v_{n−1}v_{n} = (n − 1)!. By definition v_{n+1} = nv_{n−1}, so v_{n}v_{n+1} = nv_{n−1}v_{n} = n(n − 1)! = n! as claimed. I now claim that u_{n} = v_{n} for all n ≥ 0. Proof: If n = 0, or n = 1, or n = 2, then u_{n} = 1 = v_{n} as claimed. For n ≥ 3, assume inductively that u_{n−3} = v_{n−3}, that u_{n−2} = v_{n−2}, and that u_{n−1} = v_{n−1}. By hypothesis (n − 3)! = u_{n−3}u_{n} − u_{n−1}u_{n−2}, so

\begin{aligned}u_{n} & = \frac{(n − 3)! + u_{n−1}u_{n−2}}{u_{n−3}} \\ & = \frac{(n − 3)! + v_{n−1}v_{n−2}}{v_{n−3}} = \frac{v_{n−3}v_{n−2} + (n − 2)v_{n−3}v_{n−2}}{v_{n−3}} = (n − 1)v_{n−2} = v_{n} \end{aligned}

as claimed. Hence u_{n} is an integer. Problem A4 Show that for any positive integer n there is an integer N such that the product x_{1}x_{2} ⋯ x_{n} can be expressed identically in the form

x_{1}x_{2} ⋯ x_{n} = ∑_{i=1}^{N} c_{i}(a_{i1}x_{1} + a_{i2}x_{2} + ⋯ + a_{in}x_{n})^{n}

where the c_{i} are rational numbers and each a_{ij} is one of the numbers, −1, 0, 1. Solution: One can take N = 2^{n}. Specifically, I claim that x_{1}x_{2} ⋯ x_{n} is the sum of (a_{1}a_{2} ⋯ a_{n}/2^{n}n!)(a_{1}x_{1} + a_{2}x_{2} + ⋯ + a_{n}x_{n})^{n} over all (a_{1}, a_{2}, …, a_{n}) ∈ {1, −1}^{n}. Define P_{0}(x_{1}, x_{2}, …, x_{n}) = (x_{1} + x_{2} + ⋯ + x_{n})^{n}. Note for future reference that the coefficient of x_{1}x_{2} ⋯ x_{n} in P_{0} is n!. Define P_{1}(x_{1}, x_{2}, …, x_{n}) = P_{0}(x_{1}, x_{2}, …, x_{n}) − P_{0}(−x_{1}, x_{2}, …, x_{n}). The coefficient of x_{1}^{e_{1}}x_{2}^{e_{2}} ⋯ x_{n}^{e_{n}} in P_{1} is 1 − (−1)^{e_{1}} times the corresponding coefficient in P_{0}.

Define P_{2}(x_{1}, x_{2}, …, x_{n}) = P_{1}(x_{1}, x_{2}, …, x_{n}) − P_{1}(x_{1}, −x_{2}, …, x_{n}). The coefficient of x_{1}^{e_{1}}x_{2}^{e_{2}} ⋯ x_{n}^{e_{n}} in P_{2} is 1−(−1)^{e_{2}} times the corresponding coefficient in P_{1}; in other words, (1 − (−1)^{e_{1}})(1 − (−1)^{e_{2}}) times the corresponding coefficient in P_{0}.

Define P_{3}, P_{4}, …, P_{n} similarly. Then the coefficient of x_{1}^{e_{1}}x_{2}^{e_{2}} ⋯ x_{n}^{e_{n}} in P_{n} is exactly (1 − (−1)^{e_{1}})(1 − (−1)^{e_{2}}) ⋯ (1 − (−1)^{e_{n}}) times the corresponding coefficient in P_{0}. The factor (1−(−1)^{e_{1}})(1−(−1)^{e_{2}}) ⋯ (1−(−1)^{e_{n}}) is 2^{n} if e_{1}, e_{2}, …, e_{n} are all odd, otherwise 0. The coefficient in P_{0} is 0 unless e_{1} + e_{2} + ⋯ + e_{n} = n. The only way for odd numbers e_{1}, e_{2}, …, e_{n} to have sum n is for all of them to be 1. Hence P_{n}(x_{1}, x_{2}, …, x_{n}) = 2^{n}n!x_{1}x_{2} ⋯ x_{n}.

Problem A5

An m×n checkerboard is colored randomly: each square is independently assigned red or black with probability 1/2.We say that two squares, p and q, are in the same connected monochromatic region if there is a sequence of squares, all of the same color, starting at p and ending at q, in which successive squares in the sequence share a common side. Show that the expected number of connected monochromatic regions is greater than mn/8.

Solution: Sorry, I haven’t solved this one yet.

Problem A6

Suppose that f(x, y) is a continuous real-valued function on the unit square 0 ≤ x ≤ 1, 0 ≤ y ≤ 1. Show that

\begin{matrix}∫_{0}^{1} (∫_{0}^{1} f(x, y) dx)^{2} dy + ∫_{0}^{1} (∫_{0}^{1} f(x, y) dy)^{2} dx \\ ≤ (∫_{0}^{1} ∫_{0}^{1} f(x, y) dx dy)^{2} + ∫_{0}^{1} ∫_{0}^{1}[f(x, y)]^{2} dx dy. \end{matrix}

Solution: Dave Rusin writes: “Let F (x, y, z, w) = f(x, y) + f(z, w) − f(x, w) − f(z, y); then integrate F^{2} over the box [0, 1]^{4}. Done!”

c_{n}r, c_{n}r^{2} + c_{n−1}r, c_{n}r^{3} + c_{n−1}r^{2} + c_{n−2}r, …, c_{n}r^{n} + c_{n−1}r^{n−1} + ⋯ + c_{1}r

are integers.

Solution: Fix i ∈ {0, 1, …, n − 1}. Write r as u/v where u and v are coprime. Then c_{n}(u/v)^{n} + c_{n−1}(u/v)^{n−1} + ⋯ + c_{0} = 0, so c_{n}u^{n} + c_{n−1}u^{n−1}v + ⋯ + c_{0}v^{n} = 0, so c_{n}u^{n} + c_{n−1}u^{n−1}v + ⋯ + c_{i+1}u^{i+1}v^{n−i−1} = −c_{i}u^{i}v^{n−i} − c_{i−1}u^{i−1}v^{n−i+1} − ⋯ − c_{0}v^{n} is a multiple of v^{n−i}; so c_{n}u^{n−i} + c_{n−1}u^{n−i−1}v + ⋯ + c_{i+1}uv^{n−i−1} is a multiple of v^{n−i} since u^{i} and v^{n−i} are coprime; so c_{n}(u/v)^{n−i} + c_{n−1}(u/v)^{n−1−i} + ⋯ + c_{i+1}(u/v) is an integer as claimed.

Problem B2

Let m and n be positive integers. Show that

\frac{(m + n)!}{(m + n)^{m+n}} < \frac{m!}{m^{m}} · \frac{n!}{n^{n}} .

Solution: Define g(x) = x log(1 + 1/x) for x > 0. Then g′(x) = log(1 + 1/x) − (1/x^{2})x/(1+1/x) = log(1+1/x)−1/(x+1), so g′′(x) = (−1/x^{2})/(1+1/x)+1/(x+1)^{2} = (1 − (x + 1)/x)/(x + 1)^{2} < 0. The limit of g′(x) as x → ∞ is 0, so g′(x) > 0 for all x > 0, so g is strictly increasing.

Fix m ≥ 1. Define f(n) = (m + n)!m^{m}n^{n}/(m + n)^{m+n}m!n! for n ≥ 1. Then f(1) = m^{m}/(m + 1)^{m} < 1, and f(n + 1)/f(n) = (m + n)^{m+n}(n + 1)^{n}/(m + n + 1)^{m+n}n^{n} = g(n)/g(m + n) < 1, so f(n) < 1 for all n.

Alternate proof: Use Stirling’s bounds 1 < n!(exp n)/n^{n}\sqrt{2πn} < exp(1/12n) for n ≥ 1 to see that f(n) is in [exp(−1/12m − 1/12n), exp(1/12(m + n))]\sqrt{(m + n)/2πmn} and hence is below exp(1/24)\sqrt{1/π}, which is smaller than 1 since exp(1/12) < exp 1 < π.

Alternate proof: The binomial expansion of (m+n)^{m+n} includes at least two terms since the exponent is positive; all the terms are positive, and one of them is \binom{m+n}{m}m^{m}n^{n}.

Problem B3

Determine all real numbers a > 0 for which there exists a nonnegative continuous function f(x) defined on [0, a] with the property that the region

R = {(x, y) : 0 ≤ x ≤ a, 0 ≤ y ≤ f(x)}

has perimeter k units and area k square units for some real number k.

Solution: The answer is {a : a > 2}.

For a > 2: Define f(x) = 2a/(a − 2) and k = 2a^{2}/(a − 2). Then f is nonnegative; f is continuous; the region R is a rectangle of width a and height 2a/(a − 2); the area of R is 2a^{2}/(a−2) = k; and the perimeter of R is 2a+4a/(a−2) = (2a(a−2)+4a)/(a−2) = k.

For a ≤ 2: Suppose that there exists such a function f. Because f is continuous, it has a maximum value on the compact interval [0, a]; say f(m) is the maximum. The area under f is at most af(m). The perimeter of the region is at least f(m), to get from (0, 0) to (m, f(m)); plus at least another f(m), to get from (m, f(m)) to (a, 0); plus a, to get from (a, 0) to (0, 0); for a total of a + 2f(m) ≥ a + af(m) > af(m). Contradiction.

Problem B4

Let n be a positive integer, n ≥ 2, and put θ = 2π/n. Define points P_{k} = (k, 0) in the xy-plane, for k = 1, 2, …, n. Let R_{k} be the map that rotates the plane counterclockwise by the angle θ about the point P_{k}. Let R denote the map obtained by applying, in order, R_{1}, then R_{2}, …, then R_{n}. For an arbitrary point (x, y), find, and simplify, the coordinates of R(x, y).

Solution: R(x, y) = (x + n, y).

Put (x, y) into the complex plane as z = x + iy, and put P_{1}, P_{2}, …, P_{n} into the complex plane as 1, 2, …, n. Define z_{0} = z, and define z_{k} for k ≥ 1 as the result of rotating z_{k−1} by θ around k. Then z_{k} = ζ(z_{k−1} − k) + k where ζ = cos θ + i sin θ, so, by induction, z_{k} = ζ^{k}z−ζ^{k}−ζ^{k−1}−…−ζ+k. In particular, z_{n} = ζ^{n}z−(ζ^{n}+ζ^{n−1}+…+ζ)+n = z+n.

Problem B5

Evaluate

lim_{x→1^{−}} ∏_{n=0}^{∞} (\frac{1 + x^{n+1}}{1 + x^{n}} )^{x^{n}} .

Solution: The answer is 2/exp 1.

The logarithm of ((1 + x^{n+1})/(1 + x^{n}))^{x^{n}} = (1 + x^{n}(x − 1)/(1 + x^{n}))^{x^{n}} is approximately x^{2n}(x − 1)/(1 + x^{n}). There are approximately δ/u(1 − x) nonnegative integers n for which u ≤ x^{n} < u + δ. The sum of x^{2n}(x − 1)/(1 + x^{n}) over those n’s is approximately −(δ/u)u^{2}/(1 + u) = −(u/(1 + u))δ. Hence the sum of x^{2n}(x − 1)/(1 + x^{n}) over all n’s is approximately − ∫_{0}^{1}(u/(1 + u)) du = log(1 + u) − u|_{0}^{1} = log 2 − 1.

To turn this into a complete proof, write down explicit error bounds (using explicit log bounds as in B2) instead of just saying “approximately”; then observe that the error converges to 0 as x approaches 1.

Problem B6

Let A be a non-empty set of positive integers, and let N(x) denote the number of elements of A not exceeding x. Let B denote the set of positive integers b that can be written in the form b = a − a′ with a ∈ A and a′ ∈ A. Let b_{1} < b_{2} < ⋯ be the members of B, listed in increasing order. Show that if the sequence b_{i+1} − b_{i} is unbounded, then lim_{x→∞} N(x)/x = 0.

Solution: Find the smallest positive integer g_{1} such that g_{1} ∉ B.

Find the smallest positive integer h_{2} such that h_{2}, h_{2} +1, h_{2} +2, …, h_{2} +6g_{1} ∉ B. Define g_{2} = 2g_{1}(1 + ⌈h_{2}/2g_{1}⌉). Then g_{2} − 2g_{1}, g_{2} − 2g_{1} + 1, g_{2} − 2g_{1} + 2, …, g_{2} + 2g_{1} ∉ B, and g_{2} is a multiple of 2g_{1}.

Find the smallest positive integer h_{3} such that h_{3}, h_{3} +1, h_{3} +2, …, h_{3} +6g_{2} ∉ B. Define g_{3} = 2g_{2}(1 + ⌈h_{3}/2g_{2}⌉). Then g_{3} − 2g_{2}, g_{3} − 2g_{2} + 1, g_{3} − 2g_{2} + 2, …, g_{3} + 2g_{2} ∉ B, and g_{3} is a multiple of 2g_{2}.

Similarly define g_{4}, g_{5}, . . ..

If k and m are positive integers then, by Lemma 1 below, A ∩ {1, 2, …, 2mg_{k}} has at most 2mg_{k}/2^{k} elements. Hence A ∩ [1, x] has at most 2g_{k} + 2⌊x/2g_{k}⌋g_{k}/2^{k} elements; i.e., N(x) ≤ 2g_{k} + x/2^{k}. Thus lim sup_{x→∞} N(x)/x ≤ 1/2^{k}. This is true for every k, so lim_{x→∞} N(x)/x = 0.

Lemma 1: For all integers k ≥ 1 and n ≥ 0, the set A ∩ {n + 1, n + 2, …, n + 2g_{k}} has at most 2g_{k}/2^{k} elements.

Proof for k = 1: If A has both n + 1 and n + g_{1} + 1 then g_{1} ∈ B, contradiction; thus A has at most one of n + 1, n + g_{1} + 1. Similar comments apply to n + 2, n + g_{1} + 2; n + 3, n + g_{1} + 3; …; n + g_{1}, n + 2g_{1}. Hence A ∩ {n + 1, n + 2, …, n + 2g_{1}} has at most g_{1} = 2g_{k}/2^{k} elements as claimed.

Proof for k ≥ 2: Assume inductively that, for all n, the set A ∩ {n + 1, …, n + 2g_{k−1}} has at most 2g_{k−1}/2^{k−1} elements.

Consider the sets S = {n + 1, …, n + 2g_{k−1}} and S′ = {n + g_{k} + 1, …, n + g_{k} + 2g_{k−1}}. If a ∈ S and a′ ∈ S′ then a′ − a ∈ {g_{k} − 2g_{k−1} + 1, …, g_{k} + 2g_{k−1} − 1}, so a′ − a ∉ B by construction of g_{k}. Hence A cannot have elements in common with both S and S′. Furthermore, A∩S has at most 2g_{k−1}/2^{k−1} elements, and A∩S′ has at most 2g_{k−1}/2^{k−1} elements, so A ∩ (S ∪ S′) has at most 2g_{k−1}/2^{k−1} elements.

Similar comments apply with n shifted by 2g_{k−1}, 4g_{k−1}, …, g_{k} − 2g_{k−1}; recall here that g_{k} is a multiple of 2g_{k−1}. Hence A ∩ {n + 1, n + 2, …, n + 2g_{k}} has at most (g_{k}/2g_{k−1})(2g_{k−1}/2^{k−1}) = 2g_{k}/2^{k} elements as claimed.