Question bank IMO Shortlist

Quadratic solitaire is a single-player game. To start the game, the player chooses two distinct nonzero integers $a$ and $b$ and writes the equation $x^{2}+ax+b=0$ on a blackboard. On each turn, if the equation currently written on the blackboard has two distinct nonzero integer solutions $x=u$ and $x=v$, then the player erases the equation and replaces it by one of the equations $x^{2}+ux+v=0$ or $x^{2}+vx+u=0$ of their choosing. Otherwise, the game ends.

Determine all initial choices of a and b such that quadratic solitaire can be played forever.

The sunshine cost of a sequence $ a_{1}, a_{2}, \ldots, a_{100} $ of integers is the largest possible value of

$$ \left|\left(a_{1}+a_{2}+\cdots+a_{i}\right)-a_{j}\right| $$

as i and j vary over all integers 1,2,...,100.

Determine the smallest possible sunshine cost over all sequences $ a_{1}, a_{2}, \ldots, a_{100} $ of pairwise distinct integers.

Coral and Joey are playing the inekoalaty game, a two-player game whose rules depend on a positive real number $ \lambda $ which is known to both players. On the $ n^{th} $ turn of the game, the following happens:

• If $n$ is odd, Coral chooses a nonnegative real number $x_{n}$ such that

$$ x_{1}+x_{2}+\cdots+x_{n}\leq\lambda n. $$

• If $n$ is even, Joey chooses a nonnegative real number $x_{n}$ such that

$$ x_{1}^{2}+x_{2}^{2}+\cdots+x_{n}^{2}\leqslant n. $$

All chosen numbers are known to both players. If a player cannot make a move, the game ends and the other player wins.

Determine all values of $ \lambda $ for which Coral has a winning strategy and all those for which Joey has a winning strategy.

Let $\mathbb{Z}_{\geq 0}$ be the set of all nonnegative integers. Let $f: \mathbb{Z}_{\geq 0} \to \mathbb{Z}_{\geq 0}$ be an unbounded function such that, if $m$ and $n$ are nonnegative integers satisfying

$$ f(m+n)=\max\left\{f(0),f(1),\cdots,f(m+n)\right\}, $$

then

$$ f(m+n)=f(m)+f(n). $$

Prove that there exist positive integers A, B, C and D such that for all nonnegative integers n, $ f(An + B) = Cn + D $.

We say that f is unbounded if for each nonnegative integer N, there exists some nonnegative integer n such that $ f(n) \geq N $.

Determine all integers $n \geq 2$ such that the polynomial

$$ P(x,y,z)=x^{n}+y^{n}+z^{n}-x^{n-2}y z-x y^{n-2}z-x y z^{n-2} $$

can be written as $P(x,y,z) = Q(x,y,z)R(x,y,z)$, where $Q(x,y,z)$ and $R(x,y,z)$ are nonconstant polynomials with integer coefficients.

Let $S$ be a set of positive integers, possibly infinite, such that no positive integer greater than 1 divides all elements of $S$. Determine all non-periodic infinite sequences $a_1, a_2, a_3, \ldots$ of positive integers such that, for all positive integers $n$,

• $ a_n \leq |a_{n+\ell} - \ell| $ for all $ \ell $ in $ S $, and

• $ a_{n} = |a_{n+\ell} - \ell| $ for at least one $ \ell $ in S.

We say that an infinite sequence $a_{1}, a_{2}, a_{3}, \ldots$ is periodic if there exists a positive integer $t$ such that $a_{n} = a_{n+t}$ for all positive integers $n$.

For each integer $ k \geq 3 $, prove that there exists a unique tuple $ (x_1, x_2, \ldots, x_k) $ of positive real numbers such that $ x_1 \geq x_2 \geq \cdots \geq x_k $ and

$$ \left\lfloor nx_{1}+\frac{1}{2}\right\rfloor+\left\lfloor nx_{2}+\frac{1}{2}\right\rfloor+\cdots+\left\lfloor nx_{k}+\frac{1}{2}\right\rfloor=n $$

for every integer n.

Here $\lfloor z\rfloor$ denotes the greatest integer less than or equal to z. For example, $\lfloor-\pi\rfloor=-4$ and $\lfloor2\rfloor=\lfloor2.9\rfloor=2$.

