Problem 24 · 1998 AJHSME
Stretch
Number Theory
triangular-numbersmod-arithmetic
A board of 8 columns has squares numbered left to right, top to bottom (row one is 1–8, row two is 9–16, and so on). A student shades square 1, then skips one and shades square 3, skips two and shades square 6, skips three and shades square 10, and continues this way until every column has at least one shaded square. What is the number of the shaded square that first achieves this?
Show answer
Answer: E — 120.
Show hints
Hint 1 of 2
Two patterns hide here. First, the shaded square numbers 1, 3, 6, 10, 15, … are the triangular numbers (add 2, then 3, then 4, …). Second, with 8 columns, a square's column is decided by its leftover when divided by 8 — so you're really asking 'when have all 8 leftovers shown up?'
Still stuck? Show hint 2 →
Hint 2 of 2
List the triangular numbers' leftovers mod 8 in order. Seven of the eight leftovers appear fast; the holdout is leftover 0 (a multiple of 8). Find the first triangular number that's a multiple of 8.
Show solution
Approach: triangular numbers, sorted by their leftover mod 8; wait for the missing column
- The shaded squares jump 1, 3, 6, 10, 15, 21, … — the triangular numbers. Since the board is 8 wide, a square lands in column (its value's leftover after dividing by 8); column 8 means a leftover of 0, i.e. a multiple of 8.
- Track the leftovers as they arrive: 1→col1, 3→col3, 6→col6, 10→col2, 15→col7, 21→col5, 28→col4. After just seven shaded squares, columns 1,2,3,4,5,6,7 are all hit — only column 8 (leftover 0) is still empty.
- So we need the first triangular number divisible by 8. Checking on: 36, 45, 55, 66, 78, 91, 105 — none are multiples of 8 — until 120 = 8 × 15. The final column fills at square 120.
- Why this transfers: when items wrap across a fixed number of columns, the column is just the value's remainder, and 'until every column is hit' becomes 'until every remainder appears.' Watching the remainders (not the raw numbers) keeps the search short. (Bonus: 120 is the biggest answer choice, so once it's forced, it must be the answer.)
Mark:
· log in to save