Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

The 76th William Lowell Putnam Mathematical Competition
Saturday, December 5, 2015

A1 Let A and B be points on the same branch of the hyperbola xy = 1
...
Show that the region bounded by the hyperbola and the chord AP has
the same area as the region bounded by the hyperbola
and the chord PB
...

Find an odd prime factor of a2015
...

A4 For each real number x, let
f (x) =

four numbers off the list
...
Continue
in this way, crossing off the three smallest remaining
numbers and their sum, and consider the sequence of
sums produced: 6, 16, 27, 36,
...

B3 Let S be the set of all 2 × 2 real matrices


a b
M=
c d
whose entries a, b, c, d (in that order) form an arithmetic
progression
...

B4 Let T be the set of all triples (a, b, c) of positive integers
for which there exist triangles with side lengths a, b, c
...
What is the largest real number L such that
f (x) ≥ L for all x ∈ [0, 1)? (As usual, bzc denotes the
greatest integer less than or equal to z
...
Show that Nq is odd if and only if q is
of the form pk with k a positive integer and p a prime
congruent to 5 or 7 modulo 8
...
Suppose that A, B, and M are
n×n matrices with real entries such that AM = MB, and
such that A and B have the same characteristic polynomial
...

B1 Let f be a three times differentiable function (defined
on R and real-valued) such that f has at least five distinct real zeros
...

B2 Given a list of the positive integers 1, 2, 3, 4,
...

B5 Let Pn be the number of permutations π of {1, 2,
...
, n}
...

B6 For each positive integer k, let A(k)
√ be the number of
odd divisors of k in the interval [1, 2k)
...

k

Solutions to the 76th William Lowell Putnam Mathematical Competition
Saturday, December 5, 2015
Manjul Bhargava, Kiran Kedlaya, and Lenny Ng

A1 First solution: Without loss of generality, assume that
A and B lie in the first quadrant with A = (t1 , 1/t1 ), B =
(t2 , 1/t2 ), and t1 < t2
...

1
2 =

2 1/t 1/t 1/t 
2t1t2
1

2

When t1 ,t2 are fixed, this is maximized when t + t1t2 /t
is minimized,
which by AM-GM exactly holds when
√
t = t1t2
...

Similarly, the area of the region bounded by the√hypert2
bola and PB is 2t
− 2tt 2 − log tt2 , which at t = t1t2 is
p
2 −t1
also 2t√
t t − log( t2 /t1 ), as desired
...
We may thus rescale the picture so that A, B are symmetric across the line y = x, with A above the line
...
Consequently, P = (1, 1) achieves the maximum area, and the
desired equality is obvious by symmetry
...

A2 First solution: One possible√answer is 181
...
Now note that if k is an odd positive integer
kn +β kn
(k−1)n −α (k−2)n β n +
and an 6= 0, then aaknn = αα n +β
n =α
· · · − α n β (k−2)n + β (k−1)n
...
Applying this to n = 5 and k = 403, we
find that a2015 is divisible by a5 = 362 and thus by 181
...
Since a−1 = 2,
we may see by induction that a−n = an for all n
...
, a0 = 1, a
contradiction
...
In particular, if k is
odd, then p also divides akm ; we thus conclude (again)
that a2015 is divisible by a5 = 362 and thus by 181
...

Remark: One can find other odd prime factors of a2015
in the same manner
...
(The prime factorizations were computed using the Magma computer algebra
system
...
Dividing
a2015 by the product of the primes appearing in this list
yields a number N of 824 decimal digits which is definitely not prime, because 2N 6≡ 2 (mod N), but whose
prime factorization we have been unable to establish
...

One thing we can show is that each prime factor of N is
congruent to 1 modulo 6 × 2015 = 12090, thanks to the
following lemma
...
Let n be an odd integer
...
(By either solution of the
original problem, p also does not divide am for any positive
integer m < n
...
We first check that p ≡ 1 (mod 3)
...
If p ≡ 2 (mod 3), then q = p2 and
n
α and β are conjugate in p; consequently,
the
√
√ equality α =
n
n
n
−β in Fq2 means that α = c 3, β = −c 3 for some c ∈
F p
...


2
By the previous paragraph, α and β may be identified with
elements of F p , and we have (α/β )n ≡ −1, but the same does
not hold with n replaced by any smaller value
...

A3 The answer is 13725
...
To see this, write
d = gcd(a, n) and a = da1 , n = dn1 with gcd(a1 , n1 ) =
1
...
, n1 a1 modulo n1 is a permutation
of 1, 2,
...
, ω n1 a1
is a permutation of ω, ω 2 ,
...

Now since the roots of zn1 − 1 are ω, ω 2 ,
...
Setting z = −1 and
1
using the fact that n1 is odd gives ∏nb=1
(1 + ω b ) = 2
...


From the claim, we find that
2015 2015

log2

!
2πiab/2015

∏ ∏ (1 + e

)

a=1 b=1
2015

=

!

2015

∑ log2 ∏ (1 + e

a=1

2πiab/2015

)

b=1

2015

=

∑ gcd(a, 2015)
...
Thus
2015

∑ gcd(a, 2015) = ∑

a=1

d · φ (2015/d)
...

When (p, q, r) = (5, 13, 31), this is equal to 13725
...
, ω 2(n1 −1) is a permutation of ω,
...

Remark: The function f (n) = ∑d|n d · φ (n/d) is multiplicative: for any two coprime positive integers m, n, we
have f (mn) = f (m) f (n)
...

A4 The answer is L = 4/7
...
Note that for T =
{1, 4, 7, 10,
...

We first show by contradiction that for any x ∈ [0, 1),
f (x) ≥ 4/7
...
Assume f (x) < 4/7; then the smallest
integer in one of Sx , T but not in the other is in T
...

Since the difference between consecutive terms in nx,
(n + 1)x, (n + 2)x is x < 1, we conclude that bnxc =
b(n + 1)xc = b(n + 2)xc and so x < 1/2
...

It remains to show that 4/7 is the greatest lower bound
for f (x), x ∈ [0, 1)
...

It follows that Sx is a subset of S = {1, 4, 7,
...
}, and so f (x) = F(Sx ) ≤
f (S) = (1/2 + 1/24 + · · · + 1/23n+1 ) + 1/23n+1
...

A5 First solution: By inclusion-exclusion, we have


bq/4c
Nq = ∑ µ(d)
d
d|q


q/d
= ∑ µ(d)
4
d|q


q/d
≡
(mod 2),
∑
4
d|q squarefree
where µ is the M¨obius function
...


3
So Nq is odd if and only if q has an odd number of
squarefree factors q/d congruent to 5 or 7 (mod 8)
...
Hence q must have an even number of factors
that are congruent to 5 or 7 (mod 8), and so Nq is even
in this case
...
Either way,
we see that exactly two of the four residues are congruent to 5 or 7 (mod 8)
...

If q = 1, then Nq = 0 is even
...
In this case, q has two squarefree
factors, 1 and p, of which exactly one is congruent to 5
or 7 (mod 8)
...

Second solution:
Consider the set S of all integers in {1,
...
Then the product of
all elements in S is
2φ (q)/2

∏

a
...
Then for each 1 ≤ a ≤
(q − 1)/2 with (a, q) = 1, T contains exactly one element from {a, −a}: if −2r ≡ 2s (mod q) for some
r, s ∈ {1,
...
Thus the product
of all elements in T is
(−1)n

∏

a,

1≤a≤(q−1)/2
(a,q)=1

where n denotes the number of elements of S greater
than (q − 1)/2
...

However, note that the number of elements of S less
than (q − 1)/2 is equal to Nq , since dividing these numbers by 2 gives exactly the numbers counted by Nq
...
, q − 1} relatively prime to q come in pairs
{a, q − a} in each of which exactly one member is even
...


If q = 1, then Nq is even
...
Finally, suppose that q is a prime power pk with p odd
and k positive
...
e
...
But recall that −2 is a quadratic residue modulo p if and only if p ≡ 1, 3 (mod 8)
...

We conclude that for any odd integer q ≥ 1, the quantity
Nq is odd if and only if q = pk with k positive and p a
prime that is 5 or 7 (mod 8)
...

A6 First solution: (by Noam Elkies) Using row and column operations, we may construct invertible matrices
U,V such that U −1 MV is a block diagonal matrix of
the form


I 0

...
Form
the corresponding block decompositions






A11 A12
B11 B12
X11 X12
A0 =
, B0 =
,X0 =

...
Since A11 = B11 ,
it follows that A22 and B22 have the same characteristic
polynomial
...
(By similar arguments, A − MX and B − XM
have the same characteristic polynomial
...
e
...

For fixed A, B, M, the stated result is a polynomial identity in t and the entries of X
...
Since AM =
MB, we also have At M = MBt , so At MBt−1 = M
...

Remark: One can also assert directly that det(1 −
MBt−1 X) = det(1 − XMBt−1 ) using the fact that for any
square matrices U and V , UV and VU have the same
characteristic polynomial; the latter is again proved by
reducing to the case where one of the two matrices is
invertible, in which case the two matrices are similar
...

This will imply that A − MX and B − XM have the same
characteristic polynomial, yielding the desired result
...
By hypothesis, Ak
and Bk have the same characteristic polynomial, so
Trace(Ak ) = Trace(Bk )
...
, im of
nonnegative integers,
Trace(Ai1 MXAi2 MX · · · Aim−1 MXAim )
= Trace(Bi1 XMBi2 XM · · · Bim−1 XMBim )
...

Then apply the relation AM = MB repeatedly to commute M past A, to obtain
Trace(MBim +i1 XMBi2 XM · · · XMBim−1 X)
...

Remark: The conclusion holds with R replaced by an
arbitrary field
...
g
...
The third solution
only applies to fields of characteristic 0 or positive characteristic greater than n
...
However, it is not clear how
to make such an argument work
...
Then g has at least 5 distinct real
zeroes, and by repeated applications of Rolle’s theorem,
g0 , g00 , g000 have at least 4, 3, 2 distinct real zeroes, respectively
...

B2 We will prove that 42015 is such a number in the sequence
...
, and let
an , bn , cn be the summands of sn in ascending order
...
, 10n +
10 by removing one of 10n + 5, 10n + 6, 10n + 7
...

These statements follow by induction from the following simple observations:
– by computing the table of values
n
0
1
2

an
1
4
8

bn
2
5
9

cn
3
7
10

we see that (a)0 holds;

sn
6
16
27

5
– (a)n implies (b)n ;
– (a)n and (b)1 ,
...

To produce a value of n for which sn ≡ 2015
(mod 10000), we take n = 3m + 1 for some nonnegative integer m for which s3m+1 = 30m + 15
...
By taking m = 1400, we ensure
that m ≡ 2 (mod 3), so sm = 10m + 7; this ensures that
sn does indeed equal 30m + 15 = 42015, as desired
...

Define the function on nonnegative integers
f (n) = s3n+1 − (30n + 16)
which takes values in {−1, 0, 1}; we then have


n ≡ 0 (mod 3)
0
f (n) = − f ((n − 1)/3) n ≡ 1 (mod 3)


−1
n ≡ 2 (mod 3)
...

In this notation, we have sn ≡ 2015 (mod 10000) if and
only if n = 3m + 1 for some nonnegative integer m for
which m ≡ 400 (mod 1000) and f (m) = −1
...

B3 First solution: Any element
be
written as M =

of S can−1
αA + β B, where A = 11 11 , B = −3
1 3
, and α, β ∈ R
...

We claim that these are also the only matrices in S
satisfying the given condition
...
Let C =
−1 1/ 2


1/2 −1/2
verse C−1 = 1/√2 1/√2
...
Now suppose


1
that M k is in S with k ≥ 2
...
On the
other hand, from the expression for
 2D, an easy
 inducγ pk−1 γ pk
k
k
tion on k shows that D = (2α)
γ pk pk+1 , where
pk is defined inductively by p0 = 0, p1 = 1, pk+2 =
γ 2 pk + pk+1
...

Remark: A variant of this solution can be obtained by
diagonalizing the matrix M
...
If s = 0, then clearly all powers of M are
in xS
...

We now assume rs 6= 0, and show that in that case M
cannot be in S
...
By repeatedly using the
relation M 2 = 2rM + 8s2 I, we see that for each positive
integer, we have M k = tk M + uk I for unique real constants tk , uk (uniqueness follows from the independence
of M and I)
...

On the other hand, we claim that if k > 1, then rtk > 0
and uk > 0 if k is even, and tk > 0 and ruk > 0 if k is
odd (in particular, uk can never be zero)
...
Assuming the claim for k, and multiplying both sides of the
relation M k = tk M + uk I by M, yields
M k+1 = tk (2rM + 8s2 I) + uk M = (2rtk + uk )M + 8s2tk I,
implying the claim for k + 1
...
com, user
hoeij) Once one has uk = 0, one can also finish using
the relation M · M k = M k · M
...
For fixed b, c,
there is a triangle of side lengths a, b, c if and only if
|b − c| < a < b + c
...

∑
3b 5c
b,c 3 5
b,c
a=|b−c|+1
We write this as S = S1 +S2 where S1 sums over positive
integers b, c with b ≤ c and S2 sums over b > c
...

231

6
Similarly,
2b+c − 2b−c+1
3b 5c
c=1 b=c+1
 ∞  b !
 c
∞
2
2
2
=∑
− c
∑ 3
5
10
c=1
b=c+1
  c+1
∞  c
2
2
2
− c 3
=∑
5
10
3
c=1






c
∞
4
1 c
=∑ 2
−4
15
15
c=1
∞

S2 =

=

∞

∑ ∑

be the number which has n − 1, n consecutively in that
order, but not at the beginning or end
...
Therefore
Pn = 2(Un +Vn +Wn + Tn + Sn )
...

77

We conclude that S = S1 + S2 =

Un+1 = Un +Wn + Tn ,
Vn+1 = Un ,
Wn+1 = Wn ,
Tn+1 = Vn ,
Sn+1 = Sn +Vn
...


Second solution: Recall that the real numbers a, b, c
form the side lengths of a triangle if and only if
s − a, s − b, s − c > 0

s=

a+b+c
,
2

and that if we put x = 2(s−a), y = 2(s−b), z = 2(s−c),
a=

y+z
z+x
x+y
,b =
,c =

...
We may therefore
write the original sum as
2(y+z)/2
2(y+z)/2
+

...

21

=

B5 The answer is 4
...

We write
the permutations π counted by Pn as sequences
π(1), π(2),
...
Let Un be the number of permutations counted by Pn that end with n − 1, n; let Vn be the
number ending in n, n − 1; let Wn be the number starting
with n − 1 and ending in n − 2, n; let Tn be the number
ending in n − 2, n but not starting with n − 1; and let Sn

Also, it is clear that Wn = 1 for all n
...
Hence for
all n ≥ 2,
Pn+5 = 2(Un+5 +Vn+5 +Wn+5 + Tn+5 + Sn+5 )
= 2((Un+4 +Wn+4 + Tn+4 ) +Un+4
+Wn+4 +Vn+4 + (Sn+4 +Vn+4 ))
= Pn+4 + 2(Un+4 +Wn+4 +Vn+4 )
= Pn+4 + 2((Un+3 +Wn+3 + Tn+3 ) +Wn+3 +Un+3 )
= Pn+4 + Pn+3 + 2(Un+3 −Vn+3 +Wn+3 − Sn+3 )
= Pn+4 + Pn+3 + 2((Un+2 +Wn+2 + Tn+2 ) −Un+2
+Wn+2 − (Sn+2 −Vn+2 ))
= Pn+4 + Pn+3 + 2(2Wn+2 + Tn+2 − Sn+2 −Vn+2 )
= Pn+4 + Pn+3 + 2(2Wn+1 +Vn+1
− (Sn+1 +Vn+1 ) −Un+1 )
= Pn+4 + Pn+3 + 2(2Wn +Un − (Sn +Vn ) −Un
− (Un +Wn + Tn ))
= Pn+4 + Pn+3 − Pn + 4,
as desired
...
For example, Karl
Mahlburg suggests writing
Pn = 2Pn0 ,

Pn0 = Q0n + R0n

where Pn0 counts those permutations counted by Pn for
which 1 occurs before 2, and Q0n counts those permutations counted by Pn0 for which π(1) = 1
...
Hence the
difference converges to zero as n → ∞; that is, S1 converges and equals S2
...
, 6, 4, 2
...
We begin by writing

corresponding to the cases containing 3, 1, 2, 4 (where
removing 1 and reversing gives a permutation counted
by R0n−1 ); and where 4 occurs before 3, 1, 2 (where removing 1, 2 and reversing gives a permutation counted
by Q0n−2 )
...
S
...
2, 150–153
...
The sequence of the Pn
also appears as entry A003274 in the On-line Encyclopedia of Integer Sequences (http://oeis
...

B6 (from artofproblemsolving
...
Note first that the
sum does not converge absolutely, so we are not free to
rearrange it arbitrarily
...

Setting these issues aside momentarily, note that the elements of the set counted by A(k) are those odd positive integers
d for which m = k/d is also an integer and
√
d < 2dm; if we write d = 2` − 1, then the condition
on m reduces to m ≥ `
...

Lemma 1
...
be a sequence of continuous functions on [0, 1] such that for each x ∈ [0, 1], we have
f0 (x) ≥ f1 (x) ≥ · · · ≥ 0
...

Proof
...


1
S2 = ∑
`=1 2` − 1
∞

∞
1
(−1)m−1
S2 := ∑
,
∑
m
`=1 2` − 1 m=`
∞

=

so the outer sum converges absolutely
...

m
+1c

The expression on the right is bounded above in absolute value by the sum ∑`(2`−1)≤n n1 , in which the number

∞

0

m=`

∑ (−1)

Z 1
(−t)`−1
0

!
m−1 m−1

1+t

t

dt

dt
...

16
Z 1

To see that S1 converges to the same value as S2 , write

Z 1

Since the outer sum is absolutely convergent, we may
freely interchange it with the integral:
!
Z 1 ∞
1 (−t)`−1
S2 =
dt
∑
0
`=1 2` − 1 1 + t
!
Z 1
∞
1
(−1)`−1t `−1/2
√
=
dt
∑ 2` − 1
t(1 + t) `=1
0
=

∞
1
(−1)m−1
S2,n = ∑

...
In fact a bit more is true: we have


 ∞ (−1)m−1  1


∑
< ,
m=`
 `
m

k=1

fn (t) dt =

∞

and we would like to rearrange this to

n

t m−1 dt

---