cs-116 — The Buffon Needle
| Field | Value |
|---|---|
| id | cs-116 |
| difficulty | Expert |
| topics | simulation, estimation |
| lecture | lecture-29 |
| estimated time | 5-minute attempt + 10-minute discussion |
| prerequisites | the full Block I-III toolbox and proof-shaped reasoning |
| objective | make and justify design decisions where the method itself is the challenge |
| solution | held by the instructor; discussed after the attempt |
Problem
Estimate pi by dropping needles (or its discrete cousin, random points in a square). Simulation as an estimator; error shrinking like 1/sqrt(n).
Your deliverable is the simulation result with trials and spread, the one-trial story, and the comparison with exact reasoning. If the problem is ambiguous anywhere, state the assumption you are making and carry on — a stated assumption is part of a good answer.
Examples
- Input: unit square, random point (x, y); inside quarter circle if x^2+y^2 <= 1
- Output: pi ~ 4 x inside/total; 100k points -> ~3.14 ± 0.005; error ~ 1/sqrt(n)
Solve for the worked instance first. Then ask what would change if one number, name, or condition were replaced by something stranger.
What to notice
- Estimate = area ratio x 4. Run 1k, 10k, 100k, 1M - watch the error shrink by ~3x each time.
- A simulation is only as good as the story of one trial.
- Error shrinks like 1/sqrt(trials) — quadruple the work, halve the error.
Discussion starter
After the solution is revealed, the class spends five minutes on this prompt: "What hidden assumption did the generator make, and when would it fail?"
Constraints and assumptions
- Difficulty: Expert (independent design decisions and proof-shaped arguments assumed).
- Topics: simulation, estimation.
- Classroom-scale inputs unless the problem says otherwise.
- Time-box: about five minutes for the attack plan; the full argument may exceed the box - outline the proof strategy instead of grinding details.
- Optional stretch (not required): describe an alternative approach and say when it beats the obvious one.
Hints and extension
- First nudge: identify the pattern the worked instance uses before computing anything.
- If stuck after three minutes, write the input/output line you expect and trace the smallest example by hand.
- After the reveal, attempt the extension below before the next lecture.
- Extension challenge: Halve and double the trial count; report how the estimate wobbles.