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)
...


Consequently, x f (x) → 0 as x → 0+
...

Second solution
...
To check that it
is sufficient, we introduce the following concept: for X
a random variable taking finitely many integer values,
define the characteristic function

2L+ = lim sup 2 f (x f (x))
x→0+

= lim sup(1 + f (2x)) = 1 + L+
x→0+

2L− = lim inf 2 f (x f (x))
x→0+

ϕX (θ ) =

∑ P(X = ℓ)e

iℓθ

ℓ∈Z

(i
...
, the expected value of eiXθ , or the Fourier transform
of the probability measure corresponding to X)
...

– For any b ∈ Z,
P(X = b) =

1
2

Z 2π
0

e−ibθ ϕX (θ ) dθ
...


= lim inf(1 + f (2x)) = 1 + L−
x→0+

and so L− = L+ = 1, confirming (2)
...


(3)

Suppose that f (x) ≥ 1 for all x > 0
...
If there exists y > 0 with f (y) > 1, then from
(1) we have f (x + y) − f (x f (y)) = f (y f (x)) − 1 ≥ 0;
hence


y f (y)
Sc = S(c−y) f (y)
c ≥ c0 =
f (y) − 1

7
and (since (c − y) f (y) − c0 = f (y)(c − c0 )) iterating this
construction shows that S∞ = Sc for any c > c0
...


(4)

Still assuming that f (x) ≥ 1 for all x > 0, note that from
(1) with x = y,
1
f (x f (x)) = (1 + f (2x))
...

Taking the limit as x → ∞ and applying (6) yields
f (1/y) + f (y) = 1
...

y f (x)
Multiply both sides by x f (y), then take the limit as x →
∞ to obtain


1
1 = lim x f (y) f (x + y) + lim x f (y) f
x→∞
x→∞
y f (x)
= f (y) + lim x f (y)y f (x)
f (x f (y)) = f (x + y) + f

Since x f (x) → 0 as x → 0+ by (2) and x f (x) → ∞ as
x → ∞, x f (x) takes all positive real values by the intermediate value theorem
...

We may thus assume hereafter that f (x) < 1 for some
x > 0
...


(5)

x→∞

Put I = inf{ f (x) : x > 0} < 1, choose ε ∈ (0, (1 − I)/2),
and choose y > 0 such that f (y) < I + ε
...
Since x f (x) → 0 as x →
by (2), we
have sup{x f (x) : x > 0} < ∞ by the intermediate value
theorem, yielding (5)
...

We can now simplify by noting that if f (x) satisfies the
original equation, then so does f (cx) for any c > 0; we
may thus assume that the least element of f −1 (1/2) is
1
1, in which case we must show that f (x) = 1+x

...


1
1+y ,

as desired
...
Some variants of the above approach are possible
...
We first check
that

(6)

(9)

Suppose by way of contradiction that f (x) = 1 for some
x
...
It follows that f −1 (1) is infinite, contradicting (5)
...


(10)

For x < y, by substituting x 7→ y − x in (1) we obtain
1 + f (y) = f (x f (y − x)) + f ((y − x) f (x))
< 1 + f ((y − x) f (x)),

For all x > 0, by (1) with y = x,
1
1
f (x f (x)) = (1 + f (2x)) > = f (1),
2
2

and solving for f (y) now yields f (y) =

f (x) < 1 for all x > 0
...
As in the proof of (5), this
implies that x f (x) < 1 for all x > 0
...


whence f ((y − x) f (x)) > f (y)
...




---