Total Score of a Random Partitioning Game
You start with a single set containing $n$ items. At each step, you pick one of the current sets (of size $k \geq 2$) and randomly split it into two non-empty subsets of sizes $k_1$ and $k_2$ (where $k_1 + k_2 = k$). You score $k_1 \times k_2$ points for that split.
You keep going until every set is a singleton. What is the total score at the end of the game?
Hints
- Think about what the score $k_1 \times k_2$ is counting in terms of pairs of items.
- Define an indicator variable for each pair $(i,j)$ that tracks when that pair gets separated. What is the sum of all these indicators?
- Every pair starts together and ends apart, so each pair is separated exactly once -- contributing exactly 1 to the total score.
Worked Solution
How to Think About It: The scoring rule $k_1 \times k_2$ looks arbitrary at first, but it is actually counting something natural. When you split a set of size $k$ into pieces of size $k_1$ and $k_2$, how many pairs of items just got separated? Exactly $k_1 \times k_2$ -- one item from each side. That realization turns a complicated random process into a simple bookkeeping exercise. Every pair of items starts together and ends apart, and each pair gets separated exactly once. So the total score is just the total number of pairs.
Quick Estimate: For $n = 4$, there are $\binom{4}{2} = 6$ pairs. Try a specific partition sequence: split $\{1,2,3,4\}$ into $\{1,2\}$ and $\{3,4\}$ -- that scores $2 \times 2 = 4$. Then split $\{1,2\}$ into singletons -- scores $1 \times 1 = 1$. Then split $\{3,4\}$ -- scores $1 \times 1 = 1$. Total: $4 + 1 + 1 = 6$. Now try a different sequence: split $\{1,2,3,4\}$ into $\{1\}$ and $\{2,3,4\}$ -- scores $1 \times 3 = 3$. Then split $\{2,3,4\}$ into $\{2\}$ and $\{3,4\}$ -- scores $1 \times 2 = 2$. Then split $\{3,4\}$ -- scores $1$. Total: $3 + 2 + 1 = 6$. Same answer both times. For general $n$, we expect $\binom{n}{2}$.
Approach: Use an indicator variable argument -- track each pair of items separately and show each pair contributes exactly 1 to the total score.
Formal Solution:
For each pair $(i, j)$ with $i < j$, define the indicator:
$$X_{ij} = \begin{cases} 1 & \text{at the step when } i \text{ and } j \text{ are first placed in different subsets} \\ 0 & \text{otherwise} \end{cases}$$
The key observation is that the score $k_1 \times k_2$ from splitting a set of size $k$ into pieces of size $k_1$ and $k_2$ equals exactly the number of pairs $(i,j)$ that are separated by that split. So the total score across all steps is:
$$\text{Total} = \sum_{\text{all steps}} k_1 k_2 = \sum_{i < j} X_{ij}$$
Now, every pair of items starts in the same set (the original set of $n$ items) and ends in different sets (singletons). At some step along the way, each pair must be separated for the first time. This happens exactly once per pair. Therefore $X_{ij} = 1$ for every pair $(i,j)$, and:
$$\text{Total} = \sum_{i < j} 1 = \binom{n}{2} = \frac{n(n-1)}{2}$$
This holds for every possible sequence of partitions -- the randomness does not matter.
Answer: The total score is always $\binom{n}{2} = \dfrac{n(n-1)}{2}$, regardless of how the partitions are chosen. The result is deterministic because each of the $\binom{n}{2}$ pairs contributes exactly 1 point at the moment it is separated.
Intuition
The trick is recognizing that a product $k_1 \times k_2$ is just the number of cross-pairs between the two sides of a partition. Once you see that, the whole problem collapses: you are summing up pair separations across all steps, and every pair gets separated exactly once. The total is just the number of pairs, $\binom{n}{2}$, no matter what random choices you make. This is a beautiful example of an invariant -- a quantity that looks like it depends on the process but actually does not.
This indicator variable technique is one of the most powerful tools in combinatorics and probability interviews. Whenever you see a score or cost that depends on some complicated random process, ask yourself: can I decompose it into contributions from individual elements or pairs? If each contribution is deterministic (or has a simple expectation), the whole sum becomes easy to analyze. The same idea shows up in sorting (counting inversions), random graphs (counting edges), and even in finance when you decompose portfolio variance into pairwise covariance contributions.