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

---

2019 William Lowell Putnam Mathematical Competition
Problems

A1: Determine all possible values of the expression
A3 + B 3 + C 3 − 3ABC
where A, B, and C are nonnegative integers
...

Let α and β be the angles at the vertices A and B, respectively
...
Find α
...
, b2019 with b2019 6= 0, let z1 , z2 ,
...


k=0

Let µ = (|z1 | + · · · + |z2019 |)/2019 be the average of the distances from z1 , z2 ,
...
Determine the largest constant M such that µ ≥ M for all choices of
b0 , b1 ,
...

A4: Let f be a continuous real-valued function on R3
...
Must f (x, y, z) be identically 0?
A5: Let p be an odd prime number, and let Fp denote the field of integers modulo p
...


Find the greatest nonnegative integer n such that (x − 1)n divides q(x) in Fp [x]
...
Suppose that for some real number r > 1,
lim

x→0+

g(x)
= 0
...

x→0+

B1: Denote by Z2 the set of all points (x, y) in the plane with integer coordinates
...
Determine, as a function of n,
the number of four-point subsets of Pn whose elements are the vertices of a square
...


an

...
Let P = I − 2uuT , where I is the n-by-n identity matrix
...

B4: Let F be the set of functions f (x, y) that are twice continuously differentiable for x ≥ 1,
y ≥ 1 and that satisfy the following two equations (where subscripts denote partial derivatives):
xfx + yfy = xy ln(xy) ,
x2 fxx + y 2 fyy = xy
...

s≥1

Determine m(f ), and show that it is independent of the choice of f
...
Let p(x) be the polynomial of degree 1008 such that p(2n + 1) = F2n+1 for
n = 0, 1, 2,
...
Find integers j and k such that p(2019) = Fj − Fk
...
Two points in Zn are called neighbors if they differ
by exactly 1 in one coordinate and are equal in all other coordinates
...

(2) If p ∈ Zn is not in S, then exactly one of the neighbors of p is in S
...
Let X denote the given expression;
we first show that we can make X equal to each of the
claimed values
...

By taking (b, c) = (0, 1) or (b, c) = (1, 1), we obtain respectively X = 3A + 1 and X = 3A + 2; consequently,
as A varies, we achieve every nonnegative integer not
divisible by 3
...
We may also achieve
X = 0 by taking (b, c) = (0, 0)
...
It thus only remains to show that if X
is a multiple of 3, then it is a multiple of 9
...
This proves the claim
...
The factorization of X used above can be
written more symmetrically as
2

2

and let r be the inradius of 4ABC
...
By
3
the double angle formula for tangent, CD
DB = tan β = 4 ,
and so DB = 4r
...
It follows that
ED = r, whence the incircle is tangent to the altitude
CD
...

Remark
...
Since tan β2 = 13 , we may assume without
loss of generality that I = (3, 1)
...

Solution 2
...
Let r, s, and K denote the inradius,
semiperimeter, and area of 4ABC
...

If IG is parallel to AB, then

2

X = (A + B +C)(A + B +C − AB − BC −CA)
...
The other eigenvalues are A + ζ B + ζ 2C where ζ is a primitive cube
root of unity; in fact, X is the norm form for the ring
Z[T ]/(T 3 − 1), from which it follows directly that the
image of X is closed under multiplication
...
)
One can also the unique factorization property of the
ring Z[ζ ] of Eisenstein integers as follows
...

A2 Solution 1
...
Since s =
4
4 , we
have 3r2 = (s − a)(s − b)
...
It follows that tan( α2 ) tan( β2 ) =
1
α
π
3 and so tan( 2 ) = 1
...


Remark
...

a+b+c

Solution 3
...
For example, in a coordinate system with A =
(0, 0), B = (4, 0),C = (0, 3), we have


4
G=
,1 ,
I = (1, 1)
3
and for D = (1, 0),
tan

β
ID
1
=
=
...

Let C0 be the foot of the angle bisector at C
...
We may assume without loss of generality that A
and B are fixed, in which case this condition restricts C
to an ellipse with foci at A and B
...

Remark
...

