IMO Hk TST

(i) This is an alternative form of Legendre's formula. Here is a simple proof of the result. Let $n = \overline{a_s a_{s-1} \cdots a_0}$ be the binary representation of $n$. Then we have
$$\begin{aligned} f(n!) &= \sum_{j=1}^{s} \left\lfloor \frac{n}{2^j} \right\rfloor = \sum_{j=1}^{s} \overline{a_s a_{s-1} \cdots a_j} (2^j) = \sum_{j=1}^{s} \sum_{k=j}^{s} a_k \cdot 2^{k-j} = \sum_{k=1}^{s} \sum_{j=1}^{k} a_k \cdot 2^{k-j} \\ &= \sum_{k=1}^{s} a_k (2^k - 1) = \sum_{k=1}^{s} a_k \cdot 2^k - \sum_{k=1}^{s} a_k = n - g(n). \end{aligned}$$

(ii) By part (a), we have
$$\begin{aligned} f\left(\frac{(2n)!}{n!n!}\right) &= f((2n)!) - 2f(n!) \\ &= [2n - g(2n)] - 2[n - g(n)] \\ &= 2g(n) - g(2n) \\ &= 2g(n) - g(n) \\ &= g(n). \end{aligned}$$
Thus, $4$ divides $\binom{2n}{n}$ if and only if $g(n) \ge 2$. This holds if and only if $n = 100\cdots0_{(2)} = 2^k$ for some nonnegative integer $k$.