Task 4. Determine all integers $n \geq 2$ for which

$$
i+j \equiv\left(\begin{array}{c}
n \\
i
\end{array}\right)+\left(\begin{array}{c}
n \\
j
\end{array}\right) \bmod 2
$$

for all $i$ and $j$ with $0 \leq i \leq j \leq n$.
Solution. We first show that $n$ satisfies the condition if and only if $\left(\begin{array}{c}n \\ i\end{array}\right) \equiv i+1 \bmod 2$ for all $i$ with $0 \leq i \leq n$. Suppose that $\left(\begin{array}{c}n \\ i\end{array}\right) \equiv i+1 \bmod 2$ for all $i$, then $\left(\begin{array}{c}n \\ i\end{array}\right)+\left(\begin{array}{c}n \\ j\end{array}\right) \equiv i+1+j+1 \equiv i+j \bmod 2$ for all $i$ and $j$. Thus, $n$ satisfies the condition in the problem. Conversely, suppose that $n$ satisfies the condition. Since $\left(\begin{array}{l}n \\ 0\end{array}\right)=1$, it follows that $i \equiv 1+\left(\begin{array}{l}n \\ i\end{array}\right) \bmod 2$ for all $i$, so $\left(\begin{array}{c}n \\ i\end{array}\right) \equiv i-1 \equiv i+1 \bmod 2$ for all $i$.

Write $n$ as $n=2^{k}+m$ with $0 \leq m<2^{k}$. Since $n \geq 2$, we may assume $k \geq 1$. Consider

$$
\left(\begin{array}{c}
n \\
2^{k}-2
\end{array}\right)=\left(\begin{array}{c}
2^{k}+m \\
2^{k}-2
\end{array}\right)=\frac{\left(2^{k}+m\right)\left(2^{k}+m-1\right) \cdots(m+4)(m+3)}{\left(2^{k}-2\right)\left(2^{k}-3\right) \cdots 2 \cdot 1} .
$$

The product in the denominator contains $\left\lfloor\frac{2^{k}-2}{2}\right\rfloor$ factors divisible by $2,\left\lfloor\frac{2^{k}-2}{4}\right\rfloor$ factors divisible

![](https://cdn.mathpix.com/cropped/2024_04_17_ed5b183cc65c6326e1e9g-5.jpg?height=68&width=1607&top_left_y=1267&top_left_x=237)
The product in the numerator consists of $2^{k}-2$ consecutive factors and therefore contains at least $\left\lfloor\frac{2^{k}-2}{2}\right\rfloor$ factors divisible by 2, at least $\left\lfloor\frac{2^{k}-2}{4}\right\rfloor$ factors divisible by 4, ..., at least $\left\lfloor\frac{2^{k}-2}{2^{k-1}}\right\rfloor$ factors divisible by $2^{k-1}$. Thus, the product in the numerator contains at least as many factors of 2 as the product in the denominator. The product in the numerator contains more factors of 2 than the product in the denominator if $2^{k}$ appears as a factor in the numerator. This is the case if $m+3 \leq 2^{k}$, or equivalently if $m \leq 2^{k}-3$. Therefore, if $m \leq 2^{k}-3$, then $\left(\begin{array}{c}n \\ 2^{k}-2\end{array}\right)$ is even, while $2^{k}-2$ is also even. Thus, $n=2^{k}+m$ does not satisfy the condition.

Therefore, $n$ can only satisfy the condition if there is a $k \geq 2$ such that $2^{k}-2 \leq n \leq 2^{k}-1$. If $n$ is odd, then $\left(\begin{array}{l}n \\ 0\end{array}\right)+\left(\begin{array}{l}n \\ 1\end{array}\right)=1+n \equiv 0 \bmod 2$, so $n$ does not satisfy the condition. Therefore, $n$ can only satisfy the condition if it is of the form $n=2^{k}-2$ with $k \geq 2$. Now suppose that $n$ is indeed of this form. We will show that $n$ satisfies the condition. We have

$$
\left(\begin{array}{c}
2^{k}-2 \\
c
\end{array}\right)=\frac{\left(2^{k}-2\right)\left(2^{k}-3\right) \cdots\left(2^{k}-c\right)\left(2^{k}-c-1\right)}{c \cdot(c-1) \cdots 2 \cdot 1} .
$$

The number of factors of 2 in $2^{k}-i$ is equal to the number of factors of 2 in $i$ for $1 \leq i \leq 2^{k}-1$. Therefore, the number of factors of 2 in the numerator is equal to the number of factors of 2 in the product $(c+1) \cdot c \cdot(c-1) \cdots 2$, which is the number of factors of 2 in the denominator plus the number of factors of 2 in $c+1$. Thus, $\left(\begin{array}{c}2^{k}-2 \\ c\end{array}\right)$ is even if and only if $c$ is odd. This means that $n=2^{k}-2$ satisfies the condition.

We conclude that $n$ satisfies the condition if and only if $n=2^{k}-2$ with $k \geq 2$.