cs-057 — The Locker Problem
| Field | Value |
|---|---|
| id | cs-057 |
| difficulty | Beginner |
| topics | counting, patterns |
| lecture | lecture-15 |
| estimated time | 5-minute attempt + 10-minute discussion |
| prerequisites | none |
| objective | state inputs, outputs, and assumptions, then solve a small instance by hand |
| solution | held by the instructor; discussed after the attempt |
Problem
100 lockers, 100 students, student i toggles every i-th locker. Which remain open? Counting by reasoning, then verify with a tiny simulation.
Your deliverable is the count (or probability) with the sample space stated, the case analysis, and a brute-force check for a small instance. 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: 100 lockers, 100 students; student i toggles lockers divisible by i
- Output: open lockers are perfect squares: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100
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
- Locker n is toggled once per divisor of n; divisors pair up (d, n/d) - except squares, where d = n/d.
- 'How many total, how many favourable' is the whole skeleton of probability.
- Complements turn hairy unions into one subtraction.
Discussion starter
After the solution is revealed, the class spends five minutes on this prompt: "When is enumeration a legitimate answer rather than a crutch?"
Constraints and assumptions
- Difficulty: Beginner (no prior experience assumed).
- Topics: counting, patterns.
- Classroom-scale inputs unless the problem says otherwise.
- Time-box: about five minutes for a first attempt; partial answers with clear reasoning are worth more than silent struggling.
- 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: Re-derive the count with a different method and reconcile the answers.