2011 U OF I MOCK PUTNAM CONTEST

Solutions
1. [Variation of A2, Putnam 1987] The sequence of digits
1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 ...
is obtained by writing out the natural numbers in order. Let f (n) denote the position of the first digit of the number
n in this sequence. Thus, for example, f (1) = 1, f (2) = 2, f (10) = 10 (since the integer n = 10 occupies positions 10
and 11 in this sequence), f (11) = 12 (since 11 occupies positions 12 and 13), f (12) = 14 (since 12 occupies positions
14 and 15, and so on.
Find, with proof, a simple explicit formula for f (10k ), where k is an arbitrary positive integer.
Solution. The desired formula is f (10k = k10k (10k 1)/9 + 1 . To prove this, note that 10k is the first integer
with k + 1 digits. Thus, the position of its first digit is 1 plus the total number of positions occupied by the integers
with at most k digits.
Now there are 10i 10i1 integers with exactly i digits (namely, all integers n in the range 10i1 n < 10i ), so the
total number of positions occupied by integers with i digits is i(10i 10i1 ). Adding these counts for i = 1, 2, . . . , k 1
gives the number of positions occupied by integers with at most k digits:
k
X k
X k1
X
(10i 10i1 )i = 10i i 10j (j + 1)
i=1 i=1 j=0
k1
X
= 10k k 10j
j=0

10k 1
= 10k k .
10 1
Adding 1 to this count gives the above formula for f (10k ).

2. Let an = [( 2 + 1)n ], where [x] denotes the greatest integer x (i.e., the floor function). Prove that an is even if and
only if n is odd.

Solution. Let bn := (1 + 2)n + (1 2)n . Expanding each of the two nth powers by the binomial theorem shows
that
n  
X n k k X n
bn = ( 2) + ( 2) = 2 2k/2 .
k k
k=0 k even
n
Hence bn is an even integer. Now (1 2) is a number of absolute
value at most 2 1 < 1/2 and is negative
for n
odd, and positive for n even. Since ( 2 + 1)n = bn (1 2)n , by the definition of bn , it follows that [( 2 + 1)n ] is
equal to bn when n is odd, and equal to bn 1 when n is even. Since bn is always even, this proves the claim.

3. [A2, Putnam 2003] Let a1 , . . . , an , b1 , . . . , bn be positive real numbers. Prove that

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

Solution. Dividing by the right-hand side, the given inequality can be rewritten as
(1) (x1 . . . xn )1/n + (y1 . . . yn )1/n 1,
where
ai bi
xi =
, yi = .
ai + bi ai + bi
Applying AGM to each term on the left of (1) gives
n n n
1X 1X 1X
(x1 . . . xn )1/n + (y1 . . . yn )1/n xi + yi = (xi + yi ) = 1,
n i=1 n i=1 n i=1

since xi + yi = 1 for each i.

4. Let P1 , P2 , P3 , . . . be a sequence of points in 3-dimensional space satisfying (i) |Pi | 1 for all i and (ii) |Pi Pj | 1
for all i and j with i 6= j. (Here |P Q| denotes the usual (Euclidean) distance between P and Q, and |P | denotes the
distance between P and the origin.)
(a) Prove that, if > 3, then the infinite series

X 1
i=1
|Pi |
converges.
(b) Show that there exists a sequence of points Pi satisfying conditions (i) and (ii) above for which the above series
diverges when = 3.
Solution. (a) First note that, without loss of generality, we may assume that the Pi all lie in the first octant. Subdivide
this octant into boxes of side length 1/2 of the form
     
m m+1 n n+1 p p+1
B(m, n, p) = , , , ,
2 2 2 2 2 2
p
where m, n, p are nonnegative integers. Since the largest distance between any two points in such a box is 3/4 < 1,
such a box can contain at most one of the points Pi . Moreover, since |Pi | 1, the box B(0, 0, 0) cannot contain a point
Pi .
Now note that, if Pi B(m, n, p), then
 m n p  1 p
|Pi |  , , = m2 + n2 + p2 .
 
2 2 2 2
Hence

X 1 X 2

i=1
|Pi | m,n,p=0
(m2 + n2 + p2 )/2
max(m,n,p)>0

X 1
3!2 2 + n2 + p2 )/2
(using symmetry in m, n, p)
0mnp
(m
p6=0

X 1
6 2 (since m2 + n2 + p2 p2 )
p
0mnp
p6=0

X (p + 1)2
6 2 (since there are (p + 1)2 choices of (m, n) with m, n p)
p=1
p

X (2p)2
6 2 (since p + 1 2p)
p=1
p


X 1
= 24 2 ,
p=1
p2

and since > 3, the latter series converges. This proves part (a).
(b) If we let the Pi be the lattice points (m, n, p) with positive integral coordinates, then the conditions |Pi | 1 and

1
 |Pi Pj | 1 are satisfied. On the other hand, we have

X 1 X 1

i=1
|Pi |3 m,n,p=1
(m2 + n2 + p2 )3/2

k+1 k+1 k+1

2X1 2 X1 2 X1
X 1

k=1 m=2k
(m2 + n2 + p2 )3/2
n=2k p=2k
k+1 k+1 k+1
2X1 2 X1 2 X1
X 1
(since (m2 + n2 + p2 )3/2 (3 22k+2 )3/2 100 23k )
100 23k
k=1 m=2k n=2k p=2k

1 X 1
= (2k )3 (since there are (2k )3 choices of (m, n, p))
100 23k
k=1

1 X
= 1 = ,
100
k=1
P
so the series i=1 1/|Pi |3 diverges.

5. Determine, with proof, whether the series

X 1
n 2+cos(2 ln n)
n=1
converges.
Solution. We claim that the series diverges (though only barely so). The proof is somewhat technical, but the
underlying idea is easy to describe: Namely, focus on integers for which () ln n k + 1/2, where k is a positive integer.
In this case, cos(2 ln n) cos(2(k + 1/2)) = 1, so the exponent of n in the given series will be approximately 1.
Thus, if one can show that () holds for long enough intervals of ns, then the series behaves like a harmonic series over
these stretches and therefore diverges.
To make this precise, define the intervals Ik , for k = 1, 2, 3, . . . , by
h 
Ik = ek+1/2 , ek+1/2+1/(2k) .

Note that these intervals are disjoint. We will show that the given sum restricted
P to the interval Ik is c/k, where c
is a positive constant. Hence the entire series is bounded from below by k=1 c/k, a divergent series.
To prove this, note first that
1 1 1
n Ik ek+ 2 n < ek+ 2 + 2k
1 1 1
k + ln n < k + +
2   2 2k   
1 1 1
= cos 2 k + cos(2 ln n) < cos 2 k + +
2 2 2k
  
1
cos() cos(2 ln n) < cos 1 +
k

= 1 cos(2 ln n) < 1 + ,
k
where the latter inequality follows from the bound

cos((1 + x)) cos() + x max | sin((1 + t))| 1 + x.

0tx

Also, if n Ik , then
1 1
ln n < k + + k + 1 2k,
2 2k
1 e(ln n)/k e2
= .
n1+/k n n

2
 It follows that
X 1 X e2
> .
nIk
n2+cos( ln n) nIk
n
Z 
2 1 1
e dt k+1/2 ,
I t e
 k 
2 k+1/2+1/k k+1/2 1
=e ln(e ) ln(e ) k+1/2 ,
e
 
1
e2 ek .
k

Summing the latter expression over all k gives a divergent series. Hence the given series diverges as well.

6. Let Gn denote the geometric mean of the n binomial coefficients n1 , n2 , . . . , nn .

Prove that the limit limn n Gn exists, and find its value. (You may only use the definition of binomial coefficients
and standard results from calculus, but not, for example, asymptotic formulas for binomial coefficients or factorials.)
1/n
Solution. We will show that limn Gn = e. Using the definition of the binomial coefficients, we get
n   n
Y n Y n! n!n
Gnn = = = 2 2
k k!(n k)! 1! 2! . . . n!2
k=1 k=1
1n 2n nn
= 2n 2n2 2n4 .
1 2 3 . . . (n 1)4 n2

Note that, for each i {1, 2, . . . , n}, the factor i occurs exactly n times in the numerator and 2(n i + 1) times in the
denominator. Hence,
n
X
ln Gnn = (ln i)(n 2(n i + 1))
i=1
Xn n
X
(1) = (ln i)(2i n) 2 ln i.
i=1 i=1

Also,
n  
X n(n + 1) 2
(2) (ln n)(2i n) = (ln n) 2 n = n ln n.
i=1
2

Subtracting (2) from (1) gives

n
X n
X
ln Gnn = (ln i ln n)(2i n) 2 ln i + n ln n.
i=1 i=1

Dividing by n2 we get
n   
1 1X i i
(3) ln G1/n
n = ln G n
n = ln 2 1 + R(n),
n2 n i=1 n n

where
n
ln n 2 X ln n
R(n) = 2 ln i + .
n n i=1 n
Since
n
ln n 2 X 3 ln n
|R(n)| + 2 ln n ,
n n i=1 n

3
 1/n
we have limn R(n) = 0, so the term R(n) has no effect on the limit of ln Gn , and we can therefore ignore it.
R1
The remaining term on the right of (3) can be interpreted as a Riemann sum for the integral 0 (ln x)(2x 1)dx, and
evaluating this integral gives the desired limit:
n   
1X i i
lim ln G1/n
n = lim ln 2 1
n n n n n
i=1
Z 1
= (ln x)(2x 1)dx
0
1 Z 1 1
= (x2 x) ln x (x2 x) dx

0 0 x
Z 1
1
= (x 1)dx = .
0 2
1/n
Exponentiating, we get limn Gn = e1/2 , as claimed.