Prove that for each positive integer $ n$, there are pairwise relatively prime integers $ k_0,k_1,\ldots,k_n$, all strictly greater than $ 1$, such that $ k_0k_1\ldots k_n-1$ is the product of two consecutive integers.

Click for solution We need $ k_0k_1\cdots k_n = a(a + 1) + 1 = a^2 + a + 1$. Start with $ a^2 + a + 1 = (a - \varepsilon)(a - \overline\varepsilon)$, where $ \varepsilon = \cos \frac {2\pi}{3} + i \sin \frac {2\pi}{3}$. Then we would like to find $ b$ such that \[ (a^2 + a + 1)(b^2 + b + 1) = c^2 + c + 1, \] so we think that we need $ (a - \varepsilon)(b - \varepsilon) = ab + \overline\varepsilon - (a + b)\varepsilon$, so we need $ a + b = 0$, and so $ b = - a$, and we get \[ (a^2 + a + 1) (( - a)^2 + ( - a) + 1) = a^4 + a^2 + 1 \] and it's easy to see that $ a^2 + a + 1$ and $ a^2 - a + 1$ are coprime (as odd integers). Which implies that $ a^{2^n} + a^{2^{n - 1}} + 1$ will contain at least $ n + 1$ different prime factors, so we are done.

Let $ ABC$ be an acute, scalene triangle, and let $ M$, $ N$, and $ P$ be the midpoints of $ \overline{BC}$, $ \overline{CA}$, and $ \overline{AB}$, respectively. Let the perpendicular bisectors of $ \overline{AB}$ and $ \overline{AC}$ intersect ray $ AM$ in points $ D$ and $ E$ respectively, and let lines $ BD$ and $ CE$ intersect in point $ F$, inside of triangle $ ABC$. Prove that points $ A$, $ N$, $ F$, and $ P$ all lie on one circle.

Let $n$ be a positive integer. Denote by $S_n$ the set of points $(x, y)$ with integer coordinates such that \[ \left\lvert x\right\rvert + \left\lvert y + \frac{1}{2} \right\rvert < n. \] A path is a sequence of distinct points $(x_1 , y_1), (x_2, y_2), \ldots, (x_\ell, y_\ell)$ in $S_n$ such that, for $i = 2, \ldots, \ell$, the distance between $(x_i , y_i)$ and $(x_{i-1} , y_{i-1} )$ is $1$ (in other words, the points $(x_i, y_i)$ and $(x_{i-1} , y_{i-1} )$ are neighbors in the lattice of points with integer coordinates). Prove that the points in $S_n$ cannot be partitioned into fewer than $n$ paths (a partition of $S_n$ into $m$ paths is a set $\mathcal{P}$ of $m$ nonempty paths such that each point in $S_n$ appears in exactly one of the $m$ paths in $\mathcal{P}$).

Let $ \mathcal{P}$ be a convex polygon with $ n$ sides, $ n\ge3$. Any set of $ n - 3$ diagonals of $ \mathcal{P}$ that do not intersect in the interior of the polygon determine a triangulation of $ \mathcal{P}$ into $ n - 2$ triangles. If $ \mathcal{P}$ is regular and there is a triangulation of $ \mathcal{P}$ consisting of only isosceles triangles, find all the possible values of $ n$.

Three nonnegative real numbers $ r_1$, $ r_2$, $ r_3$ are written on a blackboard. These numbers have the property that there exist integers $ a_1$, $ a_2$, $ a_3$, not all zero, satisfying $ a_1r_1 + a_2r_2 + a_3r_3 = 0$. We are permitted to perform the following operation: find two numbers $ x$, $ y$ on the blackboard with $ x \le y$, then erase $ y$ and write $ y - x$ in its place. Prove that after a finite number of such operations, we can end up with at least one $ 0$ on the blackboard.

At a certain mathematical conference, every pair of mathematicians are either friends or strangers. At mealtime, every participant eats in one of two large dining rooms. Each mathematician insists upon eating in a room which contains an even number of his or her friends. Prove that the number of ways that the mathematicians may be split between the two rooms is a power of two (i.e., is of the form $ 2^k$ for some positive integer $ k$).

These problems are copyright $\copyright$ Mathematical Association of America.