RMM 2012

Given a finite group of boys and girls, a covering set of boys is a set of boys such that every girl knows at least one boy in that set; and a covering set of girls is a set of girls such that every boy knows at least one girl in that set. Prove that the number of covering sets of boys and the number of covering sets of girls have the same parity. (Acquaintance is assumed to be mutual.)

Given a triangle $A B C$, let $D, E$, and $F$ respectively denote the midpoints of the sides $B C, C A$, and $A B$. The circle $B C F$ and the line $B E$ meet again at $P$, and the circle $A B E$ and the line $A D$ meet again at $Q$. Finally, the lines $D P$ and $F Q$ meet at $R$. Prove that the centroid $G$ of the triangle $A B C$ lies on the circle $P Q R$.

Each positive integer number is coloured red or blue. A function $f$ from the set of positive integer numbers into itself has the following two properties: (a) if $x \leq y$, then $f(x) \leq f(y)$; and (b) if $x, y$ and $z$ are all (not necessarily distinct) positive integer numbers of the same colour and $x+y=z$, then $f(x)+f(y)=f(z)$.

Prove that there exists a positive number $a$ such that $f(x) \leq a x$ for all positive integer numbers $x$.

Prove that there are infinitely many positive integer numbers $n$ such that $2^{2^{n}+1}+1$ be divisible by $n$, but $2^{n}+1$ be not.

Given a positive integer number $n \geq 3$, colour each cell of an $n \times n$ square array one of $\left[(n+2)^{2} / 3\right]$ colours, each colour being used at least once. Prove that the cells of some $1 \times 3$ or $3 \times 1$ rectangular subarray have pairwise distinct colours.

Let $A B C$ be a triangle and let $I$ and $O$ respectively denote its incentre and circumcentre. Let $\omega_{A}$ be the circle through $B$ and $C$ and tangent to the incircle of the triangle $A B C$; the circles $\omega_{B}$ and $\omega_{C}$ are defined similarly. The circles $\omega_{B}$ and $\omega_{C}$ through $A$ meet again at $A^{\prime}$; the points $B^{\prime}$ and $C^{\prime}$ are defined similarly. Prove that the lines $A A^{\prime}, B B^{\prime}$ and $C C^{\prime}$ are concurrent at a point on the line $I O$.