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

---

William Lowell

maa
...
org/putnam

PUTNAM
Mathematical Competition

Problems for
Session B

The 81st William Lowell Putnam Mathematical Competition

A1
...

(ii) N has at most 2020 decimal digits
...

Answer
...

Solution 1
...
Note that 2020 = 20 · 101, so to satisfy (i) the integer
N must be divisible by 101 and end in at least two zeros (so k ≥ 2)
...
A quick check shows that M ≡ 0, 9, 99, 90 mod 101 when j ≡ 0, 1, 2, 3
mod 4
...
(One can see directly that the conditions k ≥ 2, 4|j
are necessary and sufficient by noting that 101 divides 1111 but not 1, 11 or 111
...
The total number of integers N satisfying all the conditions
is therefore
504
X

(2019 − 4m) = 2019 · 504 − 4 ·

m=1

504 · 505
= 504 · (2019 − 1010) = 504 · 1009 = 508536
...
As in the first solution, it is straightforward to show that the acceptable
numbers N are those for which there are at most 2020 decimal digits, consisting of j ones
with 4|j followed by k zeros with k ≥ 2
...
We now show that the set of such strings is in bijective


correspondence with a set of size 1009
= 508536
...

Then any choice of 2 of these 1009 pairs corresponds to a unique string of the desired form,
as follows
...

|{z}
Choose

Choose

If the two chosen pairs are separated by an odd number of pairs, do the same except for
replacing the chosen pairs by z1 and 10, respectively, for example:
xx |{z}
xx |{z}
xx |{z}
xx |{z}
xx · · · 7→ zz | z1 | 11 | 10 | 00 · · ·
...
Erasing the digits
z and restoring the two zeros that were removed at the end of the string, we get every
acceptable number N exactly once from some choice of 2 of the 1009 consecutive pairs
...
As in the first solution, the positive integers N satisfying conditions (i) and
(iii) have j ones followed by k zeros, with 4|j, j ≥ 1, and k ≥ 2
...

·
1 − x4 1 − x
m=0
m

Hence the generating function for the number Bm =

P

bk of such integers with at most

k≤m

m digits is
∞
X

∞
X
1
x6
x6 (1 + x + x2 + x3 )2
Bm x =
·
bm x m =
=

...

2
2

A2
...
Evaluate
k
X
j=0

k−j

2




k+j

...
22k = 4k
...
Consider lattice paths of length 2k + 1 that begin from the origin, and where
each step is either of the form (x, y) 7→ (x + 1, y) or (x, y) 7→ (x, y + 1); thus these paths will
be in the first quadrant
...
So there are
22k such paths that have at least k + 1 “right steps” among their 2k + 1 steps
...
There are exactly k+j
j
paths from (0, 0) to (k, j), and 2k−j possible paths after (k +1, j)
...


Solution 2
...
Then using basic
properties of binomial coefficients, one finds that for k ≥ 0,


k+1
X
k+1−j k + 1 + j
S(k + 1) =
2
j
j=0

 

k+1
X
k+j
k+j
k+1−j
+
=
2
j
j−1
j=0

 X


k+1
k
X
k−j k + j
k−j k + j + 1
=2
2
+
2
j
j
j=0
j=0





2k + 1
1
2k + 2
= 2 S(k) +
+
S(k + 1) −
k+1
2
k+1




1
2k + 1
1 2k + 2
= 2 S(k) + S(k + 1) +
−
2
k+1
2 k+1
1
= 2 S(k) + S(k + 1)
...

Solution 3
...

k

k

But this coefficient can also be expressed as

k  
k 
X
X
k
2k + 1
1
k+1
2
−
= 2k+1 · 2k − · 22k+1 = 22k = 4k ,
2
j
j
j=0
j=0
as claimed
...
Let a0 = π/2, and for n ≥ 1, let an = sin(an−1 )
...

Answer
...

√
Solution 1
...

Note that on the interval (0, π/2), sin(x) is increasing and sin x > x − x3 /6 by Taylor’s
theorem with remainder (because the fifth derivative, cos x, is positive on the interval)
...

n
n 6
n
On the other hand,

√
√
1
1
n+1− n
√ −√
= √ √
n
n+1
n n+1
1
= √
√ √ √
( n + 1 + n) n n + 1

3
1
1
1
√
,
> √ √ √ =
6
(3 n) n(2 n)
n

so
an+1 > √
completing the induction
...

n=1 n

Solution 2
...
By the continuity of the sine function we must have
L = sin(L), so L = 0
...

3
x→0
x
x
sin x
6
3
We can then apply the Stolz-Ces`aro theorem to get
1/a2n+1 − 1/a2n
1/a2n
1
= lim
=
...

A4
...
Choose a white square uniformly at
random, choose one of its two neighbors with equal probability, and color this neighboring
square black if it is not already black
...
Let w(N ) be the expected number of white squares
remaining
...

N →∞
N
1
Answer
...
Note that w(0) = 0, w(1) = 1, and w(2) = 1 (as eventually one of the two white
squares will turn black)
...

For the first step of the process, there are 2N equally likely possible “outcomes”, consisting
of a choice of a white square along with a choice of one of its neighbors to be colored
...
The other 2N − 2 outcomes all
result in a white square being colored black
...
Of the 2N − 2 outcomes that lead to a white square being colored
black, one has k = 1, one has k = N , and the other values of k, with 2 ≤ k ≤ N − 1, occur
twice each
...
) Because these 2N − 2
outcomes are equally likely, we can conclude that
1
w(N ) =
w(0) + w(N − 1) + 2(w(1) + w(N − 2))+
2N − 2


· · · + 2(w(N − 2) + w(1)) + w(N − 1) + w(0)
N
−2
X


1
=
w(n)
...
Subtracting this equation from the same one

n=1

in which N is replaced by N + 1, we get N w(N + 1) − (N − 1)w(N ) = w(N ) + w(N − 1),
that is,
1
w(N + 1) = w(N ) + w(N − 1)
...
By inspection, one solution is
w(N ) = N + 1 ; we will use reduction of order to find the general solution
...
Thus if we let
∆(N ) = q(N ) − q(N − 1), we have
1
∆(N + 1) = −
∆(N ) ,
N +2
which implies that
(−1)N
∆(N ) = C
(N + 1)!

for some constant C
...

w(N ) = a · (N + 1) + C · (N + 1)
(n
+
1)!
n=1
From the initial conditions we have w(0) = 0, so a = 0, and then w(1) = 1, so C = −1
and
#
"N +1
#
"N +1
X (−1)j
X (−1)j
w(N ) = (N + 1)
= (N + 1)

...

N →∞
N →∞
N
j!
e
j=0
A5
...

Find the largest integer n such that an = 2020
...
n = F4040 − 1
...
We will show that for any integer m ≥ 2, the largest n such that an = m is
n = F2m − 1; therefore, the answer is F4040 − 1
...
Thus it is enough to show the two following facts, each of which will be
proved by induction on m:
a) For n = F2m − 1, we have an = m
...

P
Proof of a): For the base case m = 2, we have n = F4 − 1 = 2 and the sets S with
Fk = n
k∈S
P
are {1, 2} and {3}
...
To get a decomposition n =
Fk of the
k∈S

desired form, we can add F2m+1 to any such decomposition of F2m − 1; by the induction
hypothesis, there are exactly m such
...

Proof of b): We’ll use m = 2 and m = 3 as base cases, checking that a1 = 2 (the sets are {1}
and {2}) and a2 = 2 for m = 2, and that a3 = 3, a4 = 3, a5 = 3, a6 = 4, a7 = 3 for m = 3
...
Then we can write n = Fq + `, where
q = 2m or q = 2m + 1 and 0 ≤ ` ≤ Fq−1 − 1
...


(1) If 0 ≤ ` < Fq−3 , we can get a decomposition of n by adding Fq to any decomposition
of ` (of which there are at least 2, unless ` = 0, in which case we only have n = Fq )
as well as by adding Fq−1 to any decomposition of Fq−2 + ` (which is a number less
than Fq−1 , so it cannot create repetition)
...

(2) If Fq−3 ≤ ` < Fq−3 + Fq−4 = Fq−2 , then we can get a decomposition of n by adding
Fq to any decomposition of `, and we can also get one by adding Fq−1 + Fq−2 to any
decomposition of `
...
Because m ≥ 3, we have 2(m − 1) ≥ m + 1, as desired
...
In this case, we can get a decomposition of n by adding Fq to any decomposition of `; by the induction hypothesis, there
are at least m such decompositions
...

(This works because Fq + ` ≤ Fq + Fq−1 − 1 = Fq+1 − 1 = Fq−1 + Fq−2 + · · · + F1 , and
if any Fibonacci number is not used, the sum of the remaining ones is greater than
or equal to the one skipped, so the algorithm can continue until the sum reaches n
...

