ELMO 2019

Let $P(x)$ be a polynomial with integer coefficients such that $P(0)=1$ , and let $c > 1$ be an integer. Define $x_0=0$ and $x_{i+1} = P(x_i)$ for all integers $i \ge 0$ . Show that there are infinitely many positive integers $n$ such that $\gcd (x_n, n+c)=1$ .

Proposed by Milan Haiman and Carl Schildkraut

Let $m, n \ge 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 $\overline{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 $(x_1, y_1), \dots, (x_n, y_n)$ is the point with coordinates $\left( \frac{x_1 + \dots + x_n}{n}, \frac{y_1 + \dots + y_n}{n}\right)$ .

Proposed by Holden Mui and Carl Schildkraut

Let $n \ge 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, \dots, 3n$ . Then, on each turn, every player simultaneously passes the smallest-numbered card in their hand one place clockwise and the largest-numbered card in their hand one place counterclockwise, while keeping the middle card.

Let $T_r$ denote the configuration after $r$ turns (so $T_0$ is the initial configuration). Show that $T_r$ is eventually periodic with period $n$ , and find the smallest integer $m$ for which, regardless of the initial configuration, $T_m=T_{m+n}$ .

Proposed by Carl Schildkraut and Colin Tang

Carl is given three distinct non-parallel lines $\ell_1, \ell_2, \ell_3$ and a circle $\omega$ in the plane. In addition to a normal straightedge, Carl has a special straightedge which, given a line $\ell$ and a point $P$ , constructs a new line passing through $P$ parallel to $\ell$ . (Carl does not have a compass.) Show that Carl can construct a triangle with circumcircle $\omega$ whose sides are parallel to $\ell_1,\ell_2,\ell_3$ in some order.

Proposed by Vincent Huang

Let $S$ be a nonempty set of positive integers such that, for any (not necessarily distinct) integers $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

Carl chooses a functional expression* $E$ which is a finite nonempty string formed from a set $x_1, x_2, \dots$ 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 \colon \mathbb R \to \mathbb R$ such that the equation holds for any choices of real numbers $x_1, x_2, \dots$ . (For example, if Carl chooses the functional equation $$f(2f(x_1)+x_2) - 2f(x_1)-x_2 = 0,$$ then $S$ consists of one function, the identity function.

(a) Let $X$ denote the set of functions with domain $\mathbb R$ and image exactly $\mathbb Z$ . Show that Carl can choose his functional equation such that $S$ is nonempty but $S \subseteq X$ .

(b) Can Carl choose his functional equation such that $|S|=1$ and $S \subseteq 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 $x_i$ is a functional expression, and (iii) if $V$ and $W$ are functional expressions, then so are $f(V)$ , $V+W$ , $V-W$ , and $V \cdot W$ .

Proposed by Carl Schildkraut