Putnam Mathematical Competition, 6 December 2003

Problem A1 Let n be a fixed positive integer. How many ways are there to write n as a sum of positive integers,

n = a_{1} + a_{2} + ⋯ + a_{k},

with k an arbitrary positive integer and a_{1} ≤ a_{2} ≤ ⋯ ≤ a_{k} ≤ a_{1} + 1? For example, with n = 4, there are four ways: 4, 2 + 2, 1 + 1 + 2, 1 + 1 + 1 + 1. Problem A2 Let a_{1}, a_{2}, …, a_{n} and b_{1}, b_{2}, …, b_{n} be nonnegative real numbers. Show that

(a_{1}a_{2} ⋯ a_{n})^{1/n} + (b_{1}b_{2} ⋯ b_{n})^{1/n} ≤ ((a_{1} + b_{1})(a_{2} + b_{2}) ⋯ (a_{n} + b_{n}))^{1/n}.

Problem A3 Find the minimum value of

|sin x + cos x + tan x + cot x + sec x + csc x|

for real numbers x. Problem A4 Suppose that a, b, c, A, B, C are real numbers, a ≠ 0 and A ≠ 0, such that

|ax^{2} + bx + c| ≤ |Ax^{2} + Bx + C|

for all real numbers x. Show that |b^{2} − 4ac| ≤ |B^{2} − 4AC| .

Problem A5 A Dyck n-path is a lattice path of n upsteps (1, 1) and n downsteps (1, −1) that starts at the origin O and never dips below the x-axis. A return is a maximal sequence of contiguous downsteps that terminates on the x-axis. For example, the Dyck 5-path illustrated has two returns, of length 3 and 1 respectively.

[figure: •; O; •; •; •; •; •; •; •; •; •; •]

Show that there is a one-to-one correspondence between the Dyck n-paths with no return of even length and the Dyck (n − 1)-paths.

Problem A6

For a set S of nonnegative integers, let r_{S}(n) denote the number of ordered pairs (s_{1}, s_{2}) such that s_{1} ∈ S, s_{2} ∈ S, s_{1} ≠ s_{2}, and s_{1} + s_{2} = n. Is it possible to partition the nonnegative integers into two sets A and B in such a way that r_{A}(n) = r_{B}(n) for all n?

Problem B1 Do there exist polynomials a(x), b(x), c(y), d(y) such that

1 + xy + x^{2}y^{2} = a(x)c(y) + b(x)d(y)

holds identically? Problem B2 Let n be a positive integer. Starting with the sequence 1, \frac{1}{2}, \frac{1}{3}, …, \frac{1}{n}, form a new sequence of n−1 entries \frac{3}{4}, \frac{5}{12}, …, \frac{2n − 1}{2n(n − 1)}, by taking the averages of two consecutive entries in the first sequence. Repeat the averaging of neighbors on the second sequence to obtain a third sequence of n−2 entries and continue until the final sequence produced consists of a single number x_{n}. Show that x_{n} < \frac{2}{n}. Problem B3 Show that for each positive integer n,

n! = ∏_{i=1}^{n} lcm {1, 2, …, ⌊n/i⌋} .

(Here lcm denotes the least common multiple, and ⌊x⌋ denotes the greatest integer ≤ x.) Problem B4 Let f(z) = az^{4} + bz^{3} + cz^{2} + dz + e = a(z − r_{1})(z − r_{2})(z − r_{3})(z − r_{4}) where a, b, c, d, e are integers, a ≠ 0. Show that if r_{1} + r_{2} is a rational number, and if r_{1} + r_{2} ≠ r_{3} + r_{4}, then r_{1}r_{2} is a rational number. Problem B5 Let A, B and C be equidistant points on the circumference of a circle of unit radius centered at O, and let P be any point in the circle’s interior. Let a, b, c be the distances from P to A, B, C respectively. Show that there is a triangle with side lengths a, b, c, and that the area of this triangle depends only on the distance from P to O. Problem B6 Let f(x) be a continuous real-valued function defined on the interval [0, 1]. Show that

