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 at most one fixed
point; this induces an involution on the partitions, so to
find the parity of bk we may instead count fixed points
of the involution
...

Let Tk be the set of set partitions in question with the allsingletons partition removed; it now suffices to exhibit
a fixed-point-free involution of Tk
...
, k − 1}
for which i and i + 1 are not both singletons; we define
an involution by swapping the positions of i and i + 1
...

Clearly the set S = {0} works
...
We
claim that S cannot contain any nonzero vector v with
∥v∥ ̸= 1
...
Then S must contain the nonzero

5
vector u1 = v × w, as well as the sequence of vectors un defined inductively by un = v × un−1
...
The sequence ∥un ∥ consists of all distinct numbers and thus S
is infinite, a contradiction
...


We then observe that for any m ≥ 2, we obtain a sequence of the desired form of length 3m + 3 = (2m −
1) + 1 + (m + 1) + 2 by concatenating the arithmetic
progressions

Next note that any pair of vectors v, w ∈ S must either be
collinear or orthogonal: by the claim, v, w are both unit
vectors, and if v, w are not collinear then v × w ∈ S must
be a unit vector, whence v ⊥ w
...

Then {v1 , v2 , v3 } is an orthonormal basis of R3 , and it
follows that all of these vectors are in S: 0, v1 , v2 , v3 ,
−v1 = v3 ×v2 , −v2 = v1 ×v3 , and −v3 = v2 ×v1
...


We see that no terms are repeated by noting that the
first parenthesized sequence consists of odd numbers;
the second sequence consists of multiples of 4; and the
remaining numbers 2 and 4m − 2 are distinct (because
m ≥ 2) but both congruent to 2 mod 4
...
It is clear that
any set of this form does satisfy the given condition
...

B3 The answer is yes
...
We
claim that R2 = R+
...
Namely,
the numbers y and 2y must be of opposite colors in the
original coloring, and then 3y/2 must be of the same
color as one of y or 2y
...
Then
of the four numbers x, 2x, 3x, 4x, every other number
must be in R1 and the other two must be in B1
...
By the
previous observation again, x/2 and 3x/2 must both be
in R1 , but then x = 3x/2 − x/2 is in R2 , contradiction
...

B4 The values of n in question are the multiples of 3 starting with 9
...
e
...
See the remark below
...
If d1 and d2 are
the common differences of the arithmetic progressions
{xm , xm+1 , xm+2 } and {xm+1 , xm+2 , xm+3 } for some m,
then d2 ∈ {d1 , 2d1 , d1 /2}
...

By shifting, we may assume that the xi are themselves
all integers
...


(1, 3,
...
, 4, 0), 2
...
We may assume without loss of generality that
the smallest common difference among the arithmetic
progressions is 1 and occurs for {x1 , x2 , x3 }; by rescaling, shifting, and reversing the sequence as needed, we
may assume that x1 = 0 and (x2 , x3 ) ∈ {(1, 2), (2, 1)}
...

