For teachers / Printable sets /Stage 9 · Mixed

Stage 9 · Mixed

10 problems · IMO P2/P5; hard shortlist · mathsolympiadprep.com

Print or save as PDF The answer key prints on its own page at the end.

1. Let $n$ be a positive integer. A Nordic square is an $n \times n$ board containing all the integers from $1$ to $n^2$ so that each cell contains exactly one number. Two different cells are considered adjacent if they share a common side. Every cell that is adjacent only to cells containing larger numbers is called a valley. An uphill path is a sequence of one or more cells such that:

   (i) the first cell in the sequence is a valley,

   (ii) each subsequent cell in the sequence is adjacent to the previous cell, and

   (iii) the numbers written in the cells in the sequence are in increasing order.

   Find, as a function of $n$, the smallest possible total number of uphill paths in a Nordic square.

   Author: Nikola Petrovi?

   Combinatorics Solution and answer checking →

2. Let $n$ be a positive integer with $b$ digits and $l, r$ be non-negative integers satisfying $l + r < b$. We say that a positive integer number is a sub-divisor of $n$, if it divides the number obtained by erasing the first $l$ and last $r$ digits of $n$. (For example, sub-divisors of $143$ are $1$, $2$, $3$, $4$, $7$, $11$, $13$, $14$, $43$ and $143$.) For any positive integer $d$, let $A_d$ be the set of positive integers for which $d$ is not a sub-divisor. Find all positive integers $d$ for which the set $A_d$ is finite.

   Number theory Solution and answer checking →

3. Let $ABC$ be an acute scalene triangle. The incircle of $ABC$ touches $BC$, $CA$, $AB$ at $D$, $E$, $F$ respectively. Let $X$, $Y$, $Z$ be feet of the altitudes from $A$, $B$, $C$ to the sides $BC$, $CA$, $AB$ respectively. Let $A'$, $B'$, $C'$ be the reflections of $X$, $Y$, $Z$ in $EF$, $FD$, $DE$ respectively. Prove that triangles $ABC$ and $A'B'C'$ are similar.

   Geometry Solution and answer checking →

4. Determine the smallest positive integer $n$ for which there exists a polynomial
   $$P(X)=a_{2 n} X^{2 n}+a_{2 n-1} X^{2 n-1}+\ldots+a_{1} X+a_{0}$$
   with real coefficients that has both of the following properties:
   - For $i=0,1, \ldots, 2 n$ we have $2014 \leq a_{i} \leq 2015$.
   - There exists a real number $\xi$ with $P(\xi)=0$.

   Algebra Solution and answer checking →

5. Dexter's Laboratory has $2024$ robots, each with a program setup by Dexter. One day, his naughty sister Dee Dee intrudes and writes an integer in $\{1, 2, \dots, 113\}$ on each of the robot's forehead. Each robot detects the numbers on all other robots' foreheads, and guess its own number base on its program, individually and simultaneously.
   Find the largest positive integer $k$ such that Dexter can setup the programs so that, no matter how the numbers distribute, there are always at least $k$ robots who guess their numbers right.

   Combinatorics Solution and answer checking →

6. Let a simple polynomial function be a polynomial function $P(x)$ whose coefficients belong to the set $\{-1, 0, 1\}$. Let $n$ be a positive integer, $n > 1$. Find the smallest possible number of non-zero coefficients in a simple polynomial function of $n$th order whose values at all integral arguments are divisible by $n$.

   Answer: 2.

   Number theory Solution and answer checking →

7. A diagonal of a regular 2006-gon is called odd if its endpoints divide the boundary into two parts, each composed of an odd number of sides. Sides are also regarded as odd diagonals.
   Suppose the 2006-gon has been dissected into triangles by 2003 nonintersecting diagonals. Find the maximum possible number of isosceles triangles with two odd sides.
   (Serbia)

   Geometry Solution and answer checking →

8. Given an integer $n \ge 3$. Let $\frac{n(n-1)}{2}$ non-negative real numbers $x_{i,j}$ ($1 \le i < j \le n$) satisfy: for any $1 \le i < j < k \le n$, we have $x_{i,j} + x_{j,k} \le x_{i,k}$. Prove that:
   $$\left\lfloor \frac{n^2}{4} \right\rfloor \cdot \sum_{1 \le i < j \le n} x_{i,j}^4 \ge \left( \sum_{1 \le i < j \le n} x_{i,j}^2 \right)^2 .$$

   Algebra Solution and answer checking →

9. A $k$-set is a set with exactly $k$ elements. For a 6-set $A$ and any collection $\mathcal{F}$ of 4-sets, we say that $A$ is $\mathcal{F}$-good if there are exactly three elements $B_1, B_2, B_3$ in $\mathcal{F}$ that are subsets of $A$, and they furthermore satisfy
   $$(A \setminus B_1) \cup (A \setminus B_2) \cup (A \setminus B_3) = A.$$
   Find all $n \ge 6$ so that there exists a collection $\mathcal{F}$ of 4-subsets of $\{1, 2, \dots, n\}$ such that every 6-set $A \subset \{1, 2, \dots, n\}$ is $\mathcal{F}$-good.

   Combinatorics Solution and answer checking →

10. Find all positive integers $a_0$, $a_1$, $a_2$, $b_0$, $b_1$, $b_2$ such that
    $a_2 b_2 n^2 + a_1 b_1 n + a_0 b_0$ divides $(a_2^{2017n} + b_2)n^2 + (a_1^{2017n} + b_1)n + (a_0^{2017n} + b_0)$ for any positive integer $n$.

    Number theory Solution and answer checking →

Answer key — Stage 9 · Mixed

Worked solutions for every problem are on the site, one page per problem.

1. $2n(n - 1) + 1$ open
2. Prove it — see the worked solution open
3. Prove it — see the worked solution open
4. Prove it — see the worked solution open
5. Prove it — see the worked solution open
6. Prove it — see the worked solution open
7. Prove it — see the worked solution open
8. Prove it — see the worked solution open
9. Prove it — see the worked solution open
10. Prove it — see the worked solution open

Problems belong to the competitions that set them and are reproduced from open datasets under their licences; every problem page names its source. Free to copy for classroom use.