Problem 30 · 2011 Math Kangaroo
Stretch
Counting & Probability
caseworkcareful-counting
Determine all n (with \(1 \le n \le 8\)) for which one can mark several cells of a 5×5 table so that there are exactly n marked cells in every 3×3 sub-table.
Show answer
Answer: E — All numbers from 1 to 8 are possible.
Show hints
Hint 1 of 3
Sliding a 3×3 window one column right drops its left column and adds a new one, so equal counts force the dropped and added columns (over those three rows) to match.
Still stuck? Show hint 2 →
Hint 2 of 3
That balancing condition makes column-1 match column-4 and column-2 match column-5, suggesting a repeating pattern.
Still stuck? Show hint 3 →
Hint 3 of 3
Instead of asking which n are forbidden, just try to build one valid marking for each n from 1 to 8.
Show solution
Approach: build an explicit marking for every n from 1 to 8
- Because overlapping windows force the marking to repeat (column 4 like column 1, column 5 like column 2, and likewise for rows), a marking is fixed by a small repeating block.
- Choosing how many cells of that block are marked lets the common window-count be tuned up or down across the whole achievable range.
- Carrying this out gives an explicit valid pattern for each target, so n = 1, 2, 3, 4, 5, 6, 7 and 8 are all attainable.
- Hence every value from 1 to 8 works, choice (E).
Mark:
· log in to save