∫_{0}^{1} ∫_{0}^{1} |f(x) + f(y)| dx dy ≥ ∫_{0}^{1} |f(x)| dx.

Solutions

D. J. Bernstein, 7 December 2003

Problem A1

Let n be a fixed positive integer. How many ways are there to write n as a sum of positive integers,

n = a_{1} + a_{2} + ⋯ + a_{k},

with k an arbitrary positive integer and a_{1} ≤ a_{2} ≤ ⋯ ≤ a_{k} ≤ a_{1} + 1? For example, with n = 4, there are four ways: 4, 2 + 2, 1 + 1 + 2, 1 + 1 + 1 + 1.

Solution: There are exactly n ways to write n as such a sum. More precisely, there is exactly 1 way (a_{1}, a_{2}, …, a_{k}) for each k ∈ {1, 2, …, n}.

Say a_{1}, a_{2}, …, a_{k} satisfy the stated conditions. Observe first that n ≥ a_{1}+a_{2}+⋯+a_{k} ≥ 1 + 1 + ⋯ + 1 = k so k ∈ {1, 2, …, n}. The inequalities a_{1} ≤ a_{2} ≤ ⋯ ≤ a_{k} ≤ a_{1} + 1 imply that all of a_{1}, a_{2}, …, a_{k} are in {a_{1}, a_{1} + 1}. Define j as the number of occurrences of a_{1} + 1; then n = a_{1} + a_{2} + ⋯ + a_{k} = ka_{1} + j with 0 ≤ j ≤ k − 1, so a_{1} = ⌊n/k⌋ and j = n mod k. Thus a_{1}, a_{2}, …, a_{k} consist of n mod k occurrences of ⌊n/k⌋ + 1 preceded by k − (n mod k) occurrences of ⌊n/k⌋.

Conversely, take any k ∈ {1, 2, …, n}, and build a_{1}, a_{2}, …, a_{k} as n mod k occurrences of ⌊n/k⌋ + 1 preceded by k − (n mod k) occurrences of ⌊n/k⌋. Then a_{1} ≤ a_{2} ≤ ⋯ ≤ a_{k}; a_{k} ≤ ⌊n/k⌋ + 1 ≤ a_{1} + 1; and a_{1} + a_{2} + ⋯ + a_{k} = k ⌊n/k⌋ + (n mod k) = n.

Problem A2

Let a_{1}, a_{2}, …, a_{n} and b_{1}, b_{2}, …, b_{n} be nonnegative real numbers. Show that

(a_{1}a_{2} ⋯ a_{n})^{1/n} + (b_{1}b_{2} ⋯ b_{n})^{1/n} ≤ ((a_{1} + b_{1})(a_{2} + b_{2}) ⋯ (a_{n} + b_{n}))^{1/n}.

Solution: If a_{i} = b_{i} = 0 then the left side and right side are both 0. So assume that a_{i} + b_{i} > 0 for each i. By the arithmetic-geometric mean inequality,

\begin{matrix}(\frac{a_{1}}{a_{1} + b_{1}} ⋯ \frac{a_{n}}{a_{n} + b_{n}} )^{1/n} + (\frac{b_{1}}{a_{1} + b_{1}} ⋯ \frac{b_{n}}{a_{n} + b_{n}} )^{1/n} \\ ≤ \frac{1}{n} (\frac{a_{1}}{a_{1} + b_{1}} + ⋯ + \frac{a_{n}}{a_{n} + b_{n}} ) + \frac{1}{n} (\frac{b_{1}}{a_{1} + b_{1}} + ⋯ + \frac{b_{n}}{a_{n} + b_{n}} ) = 1. \end{matrix}

Clear denominators: (a_{1} ⋯ a_{n})^{1/n} + (b_{1} ⋯ b_{n})^{1/n} ≤ ((a_{1} + b_{1}) ⋯ (a_{n} + b_{n}))^{1/n}.

This result, Hölder’s inequality, is fairly standard course material, so it isn’t a reasonable Putnam problem.

