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 83rd William Lowell Putnam Mathematical Competition
Saturday, December 3, 2022

A1 Determine all ordered pairs of real numbers (a, b) such
that the line y = ax + b intersects the curve y = ln(1 +
x2 ) in exactly one point
...
Over all real polynomials
p(x) of degree n, what is the largest possible number of
negative coefficients of p(x)2 ?
A3 Let p be a prime number greater than 5
...
such that
an ∈ {1, 2,
...
Prove that f (p) is congruent to 0 or 2
(mod 5)
...
are real numbers between 0 and
1 that are chosen independently and uniformly at random
...
Find the expected value of S
...
They take turns
placing tiles that cover two adjacent squares, with Alice
going first
...
The game ends when
no tile can be placed according to this rule
...
What is
the greatest number of uncovered squares that Alice can
ensure at the end of the game, no matter how Bob plays?
A6 Let n be a positive integer
...
, x2n with −1 < x1 < x2 < · · · <
x2n < 1 such that the sum of the lengths of the n intervals
2k−1 2k−1
[x12k−1 , x22k−1 ], [x32k−1 , x42k−1 ],
...

B1 Suppose that P(x) = a1 x + a2 x2 + · · · + an xn is a polynomial with integer coefficients, with a1 odd
...
Prove that bk
is nonzero for all k ≥ 0
...
For what positive integers n does there exist a set S ⊂ R3 with exactly
n elements such that
S = {v × w : v, w ∈ S}?
B3 Assign to each positive real number a color, either red
or blue
...
Recolor the positive reals so that the numbers
in D are red and the numbers not in D are blue
...
, xn such that
each of the sets
{x1 , x2 , x3 }, {x2 , x3 , x4 },
...

B5 For 0 ≤ p ≤ 1/2, let X1 , X2 ,
...
Given a positive integer n and integers
b, a1 ,
...
, an ) denote the probability
that a1 X1 + · · · + an Xn = b
...
, an ) ≥ P(b, a1 ,
...
, an ?
B6 Find all continuous functions f : R+ → R+ such that
f (x f (y)) + f (y f (x)) = 1 + f (x + y)
for all x, y > 0
...
We show that y = ax + b intersects y = f (x) in exactly one point if and only if (a, b)
lies in one of the following groups:
– a=b=0
– |a| ≥ 1, arbitrary b
– 0 < |a| < 1, and b < ln(1 − r− )2 − |a|r− or b >
ln(1 − r+ )2 − |a|r+ , where
√
1 ± 1 − a2
r± =

...
For a = 0, by the symmetry of
y = f (x) and the fact that f (x) > 0 for all x ̸= 0 implies
that the only line y = b that intersects y = f (x) exactly
once is the line y = 0
...
In particular, f ′ (x) ≤ 1 for all x (including x < 0 since then
f ′ (x) < 0) and f ′ (x) achieves each value in (0, 1) exactly twice on [0, ∞)
...
They must intersect at
least once by the intermediate value theorem: for x ≪ 0,
ax + b < 0 < f (x), while for x ≫ 0, ax + b > f (x) since
ln(1+x2 )

limx→∞
= 0
...
For
a = 1, suppose that they intersect at two points (x0 , y0 )
and (x1 , y1 )
...

Finally we consider 0 < a < 1
...
If we define g(x) = f (x) − ax,
then g′ (r± ) = 0; g′ is strictly decreasing on (−∞, r− ),
strictly increasing on (r− , r+ ), and strictly decreasing
on (r+ , ∞); and limx→−∞ g(x) = ∞ while limx→∞ g(x) =
−∞
...
That is, y = ax + b intersects y = f (x) in exactly
one point if and only if b < g(r− ) or b > g(r+ )
...
Write p(x) = an xn +· · ·+a1 x+a0
and p(x)2 = b2n x2n + · · · + b1 x + b0
...
We claim that not all of the remaining 2n − 1 coefficients b1 ,
...
Indeed, suppose bi < 0 for 1 ≤ i ≤
2n − 1
...
Assume
a0 > 0 (or else replace p(x) by −p(x))
...
For i = 1, this
follows from 2a0 a1 = b1 < 0
...
But now
b2n−1 = 2an−1 an > 0, contradiction
...
For example,
we may take
p(x) = n(xn + 1) − 2(xn−1 + · · · + x),
so that
p(x)2 = n2 (x2n + xn + 1) − 2n(xn + 1)(xn−1 + · · · + x)
+ (xn−1 + · · · + x)2
...
, n − 1, n + 1,
...

A3 First solution
...
as
lying in F×
p ⊂ F p
...
Using this recurrence, we compute
1 + a2
1 + a1 + a2
, a4 =
,
a1
a1 a2
1 + a1
, a6 = a1 , a7 = a2
a5 =
a2

a3 =

and thus the sequence is periodic with period 5
...

The number of choices for a1 , a2 ∈ {1,
...

Since p is not a multiple of 5, (p − 2)(p − 3) is a product of two consecutive integers a, a + 1, where a ̸≡ 2
(mod 5)
...
Thus the number of possible sequences a1 , a2 ,
...

Second solution
...
As in the first solution,
any admissible sequence is 5-periodic
...
Each of these 5-tuples in S
comes from a unique admissible sequence, and there
is a 5-periodic action on S given by cyclic permutation:
(a, b, c, d, e) → (b, c, d, e, a)
...
It follows that the number of admissible sequences is a multiple of 5 plus the number of
constant admissible sequences
...

Since the quadratic x2 − x − 1 has discriminant 5, for
p > 5 it has either 2 roots (if the discriminant is a
quadratic residue mod p) or 0 roots mod p
...


A4 The expected value is
Extend S to an infinite sum by including zero summands for i > k
...
This summand occurs if and only
if X1 ,
...
, Xi−1 occur in nonincreasing order
...

2 (i − 1)! i i + 1
2 (i + 1)!

=

Since 2022 ≡ 6 (mod 7), this will yield a(2022) = 2 +
⌊ 2022
7 ⌋ = 290
...
Since the number of odd intervals never decreases, we have a(n), b(n) ≥ n − 2⌊ 2n ⌋; by looking at
the possible final positions, we see that equality holds
for n = 0, 1, 2, 3, 5
...

We now proceed to the induction step
...
In particular,
this means that a(m) ≥ b(m); consequently, it does not
change the analysis to allow a player to pass their turn
after the first move, as both players will still have an
optimal strategy which involves never passing
...


Moving first, Alice can leave behind two intervals of
length 1 and n − 3
...

On the other hand, if Alice leaves behind intervals of
length i and n − 2 − i, Bob can choose to play in either one of these intervals and then follow Alice’s lead
thereafter (exercising the pass option if Alice makes the
last legal move in one of the intervals)
...
, n − 2}
= a(n − 7) + 1
...
This shows that

Summing over i, we obtain


∞
1
1
1
1/2
=
2
=
2
e
−
1
−

...
More
generally, let a(n) (resp
...
Bob) moving first in a position with n
consecutive squares
...

On the other hand, if Bob leaves behind intervals of
length i and n − 2 − i, Alice can choose to play in either one of these intervals and then follow Bob’s lead
thereafter (again passing as needed)
...
, n − 2}
= b(n − 7) + 1
...

