CombinatoricsDifficulty 5.2AIME, harderProve itUnited States
Problem:
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 81?
Solutions — 2
Solution 1
Solution:
There are 7! total ways to break the chalks. How many of these result in all having length 81? 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 (36)=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 7!20⋅22=631
Solution 2
Solution:
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 bn is the number of ways to expand a binary tree with n layers, we have b1=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 (2k−12k+1−2) ways. For each one of these trees, there are bk ways to decide these moves. So we have bk+1=(2k−12k+1−2)bk2. So b2=(12)⋅12=2, b3=(36)⋅22=20⋅22. Thus, the final answer is 7!20⋅22=631
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.