Iranian Mathematical Olympiad

Lemma. Suppose $n \ge 2$ is an integer, then all of the numbers $\begin{pmatrix} n \\ 0 \end{pmatrix}, \begin{pmatrix} n \\ 1 \end{pmatrix}, \dots, \begin{pmatrix} n \\ n \end{pmatrix}$ are odd if and only if $n = 2^k - 1$ for an integer $k \ge 2$.

Proof. For an integer $t$, let $v(t)$ be the greatest integer $u$ such that $2^u \mid n$. We know that
" If $p, q \in \mathbb{N}$ and $0 \le p \le 2^q$ then $v(p) = v(2^q + p) = v(2^q - p)$" (1)
Because if $p = 2^a b$ with $a, b \in \mathbb{N}$ and $b$ an odd number then $a < q$ and $2^q \pm p = 2^a (2^{q-a} \pm b)$ where $2^{q-a} \pm b$ are odd numbers.
Now there is one and only one $m \in \mathbb{N}$ such that $2^m \le n < 2^{m+1}$. Let $n = 2^m + s$
with $0 \le s < 2^m$. Now consider the number $\begin{pmatrix} n \\ 2^m - 1 \end{pmatrix}$. We have
$$\begin{pmatrix} n \\ 2^m - 1 \end{pmatrix} = \begin{pmatrix} 2^m + s \\ 2^m - 1 \end{pmatrix} = \begin{pmatrix} 2^m + s \\ s + 1 \end{pmatrix} = \frac{(2^m + s)(2^m + s - 1)\cdots(2^m + 1)(2^m)}{s(s-1)\cdots(1)(s+1)}.$$
By (1) we have $v(2^m + i) = v(i)$ where $1 \le i \le s$, therefore
$$v((2^m + s) \cdots (2^m + 1)) = v(s!),$$
and by assumption $\begin{pmatrix} n \\ 2^m - 1 \end{pmatrix}$ is odd therefore $v(2^m) = v(s+1)$ and consequently
$2^m \mid s+1$ and $s+1 \ge 1$. Hence we have $2^m - 1 \le s$ and therefore $s = 2^m - 1$ and
$n = 2^m + s = 2^{m+1} - 1$.
Now if $n = 2^k - 1$ for some natural number $k$, for each $1 \le c \le n$ we have
$$\begin{pmatrix} 2^k - 1 \\ c \end{pmatrix} = \frac{(2^k - 1)(2^k - 2)\cdots(2^k - c)}{(1)(2)\cdots(c)} \quad \text{and by (1) we know for} \quad 1 \le l \le c$$
$$v(2^k - l) = v(l), \text{ so } \begin{pmatrix} 2^k - 1 \\ c \end{pmatrix} \text{ is odd for } 0 \le c \le n. \quad \square$$

Now we return to main problem:
Positive integer $n$ has the property of the problem if and only if all the numbers $\begin{pmatrix} n \\ i \end{pmatrix} - i$ ($0 \le i \le n$) have the same parity. It means that for every $0 \le i \le n-1$, $\begin{pmatrix} n \\ i \end{pmatrix}, \begin{pmatrix} n \\ i+1 \end{pmatrix}$ have different parities. So $\begin{pmatrix} n+1 \\ i+1 \end{pmatrix} = \begin{pmatrix} n \\ i \end{pmatrix} + \begin{pmatrix} n \\ i+1 \end{pmatrix}$ ($1 \le i \le n-1$) is odd
and as we know $\begin{pmatrix} n+1 \\ 0 \end{pmatrix} = 1$ is also odd. Therefore by the lemma this is equivalence
to $n+1 = 2^k - 1$ for some integer $k \ge 2$ so $n = 2^k - 2$ where $k \ge 2$ is an integer.
$\boxed{}$