"Olympiad counting puzzle" without complex numbers
\[\gdef\Mod#1{\ (\text{mod}\ #1)}\]$\gdef\Mod#1{\ (\text{mod}\ #1)}$
The king of maths animation, 3blue1brown, recently dropped yet another absolute gem of a video. It's been a three-month drought, but oh did this one make the wait worth it.
One commenter said:
I literally cried seeing the solution finally works out. It is so satisfying.
Me too, bud. Me too.
The problem solved in the video is this:
Find the number of subsets of $\{1, ..., 2000\}$, the sum of whose elements is divisible by 5.
In his trademark way, 3b1b presented an amazing solution that twisted its way through generating functions and complex analysis. However, he alluded to alternate solutions involving linear algebra. One such solution will be the subject of this post. While this method is arguably less "beautiful", I think it is more straightfoward, simple and in keeping with the problem's discrete nature.
As 3b1b remarked, it helps to think small initially. As he notes in the video, there are 8 subsets of $S=\{1,2,3,4,5\}$ that have subset sums divisible by 5:
We'll discuss here an iterative solution where if we have the answer for some smaller set $S=\{1,...,n\}$, we can obtain the solution for $S=\{1,...,(n+5)\}$.
Firstly, given some $n$, define the vector $\bm{v}^{(n)}$ as a $1\times 5$ row vector where the $j$th term (counting from 0) is the number of subsets with sum $\;\equiv j\Mod{5}$. (From here we'll use the phrase "subset-sum-$j$" to unambiguously mean "subset-sum $\;\equiv j\Mod{5}$") In set notation:
\[v^{(n)}_j=\Big|\{ s\; |\; s\subseteq \{1,...,n\},\;\text{sum}(s)\equiv j\Mod{5} \}\Big|\]
For instance, in the above figure where $n=5$, the vector will be \[\bm{v}^{(5)}=\begin{bmatrix}8&6&6&6&6\end{bmatrix}\]
There exists a square matrix $\bm{A}$ such that $\bm{v}^{(n+5)}=\bm{v}^{(n)}\bm{A}$ for all $n$
Suppose we have $S=\{1,...,n\}$. The key thing to notice is that when we append the next 5 integers to $S$, we may as well be appending their residues mod 5. Specifically, this means that $\bm{v}^{(n+5)}$ is actually unchanged if instead of having \[S=\{1,...,n\}+\{(n+1),...,(n+5)\}\] we had \[S=\{1,...,n\}+\{0,1,2,3,4\}\] This is of course because the residues do not affect the subset sums mod 5. In fact, we may as well mod everything within a subset first, and then take the sum, e.g.: \[\text{sum}(\{4,6,10,17\})\equiv\text{sum}(\{4,1,0,2\})\Mod{5}\]
But I digress. For the "original" $S=\{1,...,n\}$, suppose we have determined $\bm{v}^{(n)}$ which we will explicitly write out as \[\bm{v}^{(n)}=\begin{bmatrix}v^{(n)}_0&v^{(n)}_1&v^{(n)}_2&v^{(n)}_3&v^{(n)}_4\end{bmatrix}\]
Now consider the "invading" set $\{0,1,2,3,4\}$. We can also form 5 groups out of this invading set's subsets, with each group corresponding to a different subset-sum-mod-5. In fact, this is just the $\bm{v}^{(5)}$ we've seen earlier
\[\begin{bmatrix}8&6&6&6&6\end{bmatrix}\]
Now to determine $\bm{v}^{(n+5)}$. Specifically we start with its first component $v^{(n+5)}_0$, which is the number of subsets of $S=\{1,...,n\}+\{0,1,2,3,4\}$ with subset-sum-0. These are the contributions to $v^{(n+5)}_0$:
- For each of the $v^{(n)}_1$ original subsets with subset-sum-0, append any one of the (eight) invading subsets with subset-sum-0. (Note that the empty set $\emptyset$ is one of these eight invading subsets, so appending $\emptyset$ is basically just leaving the original subset untouched.)
- For each of the $v^{(n)}_1$ original subsets with subset-sum-1, append any one of the (six) invading subsets with subset-sum-4.
- For each of the $v^{(n)}_1$ original subsets with subset-sum-2, append any one of the (six) invading subsets with subset-sum-3.
- For each of the $v^{(n)}_1$ original subsets with subset-sum-3, append any one of the (six) invading subsets with subset-sum-2.
- For each of the $v^{(n)}_1$ original subsets with subset-sum-4, append any one of the (six) invading subsets with subset-sum-1.
And so the first equation is \[v^{(n+5)}_0 = 8v^{(n)}_0 + 6v^{(n)}_1 + 6v^{(n)}_2 + 6v^{(n)}_3 + 6v^{(n)}_4\]
Doing the same for $v^{(n+5)}_1$, $v^{(n+5)}_2$, $v^{(n+5)}_3$, $v^{(n+5)}_4$, everything can be packaged as:
\[\underbrace{\begin{bmatrix}v^{(n+5)}_0&v^{(n+5)}_1&v^{(n+5)}_2&v^{(n+5)}_3&v^{(n+5)}_4\end{bmatrix}}_{\bm{v}^{(n+5)}} = \underbrace{\begin{bmatrix}v^{(n)}_0&v^{(n)}_1&v^{(n)}_2&v^{(n)}_3&v^{(n)}_4\end{bmatrix}}_{\bm{v}^{(n)}}\underbrace{\begin{bmatrix}8&6&6&6&6\\6&8&6&6&6\\6&6&8&6&6\\6&6&6&8&6\\6&6&6&6&8\\\end{bmatrix}}_A\]
The latter square matrix is exactly the $\bm{A}$ we needed to find.
Completing the solution
Clearly the way to solve the entire problem is to obtain $\bm{v}^{(2000)}$ and take the first component $v^{(2000)}_0$ as our answer.
\[\begin{align*}\bm{v}^{(2000)} &= \bm{v}^{(0)}\bm{A}^{400}\\&=\bm{v}^{(0)}\bm{P}\bm{D}^{400}\bm{P}^{-1}\end{align*}\]
where we diagonalised $\bm{A}=\bm{P}\bm{D}\bm{P}^{-1}$ where $\bm{D}$ is a diagonal matrix. This is in principle calculable by hand using Gaussian elimination (which probably won't actually be too rough), but I'm going to cheat and use a calculator that tells me
\[\begin{align*}\bm{P} &=\begin{bmatrix}-1&-1&-1&-1&1\\0&0&0&1&1\\0&0&1&0&1\\0&1&0&0&1\\1&0&0&0&1\end{bmatrix}\\\bm{D} &=\begin{bmatrix}2&0&0&0&0\\0&2&0&0&0\\0&0&2&0&0\\0&0&0&2&0\\0&0&0&0&32\end{bmatrix}\\\bm{P}^{-1} &=\frac{1}{5}\begin{bmatrix}-1&-1&-1&-1&4\\-1&-1&-1&4&-1\\-1&-1&4&-1&-1\\-1&4&-1&-1&-1\\1&1&1&1&1\end{bmatrix}\end{align*}\]
Along with the fact that for $n=0$, the only subset is $\emptyset$ and thus
\[\bm{v}^{(0)}=\begin{bmatrix}1&0&0&0&0\end{bmatrix}\]
we are finally ready to crunch the numbers, which gives
\[\begin{align*}\bm{v}^{(2000)} &=\bm{v}^{(0)}\bm{P}\bm{D}^{400}\bm{P}^{-1}\\&=\begin{bmatrix}\frac{1}{5}(4\cdot 2^{400}+2^{2000})&? &? &? &?\end{bmatrix}\end{align*}\]
where we haven't bothered to calculate the last four components, as only the first is important. This is exactly the answer we want: in a set $\{1,...,2000\}$, there are exactly \[\boxed{\frac{1}{5}(4\cdot 2^{400}+2^{2000})}\] subsets with subset-sum divisible by 5.