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 2017 Putnam Competition Problems and Solutions
A1
...

Which positive integers are not in S?
(The set S is “smallest” in the sense that S is contained in any other such set
...
The positive integers that are not in S are 1 and the multiples of 5
...
First note that by combining conditions c) and b), n ∈ S implies n+5 ∈ S
...
Thus,
because 542 ≡ 1 (mod 5), all sufficiently large positive integers that are ≡ 1 (mod 5)
are in S
...
Then the sequence
a, a2 , a4 , a8 , a16 ,
...

Thus the sequence contains elements of S, and by repeated application of condition
b) it follows that a ∈ S
...

A2
...
Show that, whenever n is a positive integer, Qn (x) is equal to a
polynomial with integer coefficients
...
Let a sequence of polynomials be defined by P−1 (x) = 0, P0 (x) = 1, and
Pn (x) = xPn−1 (x) − Pn−2 (x) for all n ≥ 1
...
Note that
for all n ≥ 2,

 


Pn (x) −Pn−1 (x)
x −1
Pn−1 (x) −Pn−2 (x)
=
= ···
Pn−1 (x) −Pn−2 (x)
1 0
Pn−2 (x) −Pn−3 (x)

n−1 

x −1
P1 (x) −P0 (x)
=
1 0
P0 (x) −P−1 (x)

n
x −1
=

...

Pn−2 (x)

But this is precisely the defining recurrence relation for Qn (x), and since
P0 (x) = Q0 (x) and P1 (x) = Q1 (x), we are done
...
To show that the Qn (x) are polynomials with integer coefficients, we
will show that they also satisfy the simpler recurrence Qn (x) = x Qn−1 (x) − Qn−2 (x)
...

Q0 (x)

Assuming that Qn (x) = x Qn−1 (x) − Qn−2 (x) for n = N − 1, define
RN (x) = x QN −1 (x) − QN −2 (x)
...

QN −2 (x)

A3
...
For every positive
integer n, define
Z b
(f (x))n+1
In =
dx
...
is an increasing sequence with lim In = ∞
...
First consider
Z b
Z b
(f (x))n+1
(f (x))n
In − In−1 =
dx
−
dx
n−1
(g(x))n
a
a (g(x))
Z b
(f (x))n+1 − g(x)(f (x))n
=
dx
(g(x))n
a




Z b


(f (x))n − (g(x))n f (x) − g(x)
=
+ f (x) − g(x) dx
n
(g(x))
a




Z b
Z b
n


(f (x)) − (g(x))n f (x) − g(x)
=
dx
+
f
(x)
−
g(x)
dx
...
The second integral is zero, because the integrals
of f and g over the interval are equal
...

Next, we claim that there exist a subinterval I ⊆ [a, b] of positive length L and
f (x)
a constant M > 1 so that
≥ M for all x ∈ I
...
But in the latter case there must also be a point x ∈ [a, b]
(and hence a subinterval of [a, b]) where f (x) > g(x), otherwise we would have

Rb

Rb
f
(x)
dx
<
g(x) dx
...

g(x)
Finally,
Z b
Z
(f (x))n+1
(f (x))n+1
In =
dx
≥
dx
n
(g(x))n
a
I (g(x))
n
Z 
f (x)
f (x) dx
=
I g(x)
Z
n
≥M
f (x) dx
...

n→∞

A4
...
, 10
...
4
...
4
...
Let the student scores in non-decreasing order be
0 = s1 ≤ s2 ≤ · · · ≤ s2N = 10,
and let the sum of all the scores be S
...
4) =
, so N is divisible by 5 and S is even
...
Now let t = a1 + a2 + · · · + aN ,
and note that t has the same parity as S, so t is also even
...
Then for the group of N students whose
scores are s2 , s4 ,
...
, s2N −1 , the sum of their scores is
s2 + s4 + · · · + s2n + s2n+1 + · · · + s2N −1
= (a1 + s1 ) + · · · + (an + s2n−1 ) + s2n+1 + · · · + s2N −1
= (a1 + · · · + an ) + (s1 + s3 + · · · + s2N −1 )


