Ant Amelia starts on the number line at and crawls in the following manner. For Amelia chooses a time duration and an increment independently and uniformly at random from the interval During the th step of the process, Amelia moves units in the positive direction, using up minutes. If the total elapsed time has exceeded minute during the th step, she stops at the end of that step; otherwise, she continues with the next step, taking at most steps in all. What is the probability that Amelia’s position when she stops will be greater than ?
- A)
- B)
- C)
- D)
- E)
Answer
C
Key insight
The times only decide whether she takes 2 or 3 steps, each with chance 1/2. Then find the chance that the step lengths add to more than 1.
Solution
The times and the step lengths are chosen separately, so split the problem: first find how many steps she takes, then where she ends up.
1. She never stops after one step. Each is less than , so after one step less than minute has passed.
2. Two steps or three? She stops after step 2 exactly when . Picture as a random point in a -by- square. The line cuts the square into two equal triangles, so the chance is . Otherwise (chance ) she takes step 3, and then she always stops, since at most steps are allowed.
3. After two steps. Her position is . By the same square picture, the chance that is .
4. After three steps. Her position is , a random point in a -by--by- cube. The points where the sum is at most form a corner pyramid with corners , , , . Its volume is . So the chance that the sum is more than is .
5. Combine. Because the lengths do not depend on the times,
The answer is .
Why this works
The story looks tangled, but the times only decide how many step lengths get added, and the lengths are chosen independently of the times. So the problem splits into a "how many steps" chance and two standard picture problems: half of a square, and a cube with its corner pyramid removed. When random choices are independent, sort out the simpler one first and treat each outcome as its own case.
The trap
Thinking the step during which time runs out is cut short (it is finished in full), or linking the step lengths to the times.
Concise solution
First determine how many steps she takes. Since , she never stops after one step. She stops after the second step exactly when ; in the unit square of this is the half above the line , probability . Otherwise she takes the third step (and then stops regardless), also with probability .
The increments are independent of the times, so condition on the number of steps.
- Two steps: her position is , and by the same half-square argument.
- Three steps: her position is . The complement is the tetrahedron cut from the unit cube by the plane , of volume . So .
Combine:
The answer is .
Review in the AoPS books
- Introduction to Counting & Probability, Chapter 10: Geometric Probability
- Introduction to Counting & Probability, Chapter 8: Basic Probability Techniques (§8.5)
- Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.2)
- Intermediate Counting & Probability, Chapter 11: Conditional Probability
Techniques
Split into exhaustive cases and handle each · Count the complement and subtract from the total