Problem Solving in Math (Math 43900) Fall 2013

Week seven (October 8) solutions

Instructor: David Galvin

Some warm-up problems

n+1 n


1. n! < 2 for n = 2, 3, 4, . . ..

Solution: Use the geometric mean - arithmetic mean inequality, with (a1 , . . . , an ) = (1, . . . , n).
p
2. 3(a + b + c) a + b + c for positive a, b, c.

Solution: Use the power means inequality, with (a1 , a2 , a3 ) = (a, b, c) and r = 1/2, s = 1.

3. Minimize x1 + . . . + xn subject to xi 0 and x1 . . . xn = 1.

Solution: Guess: the minimum is n, achieved when all x1 = 1. Then use geometric mean -
arithmetic mean inequality to show
 
x1 + . . . + xn
n x1 . . . xn = 1
n
for positive xi satisfying x1 . . . xn = 1.

4. Minimize
x2 y2 z2
+ +
y+z z+x x+y
subject to x, y, z 0 and xyz = 1.


x y z

Solution: Apply Cauchy-Schwartz with the vectors y + z, z + x, x + y and y+z , z+x , x+y
to get  2
y2 z2

2 x
(x + y + z) + + 2 (x + y + z) ,
y+z z+x x+y
leading to
x2 y2 z2 x+y+z
+ + .
y+z z+x x+y 2
By the AM-GM inequality,
x+y+z
3 xyz = 1,
3
so
x2 y2 z2 3
+ + .
y+z z+x x+y 2
This lower bound can be achieved by taking x = y = z = 1, so the minimum is 3/2.

1
 5. If triangle has side lengths a, b, c and opposite angles (measured in radians) A, B, C, then
aA + bB + cC
.
a+b+c 3

Solution: Assume, without loss of generality, that a b c. Then also A B C, so by

Chebychev,
    
aA + bB + cC a+b+c A+B+C a+b+c
= ,
3 3 3 3 3
from which the result follows.

6. Identify which is bigger:

1999!(2000) or 2000!(1999) .
(Here n!(k) indicates iterating the factorial function k times, so for example 4!(2) = 24!.)
Solution: For n 1, n! is increasing in n (1 n < m implies n! < m!). So, starting from
the easy
1999! > 2000,
apply the factorial function 1999 more times to get
1999!(2000) > 2000!(1999) .

7. Identify which is bigger:

19991999 or 20001998 .

Solution: Consider f (x) = (1999 x) ln(1999 + x). We have ef (0) = 19991999 and ef (1) =
20001998 , so we want to see what f does on the interval [0, 1]: increase or decrease? The
derivative is
1999 x
f 0 (x) = ln(1999 + x) + ,
1999 + x
which is negative on [0, 1] (since, for example,
1999 x
1 = ln e < ln(1999 + x)
1999 + x
on that interval). So
20001998 < 19991999 .
8. Minimize
sin3 x cos3 x
+
cos x sin x
on the interval 0 < x < /2.
Solution: We can use the rearrangement inequality on the pairs sin3 x, cos3 x (which sat-

isfies sin3 x cos3 x on [0, /4], and sin3 x cos3 x on [/4, /2]), and (1/ cos x, 1/ sin x)
(which also satisfies 1/ cos x 1/ sin x on [0, /4], and 1/ cos x 1/ sin x on [/4, /2]), to
get
sin3 x cos3 x sin3 x cos3 x
+ + = sin2 x + cos2 x = 1
cos x sin x sin x cos x
on the whole interval. Since 1 can be achieved (at x = /4) the minimum is 1.

Source: These problems were all taken from a Northwestern Putnam prep problem set.

2
The Putnam problems
1. Show that for non-negative reals a1 , . . . , an and b1 , . . . , bn ,

(a1 . . . an )1/n + (b1 . . . bn )1/n ((a1 + b1 ) . . . (an + bn ))1/n .

Solution: If any ai is 0, the result is trivial, so we may assume all ai > 0. Dividing through
by (a1 . . . an )1/n , the inequality becomes

1 + (c1 . . . cn )1/n ((1 + c1 ) . . . (1 + cn ))1/n

for ci 0. Raising both sides to the power n, this is the same as

n   n
X n k/n
X
(c1 . . . cn ) ek
k
k=0 k=0

where ek is the sum of the products of the ci s, taken k at a time. So it is enough to show
that for each k,  
n X Y
(c1 . . . cn )k/n ci .
k
A{1,...,n}, |A|=k iA
Q
We apply the AM-GM inequality to the numbers iA ci as A ranges over all subsets of size
k of {1, . . . , n}. Note that each ai appears exactly n1


k1 times in all these numbers. So we
we get P Q
n1 n |A|=k iA ci
(c . . . c )(k1) (k )
/ A{1,...,n},
1 n
. n
k
n1 n



Since k1 / k = k/n, this is the same as
P Q
k/n A{1,...,n}, |A|=k iA ci
(c1 . . . cn ) n

,
k

which is exactly what we wanted to show.

Source: Putnam 2003 A2

2. Minimize
9 2
p 
2 2
(u v) + 2u
v