A6 First solution
...
To show that
m ≥ n, we take
x j = cos

(2n + 1 − j)π
2n + 1

( j = 1,
...


3
It is apparent that −1 < x1 < · · · < x2n < 1
...

2n + 1
j=1
For ζ = e2πi(n+1)/(2n+1) , this becomes
2k−1
ζ j +ζ−j
2
j=1


1 2n 2k−1 2k − 1 j(2k−1−2l)
= − 2k−1 ∑ ∑
ζ
l
2
j=1 l=0


1 2k−1 2k − 1 2n j(2k−1−2l)
= − 2k−1 ∑
∑ζ
l
2
j=1
l=0


1 2k−1 2k − 1
= − 2k−1 ∑
(−1) = 1,
l
2
l=0
2n



=−∑

using the fact that ζ 2k−1−2l is a nontrivial root of unity
of order dividing 2n + 1
...
We
say that a multiset {x1 ,
...

Lemma
...
, xm }, {y1 ,
...
We then have

By the lemma, this means that the multisets
{1, x1 , x3 ,
...
, x2n } become equal
after removing pairs of inverses until this becomes impossible
...

Remark
...
,n; j=0,
...
, xn pairwise distinct (this matrix has determinant ∏0≤i< j≤n (xi − x j ) ̸= 0)
...
Bhargava, Galois groups
of random integer polynomials and van der Waerden’s
conjecture, arXiv:2111
...

Remark
...
However, it does become unique
if we add the assumption that xi = −x2n+1−i for i =
1,
...
e
...

Second solution
...
Let sk denote the k-th power sum of
p(x); then for any given m, the desired condition is that
s2k−1 = 0 for k = 1,
...
Let ek denote the k-th elementary symmetric function of the roots of p(x); that
is,

(k = 1,
...


i=1

(k = 1,
...


i=1

p(x) = x2n+1 +

2n+1

∑ (−1)k ek x2n+1−k
...


By the Girard–Newton identities,
Proof
...

Form the rational functions
m

xi z
,
2 2
i=1 1 − xi z

f (z) = ∑

n

yi z
;
2 2
i=1 1 − yi z

g(z) = ∑

both f (z) and g(z) have total pole order at most 2n
...
Consequently, the two series
are equal
...
, xm }
2 } and the residue of
from f (z): f has poles at {1/x12 ,
...
e
...
Similarly, we may recover {y1 ,
...


(2k − 1)e2k−1 = s1 e2k−2 − s2 e2k−2 + · · · − s2k e1 ;
hence the desired condition implies that e2k−1 = 0 for
k = 1,
...

If we had a solution with m = n + 1, then the vanishing
of e1 ,
...
Since we have
already identified 2n + 1 other roots of p, this yields a
contradiction
...
It will thus suffice to choose q(x)

4
so that the resulting polynomial p(x) has roots consisting of −1 plus 2n distinct values in (−1, 1)
...
g
...
The
polynomial xr(x2 ) then has 2n + 1 distinct real roots;
consequently, for ε > 0 sufficiently small, xr(x2 ) + ε
also has 2n + 1 distinct real roots
...

Remark
...
, −a1 , 0, a1 ,
...
Let G be the set of power series of
xn
the form ∑∞
n=0 cn n! with c0 = 1, cn ∈ Z; then G forms a
group under formal series multiplication because
!
!
∞
∞
∞
xn
xn
xn
∑ cn n! ∑ dn n! = ∑ en n!
n=0
n=0
n=0
with
n

en =

 
n
∑ m cm dn−m
...

n

(where 0 < a1 < · · · < an−1 < 1 but no other conditions
are imposed) and deforming it using the implicit function theorem
...
, x2n (t) with xi (t) =
x2n−i (t) for i = 1,
...
, 2n;
this is because the Jacobian matrix
J = ((2k − 1)xi (0)2k−2 )i=n,
...
,n
(interpreting 00 as 1) has the property that every maximal minor is nonzero (these being scaled Vandermonde
matrices)
...

In the proof that m = n + 1 cannot occur, one can similarly use the implicit function theorem (with some care)
to reduce to the case where {|x1 |,
...
This can be extended to a complete solution, but the details are rather involved
...

n

(P(x))
First solution
...

n!
n=0

(P(x))k + ∑

In particular, b0 = 1 and b1 = a1 are both odd
...

The coefficient of xk in (P(x))k is ak1
...
For k even or n ≤ k − 2, this follows
k!
immediately from the fact that n!
is an even integer
...


We have e2x ∈ H because 2n! ∈ 2Z for all n ≥ 1: the
exponent of 2 in the prime factorization of n! is
∞

∑

i=1

jnk
2i

∞

n
= n
...

We deduce
that eP(x)−x ∈ H
...

Third solution
...

For each j, choose a set S j consisting of |a j | colors
...
, k}, with each part of size j assigned a color in
S j , and the weight being (−1)i where i is the number of
parts of any size j for which a j < 0
...

Choose an involution on each S j with

---