Solution 2
...
(This way of writing n will be referred to as the base-Fibonacci
representation of n; the first few are 1 = F2 , 2 = F3 , 3 = F4 , 4 = F2 + F4
...
By induction, n − Fm has a base-Fibonacci
representation, for which the set of subscripts cannot include m − 1, and adding Fm gives a
base-Fibonacci representation for n
...

Next, we identify any nonempty finite set S of positive integers with the finite sequence
(sk )k≥1 of zeros and ones, ending with a 1, such that sk = 1 ⇔ k ∈ S
...

We will show, more generally, that the largest n for which there are exactly m ≥ 2 sets with
f (S) = n is n = F2m − 1, so that the answer is F4040 − 1
...
Replace any occurrence of consecutive terms (1, 1, 0) in the sequence by
(0, 0, 1); if there is no occurrence of (1, 1, 0) but the sequence starts with (1, 0), replace that
start by (0, 1)
...
Therefore, we can count the number of sets with f (S) = n by
counting the number of sets that can be transformed into S0 by a sequence of such moves, or
equivalently the number of sets that can be obtained from S0 (including S0 itself) by reversing
these moves
...

Suppose that n = F2m − 1
...
, 0, 1, and when we start reversing the moves
we see that at every step there is only one choice, which is an A move; after k steps we will
have
n = F1 + F2 + · · · + F2k + F2k+3 + F2k+5 + · · · + F2m−3 + F2m−1
and we get such representations for k = 0, 1,
...

To finish the proof, we now show by induction that if n ≥ F2m , there are more than m
sets S with f (S) = n
...
Thus it is
enough to prove that for any base-Fibonacci sequence S0 with its final 1 in either the 2mth
position or the (2m + 1)st position, there are at least m + 1 different outcomes (counting
S0 itself) of the A and B moves described above
...
If there
is no such string of zeros, then S0 must be precisely of the form 0, 1, 0, 1, 0, 1,
...
If the rightmost string
of at least two successive zeros actually comes at the very beginning of the sequence, say that
the sequence starts with exactly z zeros (z ≥ 2), so it consists of those z zeros followed by
1, 0, 1, 0,
...
Then we can start with bz/2c A moves at the
beginning of the sequence; if z is odd, we can follow those up with a B move, so, whether z is
even or odd, we have a total of b(z + 1)/2c moves available at the beginning of the sequence
...
In all, we have at least b(z + 1)/2c + r + 1
different outcomes (counting S0 itself); meanwhile, the length of the sequence S0 is z +2r +1
...
We are left with the case that the rightmost string of at least two zeros in S0 does
not come at the beginning of the sequence; say it comes after a 1 in the ath position and
consists of exactly z zeros, followed by (r + 1) ones and r zeros, alternating as in the previous
case
...
For each of
these “partial” outcomes, the rest of the sequence, starting with the z consecutive zeros, can
be treated as in the previous case, except that if z is odd, we do not have the follow-up B
move available after the initial bz/2c A moves
...
The length of the sequence is a + z + 2r + 1
...

This estimate concludes the proof
...
For a positive integer N , define the function
fN (x) =

N
X
n=0



N + 1/2 − n
sin (2n + 1)x
...

π
Answer
...

4
Solution
...
The following computation
allows us to write its derivative in closed form:
N
N
X
X


2N + 1 − 2n
2N + 1 − 2n
fN0 (x) =
cos((2n + 1)x) =
Re e(2n+1)ix
2(N + 1)
2(N + 1)
n=0
n=0
!
N
X
1
2(N +1)ix
(2n−1−2N )ix
(2N + 1 − 2n)e
=
Re e
2(N + 1)
n=0
!
N
X
1
d
=
Re ie2(N +1)ix
e(2n−1−2N )ix
2(N + 1)
dx n=0



2(N +1)ix
1
2(N +1)ix d
(−1−2N )ix 1 − e
=
Re ie
e
2(N + 1)
dx
1 − e2ix


1
d 1 − e−2(N +1)ix
=
Re ie2(N +1)ix
2(N + 1)
dx eix − e−ix


−2(N +1)ix
1
2(N +1)ix d 1 − e
=
Re e
4(N + 1)
dx
sin x


1
2(N + 1)i (1 − e2(N +1)ix ) cos x
=
Re
+
4(N + 1)
sin x
sin2 x
[1 − cos(2(N + 1)x)] cos x
sin2 ((N + 1)x)
=
cos x
...
(This is still true where sin x = 0,
because then x = kπ for some integer k, and for all 0 ≤ n ≤ N, cos((2n + 1)kπ) = cos kπ,
so that the first expression for fN0 (x) above is a positive multiple of cos x
...
) It follows that fN (x) has its
maximum value for x = π/2
...

4M + 3
n=0 2n + 1
=

1
From here it is straightforward to check that f2M (π/2) − f2M −1 (π/2) = (4M +1)(4M
and
+2)
1
f2M +1 (π/2) − f2M (π/2) = (4M +2)(4M +3) , so the maximum value fN (π/2) is an increasing
function of N
...

2n + 1
4
n=0

Variant
...

sin x

Proof: Let z = eix , and note that
N
X

N
X

z − z 2N +3
1 − z2
n=0
 N +1

z 2N +2 − 1
z
− z −(N +1)
N +1
=
=z
z − 1/z
z − 1/z
sin[(N + 1)x]
= (cos[(N + 1)x] + i sin[(N + 1)x])

...

We now use the identity
N + 1/2 − n
1
1
=
−
(N + 1)(2n + 1)
2n + 1 2(N + 1)

to split fN (x) into two pieces:
fN (x) =

N
X
sin[(2n + 1)x]
n=0

=

2n + 1

N
X
sin[(2n + 1)x]
n=0

2n + 1

N

X
1
−
sin[(2n + 1)x]
2(N + 1) n=0
−

1
sin2 [(N + 1)x]
,
2(N + 1)
sin x

using the second part of the lemma
...

=

B1
...
Let
S=

2020
X

(−1)d(k) k 3
...

Answer
...

Solution 1
...
Therefore, S is equal to the sum starting at
2016 = 16 · 126, that is,
2020
X
S=
(−1)d(k) k 3
...


It remains to prove the desired cancellation, which results from the polynomial P (x) = x3
having degree 3 and from 23+1 = 16
...

Lemma: Suppose P (x) is a polynomial of degree n ≥ 0 , let N = 2n+1 − 1, and let m ≥ 0
be any integer
...


j=0

Proof: Note that for 0 ≤ j ≤ N , there are no carries in binary in the addition m2n+1 + j,
n+1
so d (m2n+1 + j) = d (m2n+1 ) + d(j) and we have Qm = (−1)d(m2 ) qm (0), where
qm (x) =

N
X

(−1)d(j) pm (x + j) , pm (x) = P (m2n+1 + x)
...
In fact, we will see that q(x) is identically zero
...
We then have
q(x) =

n −1
2X

(−1)

d(j)

p(x + j) +

N
X

(−1)d(j) p(x + j)

j=2n

j=0
2n −1

=

X

n
(−1)d(j) p(x + j) + (−1)d(j+2 ) p(x + j + 2n )
j=0

= −∆2n

n −1
2X

j=0

(−1)d(j) p(x + j)

because d(j + 2n ) = d(j) + 1 for 0 ≤ j ≤ 2n − 1
...

However, each application of a difference operator ∆k lowers the degree of a nonconstant
polynomial by 1, so ∆2n−1 · · · ∆4 ∆2 ∆1 p(x) is constant and q(x) is identically zero, completing
the proof of the lemma
...
Let S n,q =

n
P

(−1)d(k) k q mod 2020, so we are looking for S 2020,3
...
Similarly, we have

S 1009,2 ≡

504
504
X
X
(−1)d(2k+1) (2k + 1)2
(−1)d(2k) (2k)2 +
k=0

k=0

=

504
X



(−1)d(k) 4k 2 − 4k 2 − 4k − 1

k=0

≡ −4S 504,1 − S 504,0
and
S 1009,1 ≡

504
X

(−1)d(2k) (2k) +

k=0

=

504
X

504
X
(−1)d(2k+1) (2k + 1)
k=0

(−1)d(k) (−1)

k=0

≡ −S 504,0
...


Note that
S 504,1

252
251
X
X
d(2k)
≡
(−1)
(2k) +
(−1)d(2k+1) (2k + 1)
k=0

k=0

= (−1)d(504) (504) +

251
X

(−1)d(k) (−1)

k=0
d(504)

≡ (−1)

(504) − S 251,0

= 504 − S 251,0 ,
because the binary expansion of 504 is 111111000, so that d(504) = 6 is even
...
It follows that
S 2020,3 ≡ 48(504 − 0) + 18 · 1 − 0
= 24210 ≡ 1990
...
Let k and n be integers with 1 ≤ k < n
...
At the beginning of the game, the pegs occupy the k leftmost holes
...
The
players alternate moves, with Alice playing first
...
For what
values of n and k does Alice have a winning strategy?
Answer
...

Solution
...
, n
...
In this case we can divide the holes into disjoint
adjacent pairs Pi = {2i − 1, 2i} with 1 ≤ i ≤ n/2
...
Thus Alice’s first move must take a peg from an occupied pair of holes and
place it in one of a vacant pair of holes
...
Thus after each of Bob’s moves, each of the pairs Pi either has pegs in
both holes or in neither, whereas after each of Alice’s moves, there are two of the pairs Pi
with one peg each
...

If k and n are not both even, Alice always has a first move available which will leave
Bob either with no moves at all, or with a position equivalent to the starting position of
our game with even integers k1 and n1 , 1 ≤ k1 < n1
...

Specifically, if k and n are both odd, Alice can move the peg in hole k to hole n, leaving
k1 = k − 1 pegs at the beginning of a line of n1 = n − 1 remaining holes
...
) If k is odd and n is even, Alice can move the peg in hole 1 to hole n, winning
the game immediately if k = 1 and otherwise leaving k1 = k − 1 pegs at the beginning of a
line of n1 = n − 2 remaining holes
...
In each of these three

