RMM 2024

Let $n$ be a positive integer. Initially, a bishop is placed in each square of the top row of a $2^{n} \times 2^{n}$ chessboard; those bishops are numbered from 1 to $2^{n}$, from left to right. A jump is a simultaneous move made by all bishops such that the following conditions are satisfied:

• each bishop moves diagonally, in a straight line, some number of squares, and
• at the end of the jump, the bishops all stand in different squares of the same row.

Find the total number of permutations $\sigma$ of the numbers $1,2, \ldots, 2^{n}$ with the following property: There exists a sequence of jumps such that all bishops end up on the bottom row arranged in the order $\sigma(1), \sigma(2), \ldots, \sigma\left(2^{n}\right)$, from left to right.

Consider an odd prime $p$ and a positive integer $N<50 p$. Let $a_{1}, a_{2}, \ldots, a_{N}$ be a list of positive integers less than $p$ such that any specific value occurs at most $\frac{51}{100} N$ times and $a_{1}+a_{2}+\cdots+a_{N}$ is not divisible by $p$. Prove that there exists a permutation $b_{1}, b_{2}, \ldots, b_{N}$ of the $a_{i}$ such that, for all $k=1,2, \ldots, N$, the sum $b_{1}+b_{2}+\cdots+b_{k}$ is not divisible by $p$.

Given a positive integer $n$, a set $\mathcal{S}$ is $n$-admissible if

• each element of $\mathcal{S}$ is an unordered triple of integers in $\{1,2, \ldots, n\}$,
• $|\mathcal{S}|=n-2$, and
• for each $1 \leq k \leq n-2$ and each choice of $k$ distinct $A_{1}, A_{2}, \ldots, A_{k} \in \mathcal{S}$,

$$\left|A_{1} \cup A_{2} \cup \cdots \cup A_{k}\right| \geq k+2$$

Is it true that, for all $n>3$ and for each $n$-admissible set $\mathcal{S}$, there exist pairwise distinct points $P_{1}, \ldots, P_{n}$ in the plane such that the angles of the triangle $P_{i} P_{j} P_{k}$ are all less than $61^{\circ}$ for any triple $\{i, j, k\}$ in $\mathcal{S}$ ?

Each problem is worth 7 marks. Time allowed: $4 \frac{1}{2}$ hours.

Fix integers $a$ and $b$ greater than 1 . For any positive integer $n$, let $r_{n}$ be the (non-negative) remainder that $b^{n}$ leaves upon division by $a^{n}$. Assume there exists a positive integer $N$ such that $r_{n}<2^{n} / n$ for all integers $n \geq N$. Prove that $a$ divides $b$.

Let $B C$ be a fixed segment in the plane, and let $A$ be a variable point in the plane not on the line $B C$. Distinct points $X$ and $Y$ are chosen on the rays $\overrightarrow{C A}$ and $\overrightarrow{B A}$, respectively, such that $\angle C B X=\angle Y C B=\angle B A C$. Assume that the tangents to the circumcircle of $A B C$ at $B$ and $C$ meet line $X Y$ at $P$ and $Q$, respectively, such that the points $X, P, Y$, and $Q$ are pairwise distinct and lie on the same side of $B C$. Let $\Omega_{1}$ be the circle through $X$ and $P$ centred on $B C$. Similarly, let $\Omega_{2}$ be the circle through $Y$ and $Q$ centred on $B C$. Prove that $\Omega_{1}$ and $\Omega_{2}$ intersect at two fixed points as $A$ varies.

A polynomial $P$ with integer coefficients is square-free if it is not expressible in the form $P=Q^{2} R$, where $Q$ and $R$ are polynomials with integer coefficients and $Q$ is not constant. For a positive integer $n$, let $\mathcal{P}_{n}$ be the set of polynomials of the form

$$1+a_{1} x+a_{2} x^{2}+\cdots+a_{n} x^{n}$$

with $a_{1}, a_{2}, \ldots, a_{n} \in\{0,1\}$. Prove that there exists an integer $N$ so that, for all integers $n \geq N$, more than $99 \%$ of the polynomials in $\mathcal{P}_{n}$ are square-free.

Each problem is worth 7 marks. Time allowed: $4 \frac{1}{2}$ hours.