Maths Olympiad Prep

Library / /571 of 740

, 2022

Combinatorics Difficulty 5.2 AIME, harder Prove it United States

Problem:

You start with a single piece of chalk of length 11. 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 88 pieces of chalk. What is the probability that they all have length 18\frac{1}{8}?

Solutions — 2

Solution 1

Solution:

There are 7!7! total ways to break the chalks. How many of these result in all having length 18\frac{1}{8}? The first move gives you no choice. Then, among the remaining 66 moves, you must apply 33 breaks on the left side and 33 breaks on the right side, so there are (63)=20\binom{6}{3} = 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
20227!=163 \frac{20 \cdot 2^{2}}{7!} = \frac{1}{63}

Solution 2

Solution:

We know there are 7!7! ways to break the chalk in total.
Now, if we break up the chalk into 88 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 bnb_{n} is the number of ways to expand a binary tree with nn layers, we have b1=1b_{1}=1. Now when we expand a node with k+1k+1 layers, we will expand either the kk-layered tree on the left or right, these moves can be ordered in (2k+122k1)\binom{2^{k+1}-2}{2^{k}-1} ways. For each one of these trees, there are bkb_{k} ways to decide these moves. So we have bk+1=(2k+122k1)bk2b_{k+1}=\binom{2^{k+1}-2}{2^{k}-1} b_{k}^{2}. So b2=(21)12=2b_{2}=\binom{2}{1} \cdot 1^{2}=2, b3=(63)22=2022b_{3}=\binom{6}{3} \cdot 2^{2}=20 \cdot 2^{2}. Thus, the final answer is
20227!=163 \frac{20 \cdot 2^{2}}{7!}=\frac{1}{63}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.