Problem A3

Find the minimum value of

|sin x + cos x + tan x + cot x + sec x + csc x|

for real numbers x.

Solution: The problem does not make sense as stated: the trigonometric functions are not all defined when x is a multiple of π/2. I presume that the intent was to say “for real numbers x where sin x ≠ 0 and cos x ≠ 0,” i.e., for real numbers x that are not multiples of π/2.

The statement of the problem also implies that there is a minimum value of the function. Are contestants required to prove this, or are they allowed to assume it? I presume that contestants are required to prove it.

Anyway, the minimum is 2\sqrt{2} − 1.

Write y = sin x + cos x. Then y^{2} = (sin x)^{2} + (cos x)^{2} + 2 sin x cos x = 1 + 2 sin x cos x, so tan x+cot x = (sin x)^{2}/(sin x cos x)+(cos x)^{2}/(sin x cos x) = 2/(y^{2}−1) and sec x+csc x = (sin x)/(sin x cos x) + (cos x)/(sin x cos x) = 2y/(y^{2} − 1), so sin x + cos x + tan x + cot x + sec x + csc x = y + 2/(y^{2} − 1) + 2y/(y^{2} − 1) = y + 2/(y − 1).

If y > 1 then, by the arithmetic-geometric-mean inequality, (y − 1) + 2/(y − 1) ≥ 2\sqrt{(y − 1)2/(y − 1)} = 2\sqrt{2}, so y + 2/(y − 1) ≥ 2\sqrt{2} + 1 > 2\sqrt{2} − 1. If y < 1 then similarly (1 − y) + 2/(1 − y) ≥ 2\sqrt{2} so −(y + 2/(y − 1)) ≥ 2\sqrt{2} − 1. In both cases, |y + 2/(y − 1)| ≥ 2\sqrt{2} − 1, so |sin x + cos x + tan x + cot x + sec x + csc x| ≥ 2\sqrt{2} − 1.

To see that the alleged minimum is achieved, note that 1/\sqrt{2} − 1 ∈ [−1, 1], and set x = π/4+arccos(1/\sqrt{2}−1). Then y = \sqrt{2} cos(x−π/4) = 1−\sqrt{2} so y+2/(y−1) = 1−2\sqrt{2}.

Problem A4

Suppose that a, b, c, A, B, C are real numbers, a ≠ 0 and A ≠ 0, such that

|ax^{2} + bx + c| ≤ |Ax^{2} + Bx + C|

for all real numbers x. Show that

|b^{2} − 4ac| ≤ |B^{2} − 4AC| .

Solution: Assume without loss of generality that a > 0. (Otherwise replace (a, b, c) with (−a, −b, −c); this transformation does not change |ax^{2} + bx + c|, and it does not change |b^{2} − 4ac|.) Similarly assume that A > 0.

Observe that lim_{x→∞}(Ax^{2} +Bx+C)/x^{2} = A. Thus lim_{x→∞} |(Ax^{2} + Bx + C)/x^{2}| = A. Similarly lim_{x→∞} |(ax^{2} + bx + c)/x^{2}| = a. Hence a ≤ A.

Now write d = b^{2} − 4ac and D = B^{2} − 4AC.

Case 1: D > 0. Write r = (−B + \sqrt{D})/2A and s = (−B − \sqrt{D})/2A; then r ≠ s. If x ∈ {r, s} then Ax^{2} + Bx + C = 0 so |ax^{2} + bx + c| ≤ |0| = 0 so ax^{2} + bx + c = 0. Thus ax^{2} + bx + c = a(x − r)(x − s); so d = a^{2}(r − s)^{2} = a^{2}(\sqrt{D}/A)^{2} = Da^{2}/A^{2}. Hence 0 < d ≤ D.

Case 2: D = 0. The functions Ax^{2} + Bx + C and −Ax^{2} − Bx − C both have value 0 and derivative 0 for x = −B/2A, so the intermediate function ax^{2} + bx + c also has value 0 and derivative 0, i.e., a double root. Hence d = 0.

