Olympiad

Let \(a_1, b_2, \dots\) and \(b_1, b_2, \dots\) be sequences of real numbers for which \(a_1 > b_1\) and \[a_{n+1} = a_n^2 - 2b_n\] \[b_{n+1} = b_n^2 - 2a_n\] for all positive integers \(n\). Prove that \(a_1, a_2, \dots\) is eventually increasing.

Let \(n\) be a positive integer. Prove that among the first \(n\) multiples of three, there are more numbers with an even number of 1s in binary than numbers with an odd number of 1s in binary.

Let \(O = (0,0)\) and call a lattice triangle \(ABC\) marine if \([ABO] = [BCO] = [CAO] = \frac{1}{2}\). Find all points in \(\mathbb{R}^2\) that don't lie in the interior of any marine triangle.

\(ABC\)'s incircle has center \(I\) and is tangent to \(\overline{BC}\), \(\overline{CA}\), and \(\overline{AB}\) at \(D\), \(E\), and \(F\). If \((ADI)\) intersects \(\overline{AB}\) and \(\overline{AC}\) again at \(X\) and \(Y\), prove \(\overline{EF}\) bisects \(\overline{XY}\).

Each point in the plane is labeled with a real number. Prove that there exist two distinct points \(P\) and \(Q\) such that their labels differ by less than the distance from \(P\) to \(Q\).

For every pair of integers \(a, b \in \mathbb{Z}^+\) and function \(f: \mathbb{Z}/a\mathbb{Z} \to \mathbb{Z}/b\mathbb{Z}\), let \(\Delta f : \mathbb{Z}/a\mathbb{Z} \to \mathbb{Z}/b\mathbb{Z}\) denote the function \(n \mapsto f(n+1) - f(n)\). In terms of \(a\) and \(b\), determine the number of functions \(f : \mathbb{Z}/a\mathbb{Z} \to \mathbb{Z}/b\mathbb{Z}\) for which \(\Delta^N f = f\) for some \(N \in \mathbb{Z}^+\).

Let distinct points \(P\) and \(Q\) lie inside scalene triangle \(ABC\). Suppose that the angle bisectors of \(\angle PAQ\), \(\angle PBQ\), and \(\angle PCQ\) are altitudes of triangle \(ABC\). Prove that the midpoint of \(\overline{PQ}\) lies on the Euler line of triangle \(ABC\).

Quadrilaterals \(ABCD \sim A_1B_1C_1D_1 \sim A_2B_2C_2D_2\) lie in the plane such that \[ \overline{A_1B_2} \subset \overline{AB}, \: \overline{B_1C_2} \subset \overline{BC}, \: \overline{C_1D_2} \subset \overline{CD}, \text{ and } \overline{D_1A_2} \subset \overline{DA}. \] Prove that \(\overline{AC} \cap \overline{BD}\), \(\overline{A_1C_1} \cap \overline{B_1D_1}\), and \(\overline{A_2C_2} \cap \overline{B_2D_2}\) are collinear.

A circle through \(B\) and a circle through \(C\) are both externally tangent to the incircle and \(A\)-excircle of \(\triangle ABC\). Prove \(\overline{BC}\) cuts the circles into congruent chords.

Find all primes \(p \geq 5\) for which \[ \left\{2^{-1}, 3^{-1}, \ldots, \left(\frac{p-1}{2}\right)^{-1}\right\} = \left\{-2, -3, \ldots, -\frac{p-1}{2}\right\} \pmod{p}. \]

Fix an odd integer \(n\), and place \(\frac{1}{2}(n^2-1)\) nonoverlapping dominoes in an \(n \times n\) grid. Let \(k\) be the number of distinct grid-aligned configurations obtainable by sliding the dominoes. In terms of \(n\), find all possible values of \(k\).

The foot from \(C\) to the \(A\)-median of triangle \(ABC\) is \(P\), and the circumcircle of triangle \(ABP\) meets \(\overline{BC}\) again at \(Q\). Prove that the midpoint of \(\overline{AQ}\) is equidistant from \(B\) and \(C\).

Philena and Nathan are playing a game. First, Nathan secretly chooses an ordered pair \((x, y)\) of positive integers such that \(x \leq 20\) and \(y \leq 23\). (Philena knows that Nathan's pair must satisfy \(x \leq 20\) and \(y \leq 23\).) The game then proceeds in rounds; in every round, Philena chooses an ordered pair \((a, b)\) of positive integers and tells it to Nathan; Nathan says YES if \(x \leq a\) and \(y \leq b\), and NO otherwise. Find, with proof, the smallest positive integer \(N\) for which Philena has a strategy that guarantees she can be certain of Nathan's pair after at most \(N\) rounds.

Define a width-one strip to be a rectangle with width 1 or height 1. An \(n \times n\) square is dissected into width-one strips such that neighboring strips share exactly one unit of perimeter. What is the minimum possible number of strips?

In terms of \(n \in \mathbb{Z}^+\), find the smallest integer \(k\) for which \((0, 1)^2 \setminus S\) is a union of \(k\) axis-aligned open rectangles for every set \(S \subset (0, 1)^2\) of size \(n\).

Convex pentagon \(ABCDE\) satisfies \(ABE \sim BEC \sim EDB\). Prove \(\overline{BE}\), \(\overline{CD}\), and the tangent to \((ACD)\) at \(A\) concur.

Find all pairs of primes \((p, q)\) for which \(p - q\) and \(pq - q\) are both square.

Find all \(m \in \mathbb{Z}^+\) for which there exists an infinite nonconstant sequence in \(\mathbb{Z}/m\mathbb{Z}\) that is both arithmetic and geometric.

Let \(M\) be a finite set of lattice points and \(n\) be a positive integer. A mine-avoiding path is a path of lattice points with length \(n\), beginning at \((0,0)\) and ending at a point on the line \(x + y = n\), that does not contain any point in \(M\). Prove that if there exists a mine-avoiding path, then there exist at least \(2^{n - |M|}\) mine-avoiding paths.

Let \(a\) and \(b\) be positive integers such that there are infinitely many pairs of positive integers \((m, n)\) such that \(m^2 + an + b\) and \(n^2 + am + b\) are both square. Prove that \(a \mid 2b\).

Points \(X\) and \(Y\) lie on sides \(\overline{AB}\) and \(\overline{CD}\) of cyclic quadrilateral \(ABCD\) with center \(O\). If \((ADX)\) and \((BCY)\) meet \(\overline{XY}\) again at \(P\) and \(Q\), prove \(OP = OQ\).

In an \(n \times n\) square of \(n^2\) real numbers, maximize the number of numbers greater than the average of its row but less than the average of its column.

Evan has a convex \(n\)-gon in the plane for a given positive integer \(n\ge 3\) and wishes to construct the centroid of its vertices. He has no standard ruler or compass, but he does have a device with which he can dissect the segment between two given points into \(m\) equal parts. For what \(m\) can Evan necessarily accomplish his task?