HMMT February, 2018

Solution:

We will solve this problem for 36 replaced by $n$. We use $[n]$ to denote $\{1,2, \ldots, n\}$ and $\sigma_{s}$ to denote the last digit of the sum of the digits of $s$.
Let $D$ be the set of all sequences of $n$ digits and let $S_{i}$ be the set of digit sequences $s$ such that $s_{i}=\sigma_{s}$, the $i^{\text{th}}$ digit of $s$. The quantity we are asked to compute is equal to $\left|D \backslash \bigcup_{i=1}^{n} S_{i}\right|$. We use the principle of inclusion-exclusion to compute this:
$$\left|D \backslash \bigcup_{i=1}^{n} S_{i}\right|=\sum_{J \subseteq[n]}(-1)^{|J|}\left|\bigcap_{j \in J} S_{j}\right|$$
Note that a digit sequence is in $S_{i}$ if and only if the $n-1$ digits which are not $i$ sum to a multiple of 10. This gives that $\left|S_{i}\right|=10 \cdot 10^{n-2}=10^{n-1}$ as there are 10 ways to pick the $i^{\text{th}}$ digit and $10^{n-2}$ ways to pick the other digits.

Similarly, given a subset $J \subseteq[n]$, we can perform a similar analysis. If a string $s$ is in $\bigcap_{j \in J} S_{j}$, we must have that $s_{j}=\sigma_{s}$ for all $j \in J$. There are 10 ways to pick $\sigma_{s}$, which determines $s_{j}$ for all $j \in J$. From there, there are $10^{(n-|J|)-1}$ ways to pick the remaining digits as if we fix all but one, the last digit is uniquely determined. This gives $10^{n-|J|}$ choices.

However, this breaks down when $|J|=n$, as not all choices of $\sigma_{s}$ lead to any valid solutions. When $|J|=n$, $J=[n]$ and we require that the last digit of $n \sigma_{s}$ is $\sigma_{s}$, which happens for $\operatorname{gcd}(n-1,10)$ values of $\sigma_{s}$.

We now compare our expression from the principle of inclusion-exclusion to the binomial expansion of $(10-1)^{n}$. By the binomial theorem,
$$9^{n}=(10-1)^{n}=\sum_{J \subseteq[n]}(-1)^{|J|} 10^{n-|J|}$$
These agree on every term except for the term where $J=[n]$. In this case, we need to add an extra $(-1)^{n} \operatorname{gcd}(n-1,10)$ and subtract $(-1)^{n}$.

Thus our final value for $\left|D \backslash \bigcup_{i=1}^{n} S_{i}\right|$ is $9^{n}+(-1)^{n}(\operatorname{gcd}(n-1,10)-1)$, which is $9^{36}+4$ for $n=36$.