1
= t + 2s1 + 2s3 + · · · + 2s2N −1
2


1
= (s1 + s3 + · · · + s2N −1 ) + ((a1 + s1 ) + · · · + (aN + s2N −1 )
2
1
1
= (s1 + s3 + · · · + s2N −1 + s2 + · · · + s2N ) = S = N (7
...
4 (and thus the average score for the complementary group is also 7
...

Solution 2
...
, s10m and thus satisfy s1 + · · · + s10m = 74m
...
If a term in S1 is exactly one less than a term in S2 ,
then we can exchange those terms and make δ smaller, contradiction
...
must all appear in S1
...
Then 5ma ≤ S1 < S2 ≤ 5mb, so b > a, so b − 1 must appear in S1 and
we can exchange b − 1 from S1 and b from S2 after all to reduce δ, contradiction
...
Each of the integers from 1 to n is written on a separate card, and then the cards
are combined into a deck and shuffled
...
choosing one card at random from the deck
...
) After a card is chosen, that card and all highernumbered cards are removed from the deck, and the remaining cards are reshuffled
before the next turn
...

Show that for each of the three players, there are arbitrarily large values of n for
which that player has the highest probability among the three players of winning the
game
...
For every positive integer n, let An , Bn , Cn denote the probabilities that
players A, B, C (respectively) win the game for that value of n
...

For n > 1, if player A chooses the card numbered k with k > 1, the game then
proceeds like the original game with k − 1 cards, except that B now chooses first, C
chooses second, and A takes on C’s original role, choosing third
...

n
n
n
Multiplying through by n and then subtracting the equations for n from those for
n + 1 yields
(n + 1) An+1 − n An = Cn , (n + 1) Bn+1 − n Bn = An , (n + 1) Cn+1 − n Cn = Bn
...

n+1 0 1 n
Cn+1
Cn


n 0 1
The eigenvalues of the matrix  1 n 0  are the roots of (n − λ)3 + 1 = 0, so if we
0 1 n
2πi/3
let ω = e
, they are given by n − λ = −1, n − λ = −ω, n − λ = −ω 2
...
In particular, the eigenvectors are the same for each n, and so we can
use them, together with


 
An+1
An
Bn+1  = Mn Bn  ,
Cn+1
Cn
to find expressions for the probabilities An , Bn , Cn , as follows:
 
 
 
 
1
1
1
1
0 = 1 1 + 1 ω 2  + 1  ω  , so
3 1
3 ω
3 ω2
0
 

1
An
Bn  = Mn−1 Mn−2 · · · M1 0
0
Cn
 
 
1
1
1
1



= Mn−1 Mn−2 · · · M1 1 + Mn−1 Mn−2 · · · M1 ω 2 
3
3
1
ω
 
1
1

+ Mn−1 Mn−2 · · · M1 ω 
3
ω2
 
 
 
n−1
n−1
1
1
1
2
Y
Y
1  1
k + ω  2 1
k+ω  
1 +
+
=
· ω
· ω
...
Then, because ω 2 = ω, we have
k
+
1
k=1

1
1
An = (1 + P + P ) = (1 + 2 Re(P )),
3
3
1
1
Bn = (1 + P ω + P ω) = (1 + 2 Re(P ω)),
3
3
1
1
Cn = (1 + P ω + P ω) = (1 + 2 Re(P ω))
...
Specifically, An is largest when Arg(P ) is in the interval
[−π/3, π/3], Bn is largest when Arg(P ) is in [π/3, π], and Cn is largest when Arg(P )

is in [−π, −π/3]
...

Arg
arctan
k
+
1
2k
−
1
k=1
k=1
n−1
X

Because arctan x ∼ x as x → 0, we have
√
√
3
3/2
arctan
∼
as k → ∞,
2k − 1
k
so the values of arg(P ) above are the partial sums of a divergent series, but the
difference between successive partial sums tends to 0
...

A6
...
, 30
...
220 · 310 = 1210 = 61, 917, 364, 224
...
Let F = F3 = {0, 1, 2} be the field with 3 elements; let those elements
correspond to “red”, “white”, and “blue” respectively
...
Label the 20
faces of the icosahedron 1, 2,
...

Using these functions, we can define a linear transformation T : V → F 20 by
T (v) = (f1 (v), f2 (v),
...

The condition that face i has two edges of the same color and a third edge of a
different color is easily checked to be equivalent to fi (v) 6= 0, so we are looking for
the cardinality of the inverse image under T of the subset {1, 2}20 of F 20
...
By symmetry, it is enough to do
this for a single face
...
Color all other edges of
the icosahedron with color 0, except for the edge connecting v4 and v5 which gets
color 1
...
The one exception is the face
which is not adjacent to v but which does have v4 v5 among its edges; for that face,
the sum of the colors is 1
...
But we know that

dim ker(T ) + dim im(T ) = dim V = 30, so dim ker(T ) = 30 − 20 = 10 and ker(T )
has 310 elements; the answer follows
...
)

B1
...
Prove that L1 and L2 intersect if and
only if, for every real number λ 6= 0 and every point P not on L1 or L2 , there exist
# »
# »
points A1 on L1 and A2 on L2 such that P A2 = λ P A1
...
To show “if”, take λ = 1 and any point P not on L1 or L2
...
To show “only if”,
assume L1 and L2 have the directions of the vectors v1 =< a1 , b1 >, v2 =< a2 , b2 >
respectively and intersect at the point (x0 , y0 )
...
Then there are points A1 , A2 on L1 , L2 respectively with P A2 = λ P A1 if and
only if there are real numbers t1 , t2 (the parameter values for A1 , A2 ) such that
x0 + a2 t2 − p = λ(x0 + a1 t1 − p) and y0 + b2 t2 − q = λ(y0 + b1 t1 − q)
...

Comment
...
In fact, if P is on Li , then the point A3−i on the other line will always
be the intersection point (x0 , y0 ), whereas the point Ai varies with λ - unless P itself
is the intersection point, in which case A1 = A2 = P for every λ
...
To show “if”, proceed as in the first solution
...
Let
M1 , M2 be the lines through P parallel to L1 , L2 respectively; note that these lines
divide the plane into four “quadrants”, one of which contains the intersection point
Q
...
Except when K = M1
and when K = M2 , the line K will intersect the lines L1 , L2 in points A1 , A2 , and
# »
# »
there will be a nonzero real number λ(K) such that P A2 = λ(K) · P A1
...
It will be
positive when the line K passes through the “quadrant” containing Q, approaching
0 as K approaches the line M1 (so that the intersection point A1 approaches infinity)
and ∞ as K approaches M2
...
By the intermediate value theorem, it follows that
λ(K) takes on all real values, and the claim follows
...
Suppose that a positive integer N can be expressed as the sum of k consecutive
positive integers
N = a + (a + 1) + (a + 2) + · · · + (a + k − 1)
for k = 2017 but for no other values of k > 1
...
a = 16
...
If we do have N = a + (a + 1) + (a + 2) + · · · + (a + k − 1) with an
integer a > 0, then we have N = k2 (2a + k − 1)
...
Now suppose a + 1008 has some odd factor s > 1,
so N = s(2017t), say
...

So if a + 1008 has an odd factor s > 1, then s ≥ 2017 and thus N ≥ 20172
...
We now show that this integer does have the specified
property
...
If k is greater than 2017
and divisible by 2017, then k also has at least one factor 2, so 2a + k − 1 is odd and
greater than 1, so not a power of 2, contradiction
...
Thus
the only possible k > 1 is k = 2017, for which N = 2017 · 1024 is the sum of 2017
consecutive integers starting with 16
...

B3
...


i=0

Show that if f (2/3) = 3/2, then f (1/2) must be irrational
...
Note that by the comparison test with the geometric series

∞
P

|x|i , the

i=0

power series f (x) is absolutely convergent for x ∈ (−1, 1); in particular, f (1/2) is a
∞
P
real number
...
Because f (1/2) =
ci ( 21 )i , the binary
i=0

expansion of this number reads c0
...
of its binary digits is eventually periodic
...
Then we have
=

p( 23 )
3k p( 32 )
3
2
= f( ) =
=

...


B4
...

2
3
4
5
6
7
8
9
10

(As usual, ln x denotes the natural logarithm of x
...
ln2 (2)
...
First consider the series
ln 1 ln 2 ln 3 ln 4
−
+
−
+ ··· ,
1
2
3
4
ln n
which converges by the alternating series test
...
) Let a be the sum of this series,
and let S be the desired sum
...

B5
...
Find positive integers a > b > c, with a as
small as possible, such that there exists a triangle with side lengths a, b, c that has
exactly two distinct equalizers
...
a = 9, b = 8, c = 7
...
As usual, let A be the vertex of the triangle opposite the side of length a,
etc
...
Then the equalizer intersects side AB at a point Y and side AC at a point
Z; say AY has length λc and AZ has length µb, so λ, µ ∈ [0, 1]
...
Meanwhile, the “equal perimeter” property
of the equalizer implies that λc + µb = (1 − λ)c + a + (1 − µ)b, so λc + µb = a+b+c

...

2
2

If we denote the polynomial on the left-hand side of this equation by p(λ), then
p( 21 ) = b−a
< 0 and p(1) = c−a
< 0, so the entire interval [ 21 , 1] is between the roots
4
2
of the quadratic polynomial (which is positive for large |λ|)
...

Now suppose that an equalizer separates vertex B from side AC
...

2
2
c−b
> 0 while p(1) = 2 < 0, so there will be exactly one root of

p(λ) = cλ2 −
This time, p( 21 ) =

a−b
4
interval [ 21 , 1],

p(λ) in the
and thus there will be exactly one equalizer that intersects
both the shortest and the longest side of T
...
If the usual side lengths are λb, µa, we get, after a similar calculation,
a+b+c
a
λ + = 0
...
Because we have exactly one
equalizer from an earlier case, there will be two distinct equalizers in all for T if and
only if p(λ) has a double root
...

2
2
So we are looking for a solution of this Diophantine equation in positive integers,
with a > b > c and a as small as possible
...
Then because 8ab
is a perfect square, there are positive integers m and n so that either a = 2m2 , b = n2
or a = m2 , b = 2n2
...
In the second case a
is odd, so a ≥ 9, so the smallest value of a that might be possible is 9
...
For b = 2 we would have (11 + c)2 = 144, so c = 1, but there is no triangle
with side lengths 9, 2, 1
...
There is a triangle with side lengths 9, 8, 7, and we have found the answer
...
Find the number of ordered 64-tuples (x0 , x1 ,
...
, x63 are
distinct elements of {1, 2,
...

2016!
Answer
...

1953!

Solution
...

Because 2017 is prime, we can think of the xi as elements of the field F2017 , and we
then have a special case of the following problem:
Given positive integers a1 , a2 ,
...
, xk are distinct
...

(2017 − k)!
In our particular case, we have k = 64, leading to the numerical answer given above
...
For k > 1, first note that because a1 ,
...
Therefore, given any distinct x1 ,
...
, xk ) is a solution;
however, that xk may not be distinct from all of x1 ,
...

The number of choices for an ordered (k − 1)-tuple (x1 ,
...
So to get the answer,
ments from F2017 is 2017 · 2016 · · · (2019 − k) =
(2018 − k)!
we need to subtract from this the number of solutions to a1 x1 + a2 x2 + · · · + ak xk = 0
for which x1 ,
...
, xk−1
...
, xk−1 to the equation
a1 x1 + a2 x2 + · · · + (ai + ak )xi + · · · + ak−1 xk−1 = 0
...
Because i can be any of the numbers 1,
...
, xk ∈ F2017 is
2017!
− (k − 1)f (k − 1) =
(2018 − k)!


2017!
2016!
k−1
=
− (k − 1)
− (−1)
· 2016 · (k − 2)!
(2018 − k)!
(2018 − k)!
(2018 − k) · 2016!
− (−1)k · 2016 · (k − 1)!
=
(2018 − k)!
2016!
=
− (−1)k · 2016 · (k − 1)!
(2017 − k)!
= f (k), completing the induction

---