in the range 0 < u < 2, v > 0.

Solution: Theexpression to be minimized is the (square of the) distance between a point

of the form (u, 2 u2 ) on 0 < u < 2, and a point of the form (v, 9/v) on v > 0; in other
words, we are looking for the (square of the) distance between the circle x2 +y 2 = 2 in the first
quadrant and the hyperbola xy = 9 in the same quadrant. By symmetry, it strongly seems
that the two closed points are (3, 3) on the hyperbola and (1, 1) on the circle (squared distance
8). To prove that this is the minimum, note that the tangent lines to the two curves at those
two points are parallel, that the distance between them at these points is the perpendicular
distance between the two tangent lines, and that the hyperbola (in the first quadrant) lies

3
 completely above its tangent line, while the circle (in the first quadrant) lies completely below
its tangent line; so the distance between ant other two points is at least the distance between
the two tangent lines.

Source: Putnam 1984 B2

3. For positive integers m, n, show

(m + n)! m! n!
< m n.
(m + n)m+n m n

Solution: Rearranging, this is the same as

  m  n
m+n m n
< 1.
m m+n m+n

This suggests looking at the binomial expansion

 m+n
m n
+ .
m+n m+n

The whole binomial expansion sums to 1; one term of the expansion is

  m  n
m+n m n
.
m m+n m+n

Since all terms are strictly positive, we get the required inequality.

Source: Putnam 2004 B2

4. Maximize x3 3x subject to x4 + 36 13x2 .

Solution: The inequality x4 + 36 13x2 factors as (x + 3)(x + 2)(x 2)(x 3) 0, so

3 x 2 or 2 x 3. The derivative of x3 3x is 3x2 3 = 3(x + 1)(x 1), and so
we see that x3 3x is increasing on both [3, 2] and [2, 3]. The maximum is therefore the
maximum of f (2) and f (3), which is f (3) = 18.

Source: Putnam 1986 A1

5. Show that for every positive integer n,

  2n1   2n+1
2n 1 2 2n + 1 2
1 3 5 . . . (2n 1) < .
e e

Solution: We estimate the integral of ln x, which is convex and hence easy to estimate. Take
the integral from 1 to 2n 1. This is less than 2(ln 3 + ln 5 + . . . + ln(2n 1)). But the
antiderivative of ln x is x ln x x, so the integral evaluates to (2n 1) ln(2n 1) 2n + 2.
Hence (2n1) ln(2n1)(2n1) < (2n1) ln(2n1)2n+2 < 2(ln 3+ln 5+. . .+ln(2n1)).
Exponentiating gives the right-hand inequality.

4
 Similarly, the integral from e to 2n + 1 is greater than 2(ln 3 + ln 5 + . . . + ln(2n 1)), and an
explicit evaluation of the antiderivative here leads to the right-hand side of the inequality. The
choice of lower bound e for the integral here is just the righ thing to make the computations
work out nicely.

Source: Putnam 1996 B2

6. Let f be a real function with a continuous third derivative such that f (x), f 0 (x), f 00 (x) and
f 000 (x) are positive for all x. Suppose that f 000 (x) f (x) for all x. Show that f 0 (x) < 2f (x)
for all x.

Solution: See Kedlaya, Poonen & Vakil, The William Lowell Putnam Mathematical Com-
petition 19852000; Problems, Solutions and Commentary, page 272. This was one of the
hardest Putnam Competition problems ever of the top 205 performers in the 1999 Putnam,
only one contestant received a score of more than 0 for this problem, and that score was 2!

Source: Putnam 1999 B4

7. Maximize Z y p
x4 + (y y 2 )2 dx
0
on the interval [0, 1].
Ryp
Solution: Let f (y) = 0 x4 + (y y 2 )2 dx. At y = 0, f (y) = 0, and at y = 1, f (y) =
R1 2
0 x dx = 1/3. Also, f is non-negative on [0, 1]. It looks like it will be impossible to evaluate
f (y) at any value other than y = 0, 1; this strongly leads to the suspicion that the maximum
is at y = 1. To prove this, we need to show that f 0 (y) 0 on the interval [0, 1]. A process by
which this can be done is outlined in Kedlaya, Poonen & Vakil, The William Lowell Putnam
Mathematical Competition 19852000; Problems, Solutions and Commentary, page 138.
Heres a (really) slick solution from the same source: Since x2 and y y 2 are positive in the
range 0 x 1, 0 y 1, we have

x4 + (y y 2 )2 x4 + 2x2 (y y 2 ) + (y y 2 )2 = (x2 + (y y 2 ))2 ,

and so Z y Z y
p 2
x2 + (y y 2 ) dx = y 2 y 3 .


x4 + (y y 2 )2 dx
0 0 3
The derivative of + y2 (2/3)y 3
is 2y 2y 2
= 2y(1 y) which is non-negative on [0, 1], so the
maximum is at y = 1, where it is 1/3. So
Z yp
x4 + (y y 2 )2 dx 1/3;
0

and 1/3 is achievable, at y = 1.

Source: Putnam 1991 A5