A3 The answer is M = 2019−1/2019
...
, b2019 as specified, AM-GM gives
µ ≥ |z1 · · · z2019 |1/2019 = |b0 /b2019 |1/2019 ≥ 2019−1/2019
...
, b2019
given by bk = 2019k/2019 for all k
...
It follows that all
of the roots of P(z) have modulus 2019−1/2019 , and so
µ = 2019−1/2019 in this case
...
Let g : R → R be any continuous
R
function with g(t + 2) = g(t) for all t and 02 g(t) dt = 0
(for instance, g(t) = sin(πt))
...

We claim that for any sphere S of radius 1, S f dS = 0
...

We can parametrize S by S(φ , θ ) = (x0 , y0 , z0 ) +
(sin φ cos θ , sin φ sin θ , cos φ ) for φ ∈ [0, π] and θ ∈
[0, 2π]
...

Remark
...
In place
RR of spherical coordinates, one may also compute S f (x, y, z) dS
by computing the integral over a ball of radius r, then
computing the derivative with respect to r and evaluating at r = 1
...
Also, there exist nonzero continuous functions on Rn whose integral over any unit ball vanishes;
this implies certain negative results about image reconstruction
...
Define the operator D = x dx ,
d
where dx
indicates formal differentiation of polynomials
...
For m = 0,
...

Since r(1) 6= 0 and n 6≡ 0 (mod p) (because n ≤
deg(q) = p − 1), we may identify n as the smallest nonnegative integer for which (Dn q)(1) 6= 0
...
By the same logic
as above, (Dn s)(1) = 0 for n = 0,
...
This implies the claimed result
...
One may also finish by checking directly that
for any positive integer m,
(
p−1
−1 (mod p) if (p − 1)|m
m
∑ k ≡ 0 (mod p) otherwise
...
Otherwise, for any primitive root ` mod p,
multiplying the sum by `m permutes the terms modulo
p and hence does not change the sum modulo p; since
`n 6≡ 1 (mod p), this is only possible if the sum is zero
modulo p
...

(by Harm Derksen) We assume
that lim supx→0+ xr |g00 (x)| < ∞ and deduce that
limx→0+ g0 (x) = 0
...

x→0+

Suppose for the moment that there exists a function h
on (0, 1) which is positive, nondecreasing, and satisfies
lim

x→0+

g(x)
h(x)
= lim
= 0
...
By Taylor’s
theorem with remainder, we can find a function ξ on
(0, c) such that ξ (x) ∈ [x − h(x), x] and
1
g(x − h(x)) = g(x) − g0 (x)h(x) + g00 (ξ (x))h(x)2
...


g(x) 1 r 00
h(x) g(x − h(x)) h(x − h(x))
+ x g (ξ (x)) r −

...
Hence
limx→0+ g0 (x) = 0 as desired
...
One of many opp
tions is h(x) = xr f (x) where
f (x) = sup{|z−r g(z)| : z ∈ (0, x)},
so that
h(x) p
= f (x),
xr

g(x) p
= f (x)x−r g(x)
...
We argue by contradiction
...

Now let ε > 0 be arbitrary
...

r
0 xn
Choose n sufficiently large that ε2M
< xn and xn < δ /2;
ε0 xnr
then xn + 2M < 2xn < δ
...
It follows that
ε02 xnr
ε0 xnr
< |g(xn +
) − g(xn )|
2 2M
2M
r
ε0 xn
≤ |g(xn +
)| + |g(xn )|
2M


ε0 xnr r
< ε (xn +
) + xnr
2M
< ε(1 + 2r )xnr ,

We take as base cases the straightforward computations
P0 = {(0, 0), (±1, 0), (0, ±1)}
P1 = P0 ∪ {(±1, ±1)}
...
For
(x, y) ∈ Pn , note that x2 + y2 ≡ 0 (mod 4); since every
perfect square is congruent to either 0 or 1 modulo 4,
x and y must both be even
...

We next identify all of the squares with vertices in Pn
...


– Suppose that (a, b) = (0, 0)
...
The number
of such squares is 4n
...
Harm Derksen points out that the “or” in the
problem need not be exclusive
...


for k = 0,
...
To
show that there are no others, by symmetry it suffices to rule out the existence of a square with
opposite vertices (a, 0) and (c, 0) where a > |c|
...

These cannot belong to any Qk , or be equal to
(0, 0), because |a + c|, |a − c| ≥ a − |c| > 0 by the
triangle inequality
...
(One can
also phrase this argument in geometric terms
...
There
is one such square with vertices

Then for x ∈ (0, 1),
g0 (x) = 5x4 sin(x−3 ) − 3x cos(x−3 )
3

Pn = {(0, 0)} ∪ Qbn/2c ∪ Rb(n−1)/2c
...
There
is one such square with vertices

whence 4M(1 + 2r )ε > ε02
...


00

We first determine the set Pn
...

Let Rn be the set of points in Z2 of the form (±2k , ±2k )
for some k ≤ n (the two signs being chosen independently)
...

limx→0+ x−r g(x)

limx→0+ x3 sin(x−3 ) =
xr g00 (x) = (20x5

For r = 2,
=
0,
limx→0+ g0 (x) = 0 and
−
9x−1 ) sin(x−3 ) − 18x2 cos(x−3 ) is unbounded as
x → 0+
...
)

n+1
for k = 0,
...
To show
that there are no others, we may reduce to the previous case: rotating by an angle of π4 and then

4
√
rescaling by a factor of 2 would yield a square
with two opposite vertices in some Qk not centered at (0, 0), which we have already ruled out
...
By symmetry, we
may reduce to the case where (a, b) = (0, 2k ) and
(c, d) = (2` , ±2` )
...
If d < 0, then the
third vertex (−2k−1 , 2k−1 − 2` ) is impossible
...


