From time to time, you stumble upon problems that are very simple yet not obvious, in a way that makes them quite intriguing. Today, I’ve found one such problem as a subproblem in a Codeforces round.
Suppose you have two sets $A$ and $B$. Let’s say they are two teams of people, where each team can have a different size. You want to set up a fair match, with any number of people provided that both sides have the same number of players. For example, you can pick 1 player from $A$ and 1 from $B$, or 2 from each side, but not 1 from $A$ and 2 from $B$. In how many ways can you set up the match?
The formalized problem sounds simple: you want to count ways of pairing up equal-sized subsets from $A$ and $B$. Of course, one way of calculating the solution would be to simply evaluate the sum:
$$f(A, B) = \sum_{i=0}^{\min(|A|, |B|)} \binom{|A|}{i} \times \binom{|B|}{i}$$
But that is a lot of computation to do, and suppose we need to do better than that. There is a very elegant solution, which is also faster. If you want to think about it for a bit, now is the time. Otherwise, keep reading.
We can solve the problem by computing only one combination. I’ll first give the formula, and then explain why it works. Let’s assume, without loss of generality, that $|A| \leq |B|$. Then,
$$f(A, B) = \binom{|A| + |B|}{|A|}$$
Why does that make sense? What we’re doing here is, from all elements of $A$ and $B$ combined, choosing which elements of $B$ we are going to use, and at the same time which elements of $A$ we going to leave out of our match. For example, say $A$ has 5 elements, and $B$ has 8. Let’s line them up:
$A_1\hspace{1em}A_2\hspace{1em}A_3\hspace{1em}A_4\hspace{1em}A_5\hspace{1em}B_1\hspace{1em}B_2\hspace{1em}B_3\hspace{1em}B_4\hspace{1em}B_5\hspace{1em}B_6\hspace{1em}B_7\hspace{1em}B_8$</
Now suppose we chose the following 5 elements in bold:
$A_1\hspace{1em}\textbf{A}_2\hspace{1em}\textbf{A}_3\hspace{1em}A_4\hspace{1em}\textbf{A}_5\hspace{1em}B_1\hspace{1em}B_2\hspace{1em}\textbf{B}_3\hspace{1em}B_4\hspace{1em}B_5\hspace{1em}B_6\hspace{1em}B_7\hspace{1em}\textbf{B}_8$
If we erase the bold from $A$ and keep only the bold $B$ elements, we get the following match:
$A_1\hspace{1em}A_4\hspace{1em}\texttt{vs}\hspace{1em}B_3\hspace{1em}B_8$
See? The elements chosen in $A$ were erased, and the elements chosen in $B$ were kept. This will always lead to a valid pair of subsets. To see why, suppose we pick $k$ elements from $A$: then we must have picked $|A| - k$ elements from $B$. That means we are going to keep $|A| - k$ elements from $A$ as well, after we erase $k$. Since $k \leq |A|$, and we assumed $|A| \leq |B|$, $0 \leq |A| - k \leq |B|$: both sides are valid. It’s also easy to see that, given a valid pair of subsets, there is only one way of choosing its elements with our procedure. Hence, this only combination gives us what we want.
$$\tag*{$\blacksquare$}$$