Case 3: D < 0. Then Ax^{2} + Bx + C = A(x + B/2A)^{2} − D/4A > 0 for all real numbers x, so ±(ax^{2} + bx + c) ≤ Ax^{2} + Bx + C for all x, so (A ∓ a)x^{2} + (B ∓ b)x + (C ∓ c) ≤ 0 for all x, so (B ∓ b)^{2} ≤ 4(A ∓ a)(C ∓ c), i.e., B^{2} ∓ 2Bb + b^{2} ≤ 4AC + 4ac ∓ (4Ac + 4aC). Average ∓ = + and ∓ = − to see that B^{2} + b^{2} ≤ 4AC + 4ac, i.e., d ≤ −D.

On the other hand, take x = −B/2A to see that −d/4a ≤ a(x + b/2a)^{2} − d/4a = ax^{2} + bx + c ≤ Ax^{2} + Bx + C = −D/4A; i.e., −d ≤ −Da/A ≤ −D.

Problem A5

A Dyck n-path is a lattice path of n upsteps (1, 1) and n downsteps (1, −1) that starts at the origin O and never dips below the x-axis. A return is a maximal sequence of contiguous downsteps that terminates on the x-axis. For example, the Dyck 5-path illustrated has two returns, of length 3 and 1 respectively.

[figure: •; O; •; •; •; •; •; •; •; •; •; •]

Show that there is a one-to-one correspondence between the Dyck n-paths with no return of even length and the Dyck (n − 1)-paths.

Solution: The problem fails to specify the range of n. The definition of a (−1)-path is unclear, so I presume that the definition of n-paths is for all n ≥ 0 and that the conclusion is for all n ≥ 1.

Fix n ≥ 1. If k ∈ {1, 2, …, n} then any (n − k)-path, followed by an upstep, followed by any (k − 1)-path, followed by a downstep, forms an n-path. Every n-path is obtained in this way from a unique k, a unique (n − k)-path, and a unique (k − 1)-path. (The upstep, (k − 1)-path, and downstep are the last mountain in the n-path.)

Hence C_{n} = C_{n−1}C_{0} + C_{n−2}C_{1} + ⋯ + C_{0}C_{n−1} for n ≥ 1, where C_{n} is the number of n-paths. Note that C_{0} = 1.

Next define O_{n} as the number of n-paths having a final return of odd length. Note that O_{0} = 0. For n ≥ 1, every such path is obtained from a unique k ∈ {1, 2, …, n}, a unique (n − k)-path, and a unique (k − 1)-path that does not have a final return of odd length; hence O_{n} = C_{n−1}(C_{0} − O_{0}) + C_{n−2}(C_{1} − O_{1}) + ⋯ + C_{0}(C_{n−1} − O_{n−1}).

Next define X_{n} as the number of n-paths having no return of even length. Note that X_{0} = 1. For n ≥ 1, every such path is obtained from a unique k ∈ {1, 2, …, n}, a unique (n − k)-path having no return of even length, and a unique (k − 1)-path that does not have a final return of odd length; hence X_{n} = X_{n−1}(C_{0} − O_{0}) + X_{n−2}(C_{1} − O_{1}) + ⋯ + X_{0}(C_{n−1} − O_{n−1}).

In particular, X_{1} = X_{0}(C_{0} − O_{0}) = 1(1 − 0) = 1 = C_{0} as desired.

Assume inductively that X_{1} = C_{0}, X_{2} = C_{1}, and so on through X_{n} = C_{n−1}. Then X_{n+1} = X_{n}(C_{0} − O_{0}) + X_{n−1}(C_{1} − O_{1}) + ⋯ + X_{1}(C_{n−1} − O_{n−1}) + X_{0}(C_{n} − O_{n}) = C_{n−1}(C_{0}−O_{0})+C_{n−2}(C_{1}−O_{1})+⋯+C_{0}(C_{n−1}−O_{n−1})+(C_{n}−O_{n}) = O_{n}+C_{n}−O_{n} = C_{n}.