Consequently,

Remark
...
Since this is clearly true for
n = 1, it suffices to show that for n ≥ 2, there are exactly 5 squares with vertices in Pn , at least one of which
is not in Pn−1
...
If
v is one of these points, then a square with a vertex at
v can only lie in S if its two sides containing v are in
line with the two sides of S containing v
...
Taking the union over the four points in Pn \ Pn−1
gives a total of 5 squares, as desired
...

π3

Solution 1
...

π
sin 2n
cos2 kπ
cos2 (k−1)π
2n
2n

Thus the sum telescopes and we find that


1
1
1
1

−1 +

 = −




...

Solution 2
...

2 (k+1)π
sin2 kπ
k=1 sin
2n
2n

(x ∈ [0, π])

2n

n
8(2k − 1)n3
+
O

...

= 3 ∑ 2
π k=1 k (k + 1)2
n2
Finally, note that
n−1


n−1 
(2k − 1)
1
1
1
∑ k2 (k + 1)2 = ∑ k2 − (k + 1)2 = 1 − n2
k=1
k=1

converges to 1, and so limn→∞ ann3 =

8

...
We first note that P corresponds to the linear transformation on Rn given by reflection in the hyperplane perpendicular to u: P(u) = −u, and for any v
with hu, vi = 0, P(v) = v
...

We next claim that if Q is an n × n orthogonal matrix
that does not have 1 as an eigenvalue, then det Q =
(−1)n
...
The product of each
conjugate pair of roots is 1; thus det Q = (−1)k where
k is the multiplicity of −1 as a root of p(t)
...

Finally, if neither of the orthogonal matrices Q nor PQ
has 1 as an eigenvalue, then det Q = det(PQ) = (−1)n ,
contradicting the fact that det P = −1
...

Remark
...
If equality
occurs, then det(Q) = (−1)n ; if equality does not occur,
then Q has 1 as an eigenvalue
...


5
Sucharit Sarkar suggests the following topological interpretation: an orthogonal matrix without 1 as an
eigenvalue induces a fixed-point-free map from the
(n − 1)-sphere to itself, and the degree of such a map
must be (−1)n
...
This solution uses the (reverse) Cayley
transform: if Q is an orthogonal matrix not having 1
as an eigenvalue, then
−1

A = (I − Q)(I + Q)

is a skew-symmetric matrix (that is, AT = −A)
...

Let V be the orthogonal complement of u in Rn
...


(I − Q)−1 (I − QP)u = (I − Q)−1 (I + Q)u = Au
and hu, Aui = hAT u, ui = h−Au, ui, so Au ∈ V
...

Remark
...

Remark
...

This reduces to the case A = I, in which case it again
comes down to the fact that the product of two square
matrices (in this case, obtained from v and w by padding
with zeroes) retains the same characteristic polynomial
when the factors are reversed
...
We compute that m( f ) = 2 ln 2 − 21
...
If
we write, e
...
, x ∂∂x (1) for the result of differentiating (1) by x and multiplying the resulting equation by
x, then the combination x ∂∂x (1) + y ∂∂y (1) − (1) − (2)
gives the equation 2xy fxy = xy ln(xy)+xy, whence fxy =
1
2 (ln(x) + ln(y) + 1)
...

