RMM 2017

(a) Prove that every positive integer $n$ can be written uniquely in the form

$$n=\sum_{j=1}^{2 k+1}(-1)^{j-1} 2^{m_{j}}$$

where $k \geq 0$ and $0 \leq m_{1}<m_{2}<\cdots<m_{2 k+1}$ are integers. This number $k$ is called the weight of $n$. (b) Find (in closed form) the difference between the number of positive integers at most $2^{2017}$ with even weight and the number of positive integers at most $2^{2017}$ with odd weight.

Determine all positive integers $n$ satisfying the following condition: for every monic polynomial $P$ of degree at most $n$ with integer coefficients, there exists a positive integer $k \leq n$, and $k+1$ distinct integers $x_{1}, x_{2}, \ldots, x_{k+1}$ such that

$$P\left(x_{1}\right)+P\left(x_{2}\right)+\cdots+P\left(x_{k}\right)=P\left(x_{k+1}\right)$$

Semen Petrov, Russia Note. A polynomial is monic if the coefficient of the highest power is one.

Let $n$ be an integer greater than 1 and let $X$ be an $n$-element set. A non-empty collection of subsets $A_{1}, \ldots, A_{k}$ of $X$ is tight if the union $A_{1} \cup \cdots \cup A_{k}$ is a proper subset of $X$ and no element of $X$ lies in exactly one of the $A_{i}$ s. Find the largest cardinality of a collection of proper non-empty subsets of $X$, no non-empty subcollection of which is tight.

Note. A subset $A$ of $X$ is proper if $A \neq X$. The sets in a collection are assumed to be distinct. The whole collection is assumed to be a subcollection.

In the Cartesian plane, let $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ be the graphs of the quadratic functions $f_{1}(x)=p_{1} x^{2}+q_{1} x+r_{1}$ and $f_{2}(x)=p_{2} x^{2}+q_{2} x+r_{2}$, where $p_{1}>0>p_{2}$. The graphs $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ cross at distinct points $A$ and $B$. The four tangents to $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ at $A$ and $B$ form a convex quadrilateral which has an inscribed circle. Prove that the graphs $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ have the same axis of symmetry.

Fix an integer $n \geq 2$. An $n \times n$ sieve is an $n \times n$ array with $n$ cells removed so that exactly one cell is removed from every row and every column. A stick is a $1 \times k$ or $k \times 1$ array for any positive integer $k$. For any sieve $A$, let $m(A)$ be the minimal number of sticks required to partition $A$. Find all possible values of $m(A)$, as $A$ varies over all possible $n \times n$ sieves.

Palmer Mebane and Nikolai Beluhov

Let $A B C D$ be any convex quadrilateral and let $P, Q, R, S$ be points on the segments $A B, B C, C D$, and $D A$, respectively. It is given that the segments $P R$ and $Q S$ dissect $A B C D$ into four quadrilaterals, each of which has perpendicular diagonals. Show that the points $P, Q, R, S$ are concyclic.

NikOlai Beluhov