In none of these cases does {x5 , x6 , 0} form an arithmetic progression
...
If one interprets “distinct” in the problem
statement to mean “not all equal”, then the problem becomes simpler: the same argument as above shows that
n must be a multiple of 3, in which case a suitable repetition of the sequence −1, 0, 1 works
...
The answer is p ≤ 1/4
...
For p > 1/3, P(0, 1) = 1 − 2p < p = P(1, 1)
...
Now suppose 1/4 < p < 1/3, and consider
(b, a1 , a2 , a3 ,
...
, 2n−1 )
...
, 22n−1 ) = (1 − 2p)n
...
, Xn ) = (1, 0,
...
, 0),
(−1, −1, 1, 0,
...
, (−1, −1,
...
, 2n−1 )
= p(1 − 2p)n−1 + p2 (1 − 2p)n−2 + · · · + pn
(1 − 2p)n − pn
=p

...
, 2n−1 ) ≥
P(1, 1, 2,
...

Now suppose p ≤ 1/4; we want to show that
for arbitrary a1 ,
...
, an ) ≥
P(b, a1 ,
...
Define the polynomial
f (x) = px + px

−1

+ 1 − 2p,

and observe that P(b, a1 ,
...
We can write
f (xa1 ) f (xa2 ) · · · f (xan ) = g(x)g(x−1 )
for some
real polynomial g: indeed, if we define α =
√
1−2p+ 1−4p
> 0, then f (x) = αp (x + α)(x−1 + α), and
2p
so we can use
 p n/2
(xa1 + α) · · · (xan + α)
...
Since g(x)g(x−1 ) is symmetric
upon inverting x, we may assume that b > 0
...
But

For p ≤ 1/4, we have
ϕXk (θ ) = (1 − 2p) + 2p cos(θ ) ≥ 0
...
, an ∈ Z, the random variable S =
a1 X1 + · · · + an Xn satisfies
n

n

ϕS (θ ) = ∏ ϕak Xk (θ ) = ∏ ϕXk (ak θ ) ≥ 0
...

1
B6 The only such functions are the functions f (x) = 1+cx
for some c ≥ 0 (the case c = 0 giving the constant function f (x) = 1)
...


For convenience, we reproduce here the given equation:
f (x f (y)) + f (y f (x)) = 1 + f (x + y)

(1)

We first prove that
lim f (x) = 1
...

x→0+

For any fixed y, we have by (1)
L+ = lim sup f (x f (y))

2(c0 cb + c1 cb+1 + · · · + cm−b cm )
≤ (c20 + c2b ) + (c21 + c2b+1 ) + · · · + (c2m−b + c2m )
≤ 2(c20 + · · · + c2m ),

x→0+

≤ lim sup(1 + f (x + y)) = 1 + f (y) < ∞
...
By (2) with y = x,

and the result follows
...
(by Yuval Peres) We check that p ≤
1/4 is necessary as in the first solution
...
e
...
We use
two evident properties of these functions:
– If X and Y are independent, then ϕX+Y (θ ) =
ϕX (θ ) + ϕY (θ )
...


In particular, if ϕX (θ ) ≥ 0 for all θ , then P(X =
b) ≤ P(X = 0)
...

We next confirm that
f (x) ≥ 1 for all x > 0 =⇒ f (x) = 1 for all x > 0
...
For 0 < c ≤ ∞, put
Sc = sup{ f (x) : 0 < x ≤ c}; for c < ∞, (2) implies that
Sc < ∞
...
In any
case, we deduce that
f (x) ≥ 1 for all x > 0 =⇒ S∞ < ∞
...

2

By substituting y 7→ xy in (1),
f (x f (xy)) + f (xy f (x)) = 1 + f (x + xy)
...


(8)

Combining (1) with (8) yields



1

...
We deduce that 2S∞ ≤ 1 + S∞
and hence S∞ = 1; this proves (3)
...
We next check that
lim f (x) = 0
...
We then must
have x f (x) ̸= y for all x, or else
1 + I ≤ 1 + f (2x) = 2 f (y) < 2I + 2ε,
contradiction
...

By (2) plus (5), f −1 (1/2) is nonempty and compact
...

We next show that
lim x f (x) = 1
...


Remark
...
For example, once we have (5), we can establish
that f is monotone decreasing as follows
...
By (1),
f (2x) + 1 = 2 f (x f (x)) = 2 f (x) = 2
and so f (2x) = 1
...

We next check that
x < y =⇒ f (x) > f (y)
...


0+

x→∞

x→∞

= f (y) + y f (y)

(7)

so in particular x f (x) ̸= 1
...
However, by (5)
and (7) we have f (x f (x)) → 12 as x → ∞, yielding (6)
...
Because (y − x) f (x) →
0 as x → y− and (y − x) f (x) → y as x → 0+ , (y − x) f (x)
takes all values in (0, y) as x varies over (0, y); this
proves (10)

---