In other words, the number of n-paths with no return of even length is the same as the number of (n − 1)-paths; i.e., there is a one-to-one correspondence between the two sets.

Problem A6

For a set S of nonnegative integers, let r_{S}(n) denote the number of ordered pairs (s_{1}, s_{2}) such that s_{1} ∈ S, s_{2} ∈ S, s_{1} ≠ s_{2}, and s_{1} + s_{2} = n. Is it possible to partition the nonnegative integers into two sets A and B in such a way that r_{A}(n) = r_{B}(n) for all n?

Solution: Yes.

Define A = {0, 3, 5, 6, 9, …} as the set of nonnegative integers n whose binary expansions have an even number of 1’s, and define B = {1, 2, 4, 7, 8, …} as the set of nonnegative integers n whose binary expansions have an odd number of 1’s.

Define f as the formal power series ∑_{n∈A} x^{n}. Similarly define g = ∑_{n∈B} x^{n}.

Now f(x^{2}) + xg(x^{2}) = ∑_{n∈A} x^{2n} + ∑_{n∈B} x^{2n+1} = ∑_{2n∈A} x^{2n} + ∑_{2n+1∈A} x^{2n+1} = ∑_{m∈A} x^{m} = f. Similarly g(x^{2}) + xf(x^{2}) = g. Hence f − g = f(x^{2}) − g(x^{2}) + xg(x^{2}) − xf(x^{2}) = (1 − x)(f(x^{2}) − g(x^{2})).

Furthermore, f +g = ∑_{n} x^{n} = 1/(1−x). Hence f^{2} −g^{2} = (f −g)(f +g) = f(x^{2})−g(x^{2}).

On the other hand, f^{2} = ∑_{s∈A,t∈A} x^{s}x^{t} = ∑_{s∈A} x^{2s} + ∑_{s∈A,t∈A,s≠t} x^{s+t} = f(x^{2}) + ∑_{n} r_{A}(n)x^{n}. Similarly g^{2} = g(x^{2}) + ∑_{n} r_{B}(n)x^{n}. Hence ∑_{n} r_{A}(n)x^{n} = f^{2} − f(x^{2}) = g^{2} − g(x^{2}) = ∑_{n} r_{B}(n)x^{n}; i.e., r_{A}(n) = r_{B}(n) for all n.

Problem B1

Do there exist polynomials a(x), b(x), c(y), d(y) such that

1 + xy + x^{2}y^{2} = a(x)c(y) + b(x)d(y)

holds identically?

Solution: No.

Suppose that 1+xy+x^{2}y^{2} = a(x)c(y)+b(x)d(y). Write a(x), b(x), c(y), d(y) respectively as a_{0} + a_{1}x + a_{2}x^{2} + ⋯, b_{0} + b_{1}x + b_{2}x^{2} + ⋯, c_{0} + c_{1}y + c_{2}y^{2} + ⋯, d_{0} + d_{1}y + d_{2}y^{2} + · · ·. Then

1 + xy + x^{2}y^{2} = (a_{0}c_{0} + b_{0}d_{0}) + (a_{0}c_{1} + b_{0}d_{1})y + (a_{0}c_{2} + b_{0}d_{2})y^{2}
+ (a_{1}c_{0} + b_{1}d_{0})x + (a_{1}c_{1} + b_{1}d_{1})xy + (a_{1}c_{2} + b_{1}c_{2})xy^{2}
+ (a_{2}c_{0} + b_{2}c_{0})x^{2} + (a_{2}c_{1} + b_{2}c_{1})x^{2}y + (a_{2}c_{2} + b_{2}c_{2})x^{2}y^{2} + · · · .

