AoPS Community 2019 ELMO Shortlist

ELMO Shortlist 2019

www.artofproblemsolving.com/community/c899366
by pieater314159, tastymath75025

– Algebra

A1 Let a, b, c be positive reals such that 1

a + 1
b + 1
c = 1. Show that

aa bc + bb ca + cc ab ≥ 27bc + 27ca + 27ab.

Proposed by Milan Haiman

A2 Find all functions f : Z → Z such that for all surjective functions g : Z → Z, f + g is also
surjective. (A function g is surjective over Z if for all integers y, there exists an integer x such
that g(x) = y.)
Proposed by Sean Li

A3 Let m, n ≥ 2 be integers. Carl is given n marked points in the plane and wishes to mark their
centroid.* He has no standard compass or straightedge. Instead, he has a device which, given
marked points A and B, marks the m − 1 points that divide segment AB into m congruent
parts (but does not draw the segment).
For which pairs (m, n) can Carl necessarily accomplish his task, regardless of which n points
he is given?
*Here, the centroid of n points with coordinates (x1 , y1 ), . . . , (xn , yn ) is the point with coordi-
n y1 +···+yn
nates x1 +···+x .


n , n

Proposed by Holden Mui and Carl Schildkraut

A4 Find all nondecreasing functions f : R → R such that, for all x, y ∈ R,

f (f (x)) + f (y) = f (x + f (y)) + 1.

Proposed by Carl Schildkraut

A5 Carl chooses a functional expression* E which is a finite nonempty string formed from a set
x1 , x2 , . . . of variables and applications of a function f , together with addition, subtraction,
multiplication (but not division), and fixed real constants. He then considers the equation E =
0, and lets S denote the set of functions f : R → R such that the equation holds for any choices
of real numbers x1 , x2 , . . . . (For example, if Carl chooses the functional equation

© 2019 AoPS Incorporated 1

AoPS Community 2019 ELMO Shortlist

f (2f (x1 ) + x2 ) − 2f (x1 ) − x2 = 0,

then S consists of one function, the identity function.

(a) Let X denote the set of functions with domain R and image exactly Z. Show that Carl can
choose his functional equation such that S is nonempty but S ⊆ X.
(b) Can Carl choose his functional equation such that |S| = 1 and S ⊆ X?
*These can be defined formally in the following way: the set of functional expressions is the
minimal one (by inclusion) such that (i) any fixed real constant is a functional expression, (ii)
for any positive integer i, the variable xi is a functional expression, and (iii) if V and W are
functional expressions, then so are f (V ), V + W , V − W , and V · W .
Proposed by Carl Schildkraut

– Combinatorics

C1 Elmo and Elmo’s clone are playing a game. Initially, n ≥ 3 points are given on a circle. On a
player’s turn, that player must draw a triangle using three unused points as vertices, without
creating any crossing edges. The first player who cannot move loses. If Elmo’s clone goes first
and players alternate turns, who wins? (Your answer may be in terms of n.)
Proposed by Milan Haiman

C2 Adithya and Bill are playing a game on a connected graph with n > 2 vertices, two of which
are labeled A and B, so that A and B are distinct and non-adjacent and known to both players.
Adithya starts on vertex A and Bill starts on B. Each turn, both players move simultaneously:
Bill moves to an adjacent vertex, while Adithya may either move to an adjacent vertex or stay
at his current vertex. Adithya loses if he is on the same vertex as Bill, and wins if he reaches B
alone. Adithya cannot see where Bill is, but Bill can see where Adithya is. Given that Adithya
has a winning strategy, what is the maximum possible number of edges the graph may have?
(Your answer may be in terms of n.)
Proposed by Steven Liu

C3 In the game of Ring Mafia, there are 2019 counters arranged in a circle. 673 of these counters
are mafia, and the remaining 1346 counters are town. Two players, Tony and Madeline, take
turns with Tony going first. Tony does not know which counters are mafia but Madeline does.
On Tonys turn, he selects any subset of the counters (possibly the empty set) and removes all
counters in that set. On Madelines turn, she selects a town counter which is adjacent to a mafia
counter and removes it. Whenever counters are removed, the remaining counters are brought
closer together without changing their order so that they still form a circle. The game ends
when either all mafia counters have been removed, or all town counters have been removed.

© 2019 AoPS Incorporated 2

AoPS Community 2019 ELMO Shortlist

Is there a strategy for Tony that guarantees, no matter where the mafia counters are placed
and what Madeline does, that at least one town counter remains at the end of the game?
Proposed by Andrew Gu

C4 Let n ≥ 3 be a fixed integer. A game is played by n players sitting in a circle. Initially, each player
draws three cards from a shuffled deck of 3n cards numbered 1, 2, . . . , 3n. Then, on each turn,
every player simultaneously passes the smallest-numbered card in their hand one place clock-
wise and the largest-numbered card in their hand one place counterclockwise, while keeping
the middle card.
Let Tr denote the configuration after r turns (so T0 is the initial configuration). Show that Tr is
eventually periodic with period n, and find the smallest integer m for which, regardless of the
initial configuration, Tm = Tm+n .
Proposed by Carl Schildkraut and Colin Tang

C5 Given a permutation of 1, 2, 3, . . . , n, with consecutive elements a, b, c (in that order), we may

perform either of the moves:
- If a is the median of a, b, and c, we may replace a, b, c with b, c, a (in that order)
- If c is the median of a, b, and c, we may replace a, b, c with c, a, b (in that order)
What is the least number of sets in a partition of all n! permutations, such that any two per-
mutations in the same set are obtainable from each other by a sequence of moves?
Proposed by Milan Haiman

– Geometry

G1 Let ABC be an acute triangle with orthocenter H and circumcircle Γ. Let BH intersect AC at
E, and let CH intersect AB at F . Let AH intersect Γ again at P 6= A. Let P E intersect Γ again
at Q 6= P . Prove that BQ bisects segment EF .
Proposed by Luke Robitaille

G2 Carl is given three distinct non-parallel lines `1 , `2 , `3 and a circle ω in the plane. In addition
to a normal straightedge, Carl has a special straightedge which, given a line ` and a point P ,
constructs a new line passing through P parallel to `. (Carl does not have a compass.) Show
that Carl can construct a triangle with circumcircle ω whose sides are parallel to `1 , `2 , `3 in
some order.
Proposed by Vincent Huang

G3 Let 4ABC be an acute triangle with incenter I and circumcenter O. The incircle touches sides
BC, CA, and AB at D, E, and F respectively, and A0 is the reflection of A over O. The circum-

© 2019 AoPS Incorporated 3

AoPS Community 2019 ELMO Shortlist

circles of ABC and A0 EF meet at G, and the circumcircles of AM G and A0 EF meet at a point
H 6= G, where M is the midpoint of EF . Prove that if GH and EF meet at T , then DT ⊥ EF .
Proposed by Ankit Bisain

G4 Let triangle ABC have altitudes BE and CF which meet at H. The reflection of A over BC is
A0 . Let (ABC) meet (AA0 E) at P and (AA0 F ) at Q. Let BC meet P Q at R. Prove that EF k HR.
Proposed by Daniel Hu

G5 Given a triangle ABC for which ∠BAC 6= 90◦ , let B1 , C1 be variable points on AB, AC, respec-
tively. Let B2 , C2 be the points on line BC such that a spiral similarity centered at A maps B1 C1
to C2 B2 . Denote the circumcircle of AB1 C1 by ω. Show that if B1 B2 and C1 C2 concur on ω at
a point distinct from B1 and C1 , then ω passes through a fixed point other than A.
Proposed by Max Jiang

G6 Let ABC be an acute scalene triangle and let P be a point in the plane. For any point Q 6=
A, B, C, define TA to be the unique point such that 4TA BP ∼ 4TA QC and 4TA BP, 4TA QC
are oriented in the same direction (clockwise or counterclockwise). Similarly define TB , TC .
a) Find all P such that there exists a point Q with TA , TB , TC all lying on the circumcircle of
4ABC. Call such a pair (P, Q) a tasty pair with respect to 4ABC.
b) Keeping the notations from a), determine if there exists a tasty pair which is also tasty with
respect to 4TA TB TC .
Proposed by Vincent Huang

– Number Theory

N1 Let P (x) be a polynomial with integer coefficients such that P (0) = 1, and let c > 1 be an
integer. Define x0 = 0 and xi+1 = P (xi ) for all integers i ≥ 0. Show that there are infinitely
many positive integers n such that gcd(xn , n + c) = 1.
Proposed by Milan Haiman and Carl Schildkraut

N2 Let f : N → N. Show that f (m) + n | f (n) + m for all positive integers m ≤ n if and only if
f (m) + n | f (n) + m for all positive integers m ≥ n.
Proposed by Carl Schildkraut

N3 Let S be a nonempty set of positive integers such that, for any (not necessarily distinct) inte-
gers a and b in S, the number ab + 1 is also in S. Show that the set of primes that do not divide
any element of S is finite.
Proposed by Carl Schildkraut

© 2019 AoPS Incorporated 4

AoPS Community 2019 ELMO Shortlist

N4 A positive integer b and a sequence a0 , a1 , a2 , . . . of integers 0 ≤ ai < b is given. It is known

that a0 6= 0 and the sequence {ai } is eventually periodic but has infinitely many nonzero terms.
Let S be the set of positive integers n so that n | (a0 a1 . . . an )b . Given that S is infinite, show
that there are infinitely many primes that divide at least one element of S.
Proposed by Carl Schildkraut and Holden Mui

N5 Given an even positive integer m, find all positive integers n for which there exists a bijection
f : [n] → [n] so that, for all x, y ∈ [n] for which n | mx − y,

(n + 1) | f (x)m − f (y).

Note: For a positive integer n, we let [n] = {1, 2, . . . , n}.

Proposed by Milan Haiman and Carl Schildkraut

© 2019 AoPS Incorporated 5

Art of Problem Solving is an ACS WASC Accredited School.