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?
Show that the answer is the same no matter how the random partitions happen to fall.
Open the full interactive solver, hints, and worked solution →