2021/22 AHSMC Part 1 Problem 10

The first digit of the number $n$ should be $1$ and its last digit should be $0$. The $2018$ digit locations in $n$, excluding the first, second, and last digits, can be filled arbitrarily with $0$'s and $1$'s. There are $2^{2018}$ ways to do this. For each of these choices, the second digit of $n$ is then chosen to be either $0$ or $1$, so that there are an even number of $1$'s in $n$ altogether. Thus there are $2^{2018}$ numbers $n$ satisfying the three properties.

Alternative Solution: The first digit of the number $n$ should be $1$ and its last digit should be $0$. There are $2019$ locations between the first and the last digit and $1$, $3$, $5$, $7$, $\ldots$, or $2019$ of them may be filled with $1$'s. The number of possibilities is $$\binom{2019}{1} + \binom{2019}{3} + \cdots + \binom{2019}{2019} = 2^{2018}.$$ The last equality follows by subtracting the following identities: $$2^{2019} = (1+1)^{2019} = \binom{2019}{0} + \binom{2019}{1} + \cdots + \binom{2019}{2018} + \binom{2019}{2019}$$ and $$0 = (1-1)^{2019} = \binom{2019}{0} - \binom{2019}{1} + \cdots + \binom{2019}{2018} - \binom{2019}{2019}.$$ The answer is (C).