Extract coefficients: a_{0}c_{0} + b_{0}d_{0} = 1, so a_{0}c_{0}c_{1} + b_{0}c_{1}d_{0} = c_{1}; and a_{0}c_{1} + b_{0}d_{1} = 0, so a_{0}c_{0}c_{1} + b_{0}c_{0}d_{1} = 0, so b_{0}(c_{1}d_{0} − c_{0}d_{1}) = c_{1}. Similarly b_{0}(c_{1}d_{2} − d_{1}c_{2}) = 0 and b_{2}(c_{1}d_{2} − d_{1}c_{2}) = c_{1}. If b_{0} = 0 then c_{1} = 0; if b_{0} ≠ 0 then c_{1}d_{2} − d_{1}c_{2} = 0 so c_{1} = 0. Either way, c_{1} = 0. Exchange a, c with b, d to see that d_{1} = 0. Hence 1 = a_{1}c_{1}+b_{1}d_{1} = 0; contradiction.

Problem B2

Let n be a positive integer. Starting with the sequence 1, \frac{1}{2}, \frac{1}{3}, …, \frac{1}{n}, form a new

sequence of n−1 entries \frac{3}{4}, \frac{5}{12}, …, \frac{2n − 1}{2n(n − 1)}, by taking the averages of two consecutive

entries in the first sequence. Repeat the averaging of neighbors on the second sequence to obtain a third sequence of n−2 entries and continue until the final sequence produced

consists of a single number x_{n}. Show that x_{n} < \frac{2}{n}.

Solution: The kth repeated average of u_{1}, u_{2}, … is (\binom{k}{0}u_{1} + \binom{k}{1}u_{2} + ⋯ + \binom{k}{k}u_{k})/2^{k}, (\binom{k}{0}u_{2} + \binom{k}{1}u_{3} + ⋯ + \binom{k}{k}u_{k+1})/2^{k}, …, by induction on k.

In particular, the (n − 1)st repeated average of 1, 1/2, …, 1/n, namely x_{n}, is

\begin{aligned}\frac{1}{2^{n−1}} ∑_{0≤i≤n−1} \binom{n − 1}{i}\frac{1}{i + 1} & = \frac{2}{n · 2^{n}} ∑_{0≤i≤n−1} \binom{n − 1}{i}\frac{n}{i + 1} \\ & = \frac{2}{n · 2^{n}} ∑_{0≤i≤n−1} \binom{n}{i + 1} = \frac{2}{n · 2^{n}} (2^{n} − 1) < \frac{2}{n}. \end{aligned}

Problem B3

Show that for each positive integer n,

n! = ∏_{i=1}^{n} lcm {1, 2, …, ⌊n/i⌋} .

(Here lcm denotes the least common multiple, and ⌊x⌋ denotes the greatest integer ≤ x.)

Solution: Let p be a prime number. For any positive integer u, write ord_{p} u for the largest nonnegative integer e such that p^{e} divides u.

If p^{e} ≤ m < p^{e+1} then ord_{p} lcm {1, 2, …, m} = e. Indeed, p^{e} appears in {1, 2, …, m}, so it divides lcm {1, 2, …, m}, while p^{e+1} divides none of {1, 2, …, m}, and hence does not divide lcm {1, 2, …, m}.

Hence ord_{p} lcm {1, 2, …, ⌊n/i⌋} = e exactly when p^{e} ≤ ⌊n/i⌋ < p^{e+1}.

Next consider the sum [i ≤ n/p] + [i ≤ n/p^{2}] + [i ≤ n/p^{3}] + ⋯, where [⋯] means 1 when ⋯ is true, 0 otherwise. This sum is e exactly when i ≤ n/p^{e} but i > n/p^{e+1}, i.e., when p^{e} ≤ ⌊n/i⌋ < p^{e+1}. Hence

ord_{p} ∏_{i} lcm {1, 2, …, ⌊n/i⌋} = ∑_{i} ord_{p} lcm {1, 2, …, ⌊n/i⌋}

= ∑_{i}([i ≤ n/p] + [i ≤ n/p^{2}] + [i ≤ n/p^{3}] + ⋯)

= ⌊n/p⌋ + ⌊n/p^{2}⌋ + ⌊n/p^{3}⌋ + ⋯ = ord_{p} n!.

