Problem 17 · 1991 AJHSME
Stretch
Counting & Probability
max-independentsum
An auditorium with 20 rows of seats has 10 seats in the first row. Each successive row has one more seat than the previous row. If students taking an exam are permitted to sit in any row, but not next to another student in that row, then the maximum number of students that can be seated for an exam is
Show answer
Answer: C — 200.
Show hints
Hint 1 of 3
First solve ONE row: in a row of n seats with no two students adjacent, the most you can fit is "fill every other seat" starting at an end. For a row of 10 that's 5; for a row of 11 that's 6. What's the rule for n?
Still stuck? Show hint 2 →
Hint 2 of 3
Per row the max is ⌈n/2⌉ (round n÷2 UP — an odd row gets the extra seat). Now you must add that over rows of 10, 11, …, 29 seats. Adding twenty numbers is slow; look for a pairing shortcut.
Still stuck? Show hint 3 →
Hint 3 of 3
Write the twenty per-row maxima in order: 5, 6, 6, 7, …, 14, 14, 15. Pair the smallest with the largest, second-smallest with second-largest. What does each pair add to?
Show solution
Approach: solve one row, then pair the row-totals from the ends
- One row first: with no two students side by side, fill every other seat starting at an end. A row of n seats holds ⌈n/2⌉ students (round up, so an odd row earns the extra seat).
- The rows have 10, 11, …, 29 seats, giving maxima 5, 6, 6, 7, 7, 8, …, 14, 14, 15.
- Pair from the ends: 5 + 15, 6 + 14, 6 + 14, … — each pair sums to 20. There are 20 rows = 10 pairs, so the total is 10 × 20 = 200.
- Why this transfers: "no two adjacent" always means "take every other one," capping a line of n at ⌈n/2⌉ — the same bound shows up in seating, tiling, and graph problems. And summing a tidy list is fastest by pairing ends (the Gauss trick).
Another way — average × count (Gauss):
- The twenty row-maxima run 5, 6, 6, …, 14, 14, 15 — they're balanced around a middle value of 10, so their average is 10.
- Total = average × count = 10 × 20 = 200, no listing required.
Mark:
· log in to save