cases, after making the indicated first move, Alice can use Bob’s strategy from the previous
paragraph to win
...
The game with k pegs and n holes is equivalent to the game with n − k pegs
and n holes (moving the k pegs to the right is equivalent to moving the n − k vacant spaces
to the left)
...


B3
...
Iteratively, for
n = 0, 1, 2,
...
Let Z be the
smallest value of n for which xn < δ
...

Answer
...

Solution 1
...
Note that 0 ≤ xn ≤ 1
for all n, so these density functions all have support [0, 1]
...

y

This yields
Z

1

ρ2 (x) =
y=x

dy
= − ln(x), ρ3 (x) =
y

Z

1

(− ln y)
y=x

dy
[− ln(x)]2
=
,
y
2

which suggests that in general
ρn (x) =

[− ln(x)]n−1
;
(n − 1)!

this is straightforward to check by induction
...

Then q1 = δ, and for n ≥ 2 we have
Z

δ

ρn (x) − ρn−1 (x) dx

qn =
0
δ

[− ln(x)]n−1 [− ln(x)]n−2
−
dx
(n − 1)!
(n − 2)!
0
δ
x[− ln(x)]n−1 
=
(n − 1)! 
Z

=

0

n−1

=

δ[− ln(δ)]
(n − 1)!


...