This is true for every prime p, so ∏_{i} lcm {1, 2, …, ⌊n/i⌋} = n!.

Problem B4

Let f(z) = az^{4} + bz^{3} + cz^{2} + dz + e = a(z − r_{1})(z − r_{2})(z − r_{3})(z − r_{4}) where a, b, c, d, e are integers, a ≠ 0. Show that if r_{1} + r_{2} is a rational number, and if r_{1} + r_{2} ≠ r_{3} + r_{4}, then r_{1}r_{2} is a rational number.

Solution: Abbreviate r_{1} + r_{2} as u, and r_{3} + r_{4} as v. Then

\begin{aligned}f(z)/a & = (z − r_{1})(z − r_{2})(z − r_{3})(z − r_{4}) = (z^{2} − uz + r_{1}r_{2})(z^{2} − vz + r_{3}r_{4}) \\ & = z^{4} − (u + v)z^{3} + (uv + r_{1}r_{2} + r_{3}r_{4})z^{2} − (ur_{3}r_{4} + vr_{1}r_{2})z + r_{1}r_{2}r_{3}r_{4}. \end{aligned}

Thus u + v is rational, and by hypothesis u is rational, so v is rational, so uv and u − v are rational. Furthermore, uv + r_{1}r_{2} + r_{3}r_{4} is rational, so r_{1}r_{2} + r_{3}r_{4} is rational, so ur_{1}r_{2} + ur_{3}r_{4} is rational. Next, ur_{3}r_{4} + vr_{1}r_{2} is rational, so (u − v)r_{1}r_{2} is rational. By hypothesis u − v is nonzero, so r_{1}r_{2} is rational.

This is too easy for a B4 problem.

Problem B5

Let A, B and C be equidistant points on the circumference of a circle of unit radius centered at O, and let P be any point in the circle’s interior. Let a, b, c be the distances from P to A, B, C respectively. Show that there is a triangle with side lengths a, b, c, and that the area of this triangle depends only on the distance from P to O.

Solution: Put the circle into the complex plane, translated so that O = 0 and rotated so that A = 1. Then B and C are the two primitive cube roots of 1.

Define Δ = 2a^{2}b^{2} + 2a^{2}c^{2} + 2b^{2}c^{2} − a^{4} − b^{4} − c^{4}. Heron’s theorem states that a, b, c are the side lengths of a triangle if and only if Δ > 0, and that the triangle has area \sqrt{Δ}/4.

Write P as ru where r is a nonnegative real number and u is a complex number of absolute value 1. Then a^{2} = |P − A|^{2} = |ru − 1|^{2} = (ru − 1)(r/u − 1) = s − ru − r/u where s = 1 + r^{2}; b^{2} = |P − B|^{2} = |ru − B|^{2} = (ru − B)(r/u − C) = s − Cru − Br/u; and c^{2} = |P − C|^{2} = |ru − C|^{2} = (ru − C)(r/u − B) = s − Bru − Cr/u.

Square to obtain a^{4}, b^{4}, c^{4}, and add. All of the u’s drop out of the resulting formula, since 1 + B + C = 0 and 1 + B^{2} + C^{2} = 0. (For example, the cross-terms 2rsu, 2Crsu, and 2Brsu add up to 0.) Hence a^{4} + b^{4} + c^{4} = 3(s^{2} + 2r^{2}). By a similar computation, a^{2}b^{2} + a^{2}c^{2} + b^{2}c^{2} = 3s^{2} + (2B + 2C + B^{2} + C^{2})r^{2} = 3(s^{2} − r^{2}). Hence Δ = 3(s^{2} − 4r^{2}) = 3(1 − r^{2})^{2}.

By hypothesis P is in the interior of the unit circle; i.e., 0 ≤ r < 1. Hence Δ > 0. The area of the triangle is (1 − r^{2})\sqrt{3}/4, which is determined by r = |P | as claimed.

Problem B6

Let f(x) be a continuous real-valued function defined on the interval [0, 1]. Show that

