Problem 19 · 1990 AJHSME
Hard
Logic & Word Problems
optimizationspacingcovering
There are 120 seats in a row. What is the fewest number of seats that must be occupied so the next person to be seated must sit next to someone?
Show answer
Answer: B — 40.
Show hints
Hint 1 of 2
Flip the goal around: 'the next person must sit next to someone' just means there's NO empty seat with both neighbors also empty. So you need every gap of empties to be small — what's the most empty seats you can leave in a row before a safe spot opens up?
Still stuck? Show hint 2 →
Hint 2 of 2
Think of each person as 'guarding' a block: themselves plus the seat on each side. To cover 120 seats with the fewest guards, give each person a full block of 3 and tile the row as (empty, person, empty) repeating.
Show solution
Approach: each person covers a block of 3 (the seated-spacing / covering idea)
- Reframe: a newcomer is forced next to someone exactly when no seat is left with *both* neighbors empty. So we must break up the empties so that no two empty seats sit side by side… actually, more precisely, each occupied person can 'block' at most the seat on each side of them.
- Picture repeating the pattern empty–person–empty, i.e. blocks of 3. One person per block of 3 means every empty seat is right next to an occupied one. That uses 120 ÷ 3 = 40 people, and it works.
- Could 39 do it? 39 people can guard at most 39×3 = 117 seats, leaving a gap — somewhere two empties sit together and a newcomer could avoid everyone. So 40 is both enough and necessary: 40.
- *Why this transfers:* 'fewest needed so every spot is covered' problems divide the total by how much one item covers (here 3) — and you confirm the floor by checking one fewer leaves a hole.
Mark:
· log in to save