2
s
Z

Z

R

m( f ) =

1
+
2

Z 2

ln(x) dx = 2 ln 2 −

1

1
2

independent of f
...
The phrasing of the question suggests that
solvers were not expected to prove that F is nonempty,
even though this is necessary to make the definition of
m( f ) logically meaningful
...

Solution 2
...
We conclude that

1
x fx = y fy = xy ln(xy)
2
x2 fxx = y2 fyy = xy
...
)
We next show that the only elements of F are f +
a ln(x/y) + b where a, b are constants
...
As in the first solution, we deduce that gxy = 0; this implies that g(x, y) =
u(x) + v(y) for some twice continuously differentiable
functions u and v
...
This yields that g = a ln(x/y) + b as desired
...
It thus remains to compute m( f )
...
We thus minimize by taking s = 1 as in the first solution
...
One way to make a correct guess for f is to
notice that the given equations are both symmetric in x
and y and posit that f should also be symmetric
...
However, before trying this, we observe that xy
appears explicitly in the equations, so it is reasonable to
make a first guess of the form f (x, y) = h(xy)
...


6
B5 Solution 1
...
More generally, let p(x) be the polynomial of degree N such that p(2n + 1) = F2n+1 for 0 ≤
n ≤ N
...

Define a sequence of polynomials p0 (x),
...
Then by induction on k, it is the case that pk (2n +
1) = F2n+1+k for 0 ≤ n ≤ N − k, and also that pk has
degree (at most) N − k for k ≥ 1
...

We now claim that for 0 ≤ k ≤ N, pN−k (2k + 3) =
∑kj=0 FN+1+ j
...

j=0

Thus we have p(2N + 3) = p0 (2N + 3) = ∑Nj=0 FN+1+ j
...
In the
case N = 1008, we thus have p(2019) = F2019 − F1010
...
This solution uses the Lagrange interpolation formula: given x0 ,
...
, yn , the unique
polynomial P of degree at most n satisfying P(xi ) = yi
for i = 0,
...

2
2

1
Fn = √ (α n − β −n ),
5

We thus deduce that p(x) = F2019 − F1010 as claimed
...
Karl Mahlburg suggests the following variant
of this
...

j=0
This identity has the following combinatorial interpretation
...
In any such tiling with n = 2018, let
j be the number of squares among
the first 1009 tiles
...

As an aside, this interpretation of Fn+1 is the oldest
known interpretation of the Fibonacci sequence, long
predating Fibonacci himself
...

Remark
...

First, note that to have Fj − Fk > 0, we must have k < j
...

If j > 2020, then

For γ ∈ R, let pγ (x) be the unique polynomial of degree
at most 1008 satisfying
p1 (2n + 1) = γ 2n+1 , p2 (2n + 1) = γ 2n+1 (n = 0,
...

5

By Lagrange interpolation,
1008

pγ (2019) =

∑ γ 2n+1

n=0

2019 − (2 j + 1)
0≤ j≤1008, j6=n (2n + 1) − (2 j + 1)

∏

1009 − j
n=0
0≤ j≤1008, j6=n n − j


1008
2n+1
1008−n 1009
= ∑γ
(−1)
n
n=0

∑ γ 2n+1

∏

= −γ((γ 2 − 1)1009 − (γ 2 )1009 )
...
But
then
(Fj − Fk ) − (F2019 − F1010 ) = (F2018 − Fk ) + F1010

1008

=

Fj − Fk ≥ Fj − Fj−1 = Fj−2 ≥ F2019 > F2019 − F1010
...


which is negative for k = 2019 (it equals F1010 − F2017 )
and positive for k ≤ 2018
...
To construct an example,
define the function f : Zn → Z/(2n + 1)Z by
f (x1 ,
...

To check condition (1), note that if p ∈ S and q is a
neighbor of p differing only in coordinate i, then
f (q) = f (p) ± i ≡ ±i (mod 2n + 1)

7
and so q ∈
/ S
...
, n} such
that f (p) is congruent to one of +i or −i modulo 2n +
1
...


Remark
...
For an application to steganography, see: J
...
Lisonˇek, Grid colorings in
steganography, IEEE Transactions on Information Theory 53 (2007), 1547–1549

---