∫_{0}^{1} ∫_{0}^{1} |f(x) + f(y)| dx dy ≥ ∫_{0}^{1} |f(x)| dx.

Solution: If x_{1}, …, x_{n} are real numbers in [0, 1] then

∑_{i≠j} 2[f(x_{i})f(x_{j}) < 0] min {|f(x_{i})| , |f(x_{j})|} ≤ n ∑_{j} |f(x_{j})|

by Lemma 1 below. Integrate over all x_{1}, …, x_{n}:

n(n − 1) ∫ ∫ 2[f(x)f(y) < 0] min {|f(x)| , |f(y)|} dx dy ≤ n^{2} ∫ |f(x)| dx.

Divide by n^{2}:

\frac{n − 1}{n} ∫ ∫ 2[f(x)f(y) < 0] min \{|f(x)| , |f(y)|\} dx dy ≤ ∫ |f(x)| dx.

Take the limit as n → ∞:

∫ ∫ 2[f(x)f(y) < 0] min {|f(x)| , |f(y)|} dx dy ≤ ∫ |f(x)| dx.

Finally, |u + v| = |u| + |v| − 2[uv < 0] min {|u| , |v|}, so

∫ ∫ |f(x) + f(y)| dx dy

= ∫ |f(x)| dx + ∫ |f(y)| dy − 2 ∫ ∫ [f(x)f(y) < 0] min {|f(x)| , |f(y)|} dx dy

≥ ∫ |f(y)| dy

as claimed.

Lemma 1: ∑_{i≠j} 2[r_{i}r_{j} < 0] min {|r_{i}| , |r_{j}|} ≤ n ∑_{j} |r_{j}| for any real numbers r_{1}, r_{2}, …, r_{n}.

Proof: Without loss of generality assume that |r_{1}| ≥ |r_{2}| ≥ ⋯ ≥ |r_{n}|. Then the sum on the left is equal to ∑_{i<j} 4[r_{i}r_{j} < 0] |r_{j}|.

Define a_{j} for j ≥ 0 as the number of positive entries in r_{1}, r_{2}, …, r_{j}. Define b_{j} for j ≥ 0 as the number of negative entries in r_{1}, r_{2}, …, r_{j}. The product a_{j}b_{j} is at most (j/2)^{2} ≤ (n/2)(j/2), so

(a_{1}b_{1} − a_{0}b_{0}) |r_{1}| + (a_{2}b_{2} − a_{1}b_{1}) |r_{2}| + ⋯ + (a_{n}b_{n} − a_{n−1}b_{n−1}) |r_{n}| = a_{1}b_{1}(|r_{1}| − |r_{2}|) + a_{2}b_{2}(|r_{2}| − |r_{3}|) + ⋯ + a_{n−1}b_{n−1}(|r_{n−1}| − |r_{n}|) + a_{n}b_{n}(|r_{n}|)

≤ \frac{n}{2} \frac{1}{2}(|r_{1}| − |r_{2}|) + \frac{n}{2} \frac{2}{2}(|r_{2}| − |r_{3}|) + ⋯ + \frac{n}{2} \frac{n − 1}{2}(|r_{n−1}| − |r_{n}|) + \frac{n}{2} \frac{n}{2}(|r_{n}|)

= \frac{n}{4} |r_{1}| + \frac{n}{4} |r_{2}| + \frac{n}{4} |r_{3}| + ⋯ + \frac{n}{4} |r_{n}| .

Next observe that a_{j}b_{j} − a_{j−1}b_{j−1} is exactly b_{j−1} if r_{j} > 0; a_{j−1} if r_{j} < 0; and 0 if r_{j} = 0. In other words, a_{j}b_{j} − a_{j−1}b_{j−1} is the number of i < j such that r_{i}r_{j} < 0. Hence ∑_{i<j} 4[r_{i}r_{j} < 0] |r_{j}| = ∑_{j} 4(a_{j}b_{j} − a_{j−1}b_{j−1}) |r_{j}| ≤ n ∑_{j} |r_{j}| as claimed.