In a country there are $n\geq 2$ cities. Any two cities has exactly one two-way airway. The government wants to license several airlines to take charge of these airways with such following conditions: i) Every airway can be licensed to exactly one airline. ii) By choosing one arbitrary airline, we can move from a city to any other cities, using only flights from this airline. What is the maximum number of airlines that the government can license to satisfy all of these conditions?

For each positive integer $n$, show that the polynomial: $$P_n(x)=\sum _{k=0}^n2^k\binom{2n}{2k}x^k(x-1)^{n-k}$$has $n$ real roots.

Given an acute scalene triangle $ABC$ inscribed in circle $(O)$. Let $H$ be its orthocenter and $M$ be the midpoint of $BC$. Let $D$ lie on the opposite rays of $HA$ so that $BC=2DM$. Let $D'$ be the reflection of $D$ through line $BC$ and $X$ be the intersection of $AO$ and $MD$. a) Show that $AM$ bisects $D'X$. b) Similarly, we define the points $E,F$ like $D$ and $Y,Z$ like $X$. Let $S$ be the intersection of tangent lines from $B,C$ with respect to $(O)$. Let $G$ be the projection of the midpoint of $AS$ to the line $AO$. Show that there exists a point with the same power to all the circles $(BEY),(CFZ),(SGO)$ and $(O)$.

Find all triplets of positive integers $(x, y, z)$ such that $2^x+1=7^y+2^z$.

Given a scalene triangle $ABC$ inscribed in the circle $(O)$. Let $(I)$ be its incircle and $BI,CI$ cut $AC,AB$ at $E,F$ respectively. A circle passes through $E$ and touches $OB$ at $B$ cuts $(O)$ again at $M$. Similarly, a circle passes through $F$ and touches $OC$ at $C$ cuts $(O)$ again at $N$. $ME,NF$ cut $(O)$ again at $P,Q$. Let $K$ be the intersection of $EF$ and $BC$ and let $PQ$ cuts $BC$ and $EF$ at $G,H$, respectively. Show that the median correspond to $G$ of the triangle $GHK$ is perpendicular to $IO$.

In the real axis, there is bug standing at coordinate $x=1$. Each step, from the position $x=a$, the bug can jump to either $x=a+2$ or $x=\frac{a}{2}$. Show that there are precisely $F_{n+4}-(n+4)$ positions (including the initial position) that the bug can jump to by at most $n$ steps. Recall that $F_n$ is the $n^{th}$ element of the Fibonacci sequence, defined by $F_0=F_1=1$, $F_{n+1}=F_n+F_{n-1}$ for all $n\geq 1$.