HMMT-Nov 2022 team, Problem 4

You start with a single piece of chalk of length 1. Every second, you choose a piece of chalk that you have uniformly at random and break it in half. You continue this until you have 8 pieces of chalk. What is the probability that they all have length $\frac{1}{8}$ ?

Solution: Solution 1: There are 7! total ways to break the chalks. How many of these result in all having length $\frac{1}{8}$ ? The first move gives you no choice. Then, among the remaining 6 moves, you must apply 3 breaks on the left side and 3 breaks on the right side, so there are $\left(\begin{array}{l}6 \\ 3\end{array}\right)=20$ ways to order those. On each side, you can either break the left side or the right side first. So the final answer is \[ \frac{20 \cdot 2^{2}}{7 !}=\frac{1}{63} \] Solution 2: We know there are 7! ways to break the chalk in total. Now, if we break up the chalk into 8 pieces, we can visualize the breaks as a binary decision tree. Each round we select a node and break that corresponding piece of chalk, expanding it into two branch nodes. The final tree of our desired configuration will have three layers. We can figure out how many different ordering we can do this in with recursion. If $b_{n}$ is the number of ways to expand a binary tree with $n$ layers, we have $b_{1}=1$. Now when we expand a node with $k+1$ layers, we will expand either the $k$-layered tree on the left or right, these moves can be ordered in $\left(\begin{array}{c}2^{k+1}-2 \\ 2^{k}-1\end{array}\right)$ ways. For each one of these trees, there are $b_{k}$ ways to decide these moves. So we have $b_{k+1}=\left(\begin{array}{c}2^{k+1}-2 \\ 2^{k}-1\end{array}\right) b_{k}^{2}$. So $b_{2}=\left(\begin{array}{l}2 \\ 1\end{array}\right) \cdot 1^{2}=2, b_{3}=\left(\begin{array}{l}6 \\ 3\end{array}\right) \cdot 2^{2}=20 \cdot 2^{2}$. Thus, the final answer is \[ \frac{20 \cdot 2^{2}}{7 !}=\frac{1}{63} \] $\fbox{\frac{1}{63}}$.

Answer: \frac{1}{63}