Tim and Tam play a game. To start the game, Tim writes some nonzero real numbers, not necessarily distinct, on a blackboard. In each round, the following happens:

First, Tam chooses a polynomial $ P_{k}(x) = a_{k}x^{k} + a_{k-1}x^{k-1} + \cdots + a_{1}x + a_{0} $ whose coefficients $ a_{k}, a_{k-1}, \ldots, a_{1}, a_{0} $ are all of the numbers currently written on the blackboard in some order. (For example, if the numbers on the blackboard are 4, -3, 4, then k = 2 and Tam may choose the polynomial $ 4x^{2} - 3x + 4 $ or $ -3x^{2} + 4x + 4 $ but not $ 4x - 3 $ or $ -3x^{2} - 3x + 4 $.)

• Then, if the equation $P_{k}(x)=0$ has no real solutions, the game is stopped. Otherwise, Tim chooses a real number $r$ such that $P_{k}(r)=0$ and writes it on the blackboard, so there is now one more number on the blackboard.

Determine whether Tim can ensure that the game is never stopped, no matter what Tam does.

Let $n \geqslant 3$ be an integer, and let $S_n$ be the set of points $(x, y)$ in the plane such that $x$ and $y$ are nonnegative integers and $x + y \lt n$. A line in the plane is called interesting if it is not parallel to the $x$-axis, the $y$-axis, or the line $x + y = 0$.

Determine all nonnegative integers k such that there exist n lines satisfying both of the following:

- the union of the $n$ lines contains every point of $S_{n}$, and

• exactly k of the lines are interesting.

There is a row of $n$ paddocks, labelled from left to right with the integers 1 to $n$, where $n \geq 3$. Skippy the Kangaroo grazes in the paddocks according to the following rule:

If Skippy is grazing in paddock $k$, then she makes a sequence of $k$ hops from a paddock to an adjacent paddock. The first of the $k$ hops is always to the right, unless Skippy is in paddock $n$, in which case it is to the left. Each of the following $k-1$ hops is in the same direction as the previous hop, unless Skippy is in paddock 1 or $n$. Skippy grazes in the paddock that she is in after the $k^{\mathrm{th}}$ hop.

For example, if n = 8 and Skippy is grazing in paddock 3, then the next four paddocks she grazes in are 6, 4, 8 and 2, in this order.

Skippy continues grazing in this way indefinitely. A paddock is overgrazed if Skippy eventually grazes in it, regardless of the paddock that she starts in. Determine all $ n \geq 3 $ for which there is exactly one overgrazed paddock.

There are 2025 white balls and 2025 black balls arranged in a row. A balanced segment is a contiguous nonempty segment of balls that contains the same number of white balls as black balls. A balanced removal is the operation of selecting a balanced segment S, removing all the balls in S, and shifting left the balls that were to the right of S so that the remaining balls form a contiguous row.

Determine the smallest positive integer $N$ satisfying the following property: for every configuration of balls and for every integer $k$ satisfying $0 \leq k \leq 2025$, there exists a sequence of at most $N$ balanced removals after which there are exactly $2k$ remaining balls.

Bluey is placing lollies on a $ 1000 \times 1000 $ grid. Initially, every cell of the grid is empty. At each step, Bluey chooses a row or column in which the total number of lollies is a multiple of 3, chooses an empty cell in this row or column, and places a lolly in it. If there is no such row or column, Bluey stops.

Determine the maximum number of lollies that Bluey can place.

Let $n$ be a positive integer, and let $(a_1, a_2, \ldots, a_n)$ be any $n$-tuple of distinct integers. An inversion is a pair $(i, j)$ of integers satisfying $1 \leq i \lt j \leq n$ and $a_i \gt a_j$. An inversion $(i, j)$ is called $\text{odd}$ if $j - i$ is odd. Let $A$ be the number of all inversions, and let $B$ be the number of odd inversions.

(a) Prove that $A \leq 5B$ for all $n$ and all $n$-tuples $(a_1, a_2, \ldots, a_n)$.

(b) Prove that there exist an n and an n-tuple $ (a_1, a_2, \ldots, a_n) $ for which A > 4.99B.

On a $ 45 \times 45 $ square grid there is an echidna. From any cell, the echidna can move to any other cell that shares a side. The echidna makes a sequence of 2024 moves, after which it has visited each cell exactly once. Prove that it is possible to write the numbers from 1 to 2025, one in each cell, in such a way that:

• For any pair of adjacent cells in the same row, the cell containing the larger number was visited earlier.

- For any pair of adjacent cells in the same column, the cell containing the larger number was visited later.

Let $P$ be a regular 100-gon. An Aussie triangulation is formed by dividing $P$ into a set $T$ of non-overlapping triangles such that:

- there are exactly 2025 different points, including the 100 vertices of $P$, that are a vertex of at least one triangle in $T$, and

- no three of these 2025 points are collinear.

A quokkalateral is a convex quadrilateral that consists of two triangles in T sharing a common side. Two quokkalaterals may share a triangle in T.

Determine the minimum number of quokkalaterals among all Aussie triangulations.

Consider a $ 2025 \times 2025 $ grid of unit squares. We place on the grid some number of rectangular tiles, possibly of different sizes, such that each side of every tile lies on a grid line and every unit square is covered by at most one tile.

Determine the minimum number of tiles we need to place so that each row and each column has exactly one unit square that is not covered by any tile.

Let $ABC$ be a triangle such that $\angle A$ is obtuse. Let $D$ and $E$ be points on sides $AB$ and $AC$, respectively, such that $BDEC$ is cyclic. Suppose the circumcircle of triangle $ADE$ intersects side $BC$ at two points $X$ and $Y$, where $B, X, Y$ and $C$ lie in that order. Let the circumcircles of triangles $BDX$ and $CEY$ be $\Omega$ and $\Gamma$, respectively. Let $P$ be a point such that $PD$ is tangent to $\Omega$ and $PE$ is tangent to $\Gamma$. Let $Q$ be a point such that $QB$ is tangent to $\Omega$ and $QC$ is tangent to $\Gamma$.

Prove that points A, P and Q are collinear.

Let $ABC$ be an acute-angled triangle. Let $I_B$ and $I_C$ be the excentres of triangle $ABC$ opposite $B$ and $C$, respectively. Let $E$ be a point on line $BA$ such that $\angle EI_B B = 90^\circ$. Let $F$ be a point on line $CA$ such that $\angle CI_C F = 90^\circ$. Let the circle with centre $I_B$ and radius $I_B E$ intersect the segment $I_B B$ at $X$. Let the circle with centre $I_C$ and radius $I_C F$ intersect the segment $I_C C$ at $Y$.

Prove that BY is perpendicular to CX.

The excentre of a triangle ABC opposite vertex B is the centre of the circle that is tangent to line segment AC, to ray BA beyond A, and to ray BC beyond C. The excentre opposite C is similarly defined.

Let $ABC$ be an acute-angled triangle with $AB \lt AC$. Let $\Gamma$ be the circumcircle of triangle $ABC$. The perpendicular from $B$ to $AC$ intersects $\Gamma$ again at $D \neq B$. Let $Q$ be the point on $\Gamma$ such that $Q \neq B$ and $AB = AQ$. Lines $BQ$ and $AC$ intersect at $R$. Line $DR$ intersects $\Gamma$ again at $S \neq D$. Segment $BC$ intersects the circumcircle of triangle $QRS$ at $T$. Lines $TQ$ and $RS$ intersect at $X$.

Prove that CX is perpendicular to AB.

Let $\Omega$ and $\Gamma$ be circles centred at $M$ and $N$, respectively, such that the radius of $\Omega$ is smaller than the radius of $\Gamma$. Suppose circles $\Omega$ and $\Gamma$ intersect at two distinct points $A$ and $B$. Line $MN$ intersects $\Omega$ at $C$ and $\Gamma$ at $D$, such that points $C, M, N$ and $D$ lie on the line in that order. Let $P$ be the circumcentre of triangle $ACD$. Line $AP$ intersects $\Omega$ again at $E \neq A$. Line $AP$ intersects $\Gamma$ again at $F \neq A$. Let $H$ be the orthocentre of triangle $PMN$.

Prove that the line passing through H parallel to AP is tangent to the circumcircle of triangle BEF.