Problem 27 · 2022 Math Kangaroo
Stretch
Spatial & Visual Reasoning
gridtiling-tessellation
What is the smallest number of cells of a \(5 \times 5\) grid that must be coloured so that every \(1 \times 4\) rectangle and every \(4 \times 1\) rectangle in the grid contains at least one coloured cell?
Show answer
Answer: B — 6
Show hints
Hint 1 of 2
Every horizontal and every vertical run of 4 cells must contain a coloured cell; first find a lower bound, then build an example reaching it.
Still stuck? Show hint 2 →
Hint 2 of 2
A single cell in the middle three columns covers both horizontal 4-strips of its row, and similarly for columns; balance these two demands.
Show solution
Approach: cover all 1x4 and 4x1 strips with a small lower bound and a matching example
- Consider the four disjoint 1x4 strips in the corners (rows 1 and 5, cols 1-4 and 2-5 style); they force several coloured cells, giving a lower bound of 6.
- Six cells placed in two short diagonals (for example (1,2),(2,3),(3,4) and (3,2),(4,3),(5,4)) hit every horizontal and every vertical 4-in-a-row.
- Since 6 cells suffice and fewer cannot, the minimum is 6, so the answer is B.
Mark:
· log in to save