Problem 15 · 2024 Math Kangaroo
Hard
Counting & Probability
grid-countingcareful-counting
The following shape is composed of identical squares. What is the maximum number of 2×1 dominoes that can be placed on the shape if each covers exactly two squares? The dominoes can be placed horizontally or vertically and are not allowed to cover each other.
Show answer
Answer: C — 10
Show hints
Hint 1 of 3
Colour the squares like a checkerboard, since every domino must cover one square of each colour.
Still stuck? Show hint 2 →
Hint 2 of 3
The number of dominoes can never exceed the count of the rarer colour, so compare the two colour totals.
Still stuck? Show hint 3 →
Hint 3 of 3
Count black and white squares; the smaller total is the ceiling, then check it is actually reachable.
Show solution
Approach: checkerboard bound that turns out to be tight
- The pyramid has rows of \(9,7,5,3\) squares, \(24\) in all, so a naive ceiling is \(12\) dominoes.
- Colour it like a checkerboard: every \(2\times1\) domino covers exactly one black and one white square.
- Counting gives \(14\) of one colour and \(10\) of the other, so no more than \(10\) dominoes can ever be placed.
- Ten dominoes can indeed be laid without overlap, so the maximum is 10 (answer C).
Mark:
· log in to save