Solution 2
...
Note that this applies to each of
X1 = x1 /x0 , X2 = x2 /x1 ,
...

Thus if U1 , U2 ,
...
are the corresponding exponential random variables, the problem
is equivalent to finding the expected number Z = Z(D) of i
...
d
...
By “First-Step Analysis” (considering
what the situation is after the first sample) we see that
Z D
Z D
Z(D) = 1 +
Z(D − t)pU (t) dt = 1 +
Z(D − t)e−t dt
0
0
Z D
= 1 + e−D
Z(u)eu du
...
Thus Z(D) = Z(0) + D = 1 + D = 1 + ln(1/δ)
...
Note that given xk−1 ≥ δ , the probability that xk is not smaller than δ is
(xk−1 − δ)/xk−1 ≤ 1 − δ
...

∞
P
n(1 − δ)n−1 ,
Thus the expected value of Z is bounded by the sum of the convergent series
n=1

and thus is finite
...
Note that this function is monotone
decreasing
...
Thus
Z 1
f (δ) = 1 +
f (δ/x) dx
...

t 1
Since f is monotone decreasing, g is monotone increasing and hence integrable
...
Hence the integral in
the functional equation is a differentiable function of t, and it follows that g is differentiable
...

Integrating and using the initial condition g(1) = 1, we get g(t) = 1 + ln t and hence
f (δ) = 1 + ln(1/δ)
...
Let n be a positive integer, and let Vn be the set of integer (2n + 1)-tuples
v = (s0 , s1 , · · · , s2n−1 , s2n ) for which s0 = s2n = 0 and |sj − sj−1 | = 1 for j = 1, 2, · · · , 2n
...

