VN TST 2019

A country has $n\ge2$ cities. Every pair is joined by a direct two-way air route. Licences for these routes are to be given to airlines subject to:
(i) Each route is licensed to exactly one airline.
(ii) Using routes of any one airline, one can travel from any city to every other city.
What is the greatest possible number of airlines?

For every positive integer $n$, prove that the polynomial
$$P_n(x)=\sum_{k=0}^n2^k\binom{2n}{2k}x^k(x-1)^{n-k}$$
has exactly $n$ distinct real roots.

Let $ABC$ be an acute scalene triangle inscribed in $(O)$, with orthocenter $H$ and midpoint $M$ of $BC$. Let $D$ lie on the ray opposite to $HA$ and satisfy $DM=BC/2$. Let $D'$ be the reflection of $D$ in $BC$, and let $X=AO\cap MD$.
(a) Prove that $AM$ passes through the midpoint of $D'X$.
(b) Define $E,F$ cyclically in the same way as $D$, and $Y,Z$ cyclically in the same way as $X$. Let $S$ be the intersection of the tangents to $(O)$ at $B,C$. Let $G$ be the perpendicular projection onto $AO$ of the midpoint of $AS$. Prove that a point has equal powers with respect to all four circles $(SGO),(BYE),(CFZ),(O)$.

Find all triples of positive integers $(x,y,z)$ satisfying $2^x+1=7^y+2^z$.

Let a scalene triangle $ABC$ have circumcircle $(O)$ and incircle $(I)$. Let $E=BI\cap AC$ and $F=CI\cap AB$. The circle through $E$ tangent to the line $OB$ at $B$ meets $(O)$ again at $M$; the circle through $F$ tangent to $OC$ at $C$ meets $(O)$ again at $N$. Let $P,Q$ be the second intersections of $ME,NF$, respectively, with $(O)$. Put $K=EF\cap BC$, $G=PQ\cap BC$, and $H=PQ\cap EF$. Prove that the median from $G$ in triangle $GHK$ is perpendicular to $OI$.

A bug starts at coordinate $x=1$ on the real number line. At each jump, from $x=a$ it may move to $x=a+2$ or $x=a/2$. Prove that the number of distinct positions, including the initial position, reachable in at most $n$ jumps is $F_{n+4}-(n+4)$, where $F_0=F_1=1$ and $F_n=F_{n-1}+F_{n-2}$ for $n\ge2$.