SMO 2023 Senior Round 2

Let $ABCD$ be a square, $E$ be a point on the side $DC$, $F$ and $G$ be the feet of the altitudes from $B$ to $AE$ and from $A$ to $BE$, respectively. Suppose $DF$ and $CG$ intersect at $H$. Prove that $\angle AHB=90^\circ$.

Find all positive integers $k$ such that there exist positive integers $a,b$ such that $a^2+4=(k^2-4)b^2$.

Let $n$ be a positive integer. There are $n$ islands with $n-1$ bridges connecting them such that one can travel from any island to another. One afternoon, a fire breaks out in one of the islands. Every morning, it spreads to all neighbouring islands. (Two islands are neighbours if they are connected by a bridge.) To control the spread, one bridge is destroyed every night until the fire has nowhere to spread the next day. Let $X$ be the minimum possible number of bridges one has to destroy before the fire stops spreading. Find the maximum possible value of $X$ over all possible configurations of bridges and islands where the fire starts at.

Find all positive integers $m,n$ satisfying $n!+2^{n-1}=2^m$.

Colour a $20000\times20000$ square grid using $2000$ different colours with $1$ colour in each square. Two squares are neighbours if they share a vertex. A path is a sequence of squares so that $2$ successive squares are neighbours. Mark $k$ of the squares. For each unmarked square $x$, there is exactly $1$ marked square $y$ of the same colour so that $x$ and $y$ are connected by a path of squares of the same colour. For any $2$ marked squares of the same colour, any path connecting them must pass through squares of all the colours. Find the maximum value of $k$.