ISL 2005

This ISL 2005 problem has not been used in any TST I know. A pity, since it is a nice problem, but in its shortlist formulation, it is absolutely incomprehensible. Here is a mathematical restatement of the problem:

Let $k$ be a nonnegative integer.

A forest consists of rooted (i. e. oriented) trees. Each vertex of the forest is either a leaf or has two successors. A vertex $v$ is called an extended successor of a vertex $u$ if there is a chain of vertices $u_{0}=u$ , $u_{1}$ , $u_{2}$ , ..., $u_{t-1}$ , $u_{t}=v$ with $t>0$ such that the vertex $u_{i+1}$ is a successor of the vertex $u_{i}$ for every integer $i$ with $0\leq i\leq t-1$ . A vertex is called dynastic if it has two successors and each of these successors has at least $k$ extended successors.

Prove that if the forest has $n$ vertices, then there are at most $\frac{n}{k+2}$ dynastic vertices.

Let $ABC$ be a triangle, and $M$ the midpoint of its side $BC$ . Let $\gamma$ be the incircle of triangle $ABC$ . The median $AM$ of triangle $ABC$ intersects the incircle $\gamma$ at two points $K$ and $L$ . Let the lines passing through $K$ and $L$ , parallel to $BC$ , intersect the incircle $\gamma$ again in two points $X$ and $Y$ . Let the lines $AX$ and $AY$ intersect $BC$ again at the points $P$ and $Q$ . Prove that $BP = CQ$ .

Denote by $d(n)$ the number of divisors of the positive integer $n$ . A positive integer $n$ is called highly divisible if $d(n) > d(m)$ for all positive integers $m < n$ . Two highly divisible integers $m$ and $n$ with $m < n$ are called consecutive if there exists no highly divisible integer $s$ satisfying $m < s < n$ .

(a) Show that there are only finitely many pairs of consecutive highly divisible integers of the form $(a, b)$ with $a\mid b$ .

(b) Show that for every prime number $p$ there exist infinitely many positive highly divisible integers $r$ such that $pr$ is also highly divisible.

Let $P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots+a_{0}$ , where $a_{0},\ldots,a_{n}$ are integers, $a_{n}>0$ , $n\geq 2$ . Prove that there exists a positive integer $m$ such that $P(m!)$ is a composite number.