q(v)

Evaluate M (2020)
...


...
We will show that M (n) =
for all n, by partitioning Vn into subsets such
2n
1
1
that the average of
over each subset is

...
With this representation of elements of Vn ,
there is a natural “cyclic rearrangement” map σ : Vn → Vn which moves each of the symbols
one position back cyclically, that is, the symbol in position 1 moves to position 2n, and for
every j > 1 the symbol in position j moves to position j − 1
...
(Note that t0 = t2n = 0 and
that |tj − tj−1 | = |sj+1 − sj | = 1
...
In particular,
for any v ∈ Vn , the list of elements v, σ(v), σ 2 (v),
...
So the average of
for w on that list of elements is
q(w)
the same as the average over the orbit of v; because the orbits partition Vn , it is enough to
1
show that this average is
for any v
...
Applying this with v replaced by σ(v) yields
3s2 −s1
3s2
1
=
=
q(σ 2 (v))
q(σ(v))
q(v)
and similarly, by induction on j,
1
3sj
=

...
, σ 2n−1 (v), we add these answers for
q(w)
q(v)
= 1,
j = 0, 1,
...
But the sum of these answers is
q(v)
so we are done
...
For j ∈ {1, 2, 3, 4}, let zj be a complex number with |zj | = 1 and zj 6= 1
...

Solution 1
...
We will transform the variables first by
zj = 1 − yj and then by yj = 1/wj
...
Meanwhile, using similar
notation for the elementary symmetric functions of the y’s and the w’s, we find that
3 − e1 (Z) + e4 (Z) = e2 (Y ) − e3 (Y ) + e4 (Y ) =
Now let
wj =

1 − e1 (W ) + e2 (W )

...

2

Then
i
1
− vj vk + (vj + vk ),
4
2
so for the symmetric functions we have
X
X
3
3i
e1 (W ) =
wj = 2 + i e1 (V ), e2 (W ) =
wj wk = − e2 (V ) + e1 (V )
2
2
jwj wk =

and it is enough to show that
1 − e1 (W ) + e2 (W ) =
is never zero for real V = (v1 , v2 , v3 , v4 )
...
However, because V is real we have
X 2 X
X
e1 (V )2 =
vj =
vj2 + 2
vj vk ≥ 2e2 (V ),
j
so those values for e1 (V ) and e2 (V ) are impossible
...
We use a bilinear (linear fractional) transformation to map the circle |z| = 1
to the real line
...

w=i
1−z
w+i
To check, |z| = 1 implies |w − i| = |w + i|, from which it follows that w is real
...

(w1 + i)(w2 + i)(w3 + i)(w4 + i)

If this were zero for real numbers wi , taking real and imaginary parts of the numerator we
would get
8−4(w1 w2 +w1 w3 +w1 w4 +w2 w3 +w2 w4 +w3 w4 ) = 0 and w1 +w2 +w3 +w4 = 0, respectively
...

B6
...
Prove that
n
√
X
(−1)bk( 2−1)c ≥ 0
...
)
√
Solution
...

α
Also, let ak = (−1)bkαc
...
Because 1/3 < α < 1/2, the signs come
in runs of two or three equal signs, starting with a run of two 1s because bαc = b2αc = 0
and b3αc = 1
...
Denote the new sequence of signs by (bk ); that is, bk is the value taken by the k-th run
of length 3 in the sequence (ak )
...
Assuming this for now, we can prove the desired result
by a reduction argument, as follows
...
Then aN −2 , aN −1 , aN must be a run of three −1s, because

k=1

every run of fewer −1s is preceded by a run of 1s of at least equal length, so that omitting
both those runs can only decrease the partial sum
...
If we pass from the sequence (ak ) to the sequence (bk ),
we delete two entries from each run, starting with two 1s and ending with two −1s, so the
sum of all the terms will be unchanged
...
But m ≤ N/3 , contradicting the minimality of N
...
Suppose that the k-th run of length 3 is the (t+1)-st
run overall, that is, the run for which the floor is equal to t
...
There are
2t + (k − 1) terms before this run, so it consists of the terms with subscripts 2t + k, 2t + k + 1,
and 2t + k + 2, and we have the inequalities
t < (2t + k)α , (2t + k + 2)α < t + 1
...
But k/α = k(2 + α) = 2k + kα, so bkαc = t − 2k,
ak = (−1)bkαc = (−1)t−2k = (−1)t = bk , and we are done

---

Title: The 81st William Lowell Putnam Mathematical Competition, 2020
Description: The William Lowell Putnam Mathematics Competition Is a North American math contest for college students, organized by the Mathematical Association of America (MAA). Each year on the first Saturday in December, several thousands US and Canadian students spend 6 hours (in two sittings) trying to solve 12 problems. This past papers content problems and solutions.

Buy These NotesPreview