Problem 23 · 2016 Math Kangaroo
Stretch
Logic & Word Problems
casework
We consider a 5×5 square that is split up into 25 fields. Initially all fields are white. In each move it is allowed to change the colour of two fields that are horizontally or vertically adjacent (i.e. white fields turn black and black ones turn white). What is the smallest number of moves needed to obtain the chessboard colouring shown in the diagram?
Show answer
Answer: B — 12
Show hints
Hint 1 of 3
Only the grey target cells must change colour (an odd number of times); count them.
Still stuck? Show hint 2 →
Hint 2 of 3
Each move flips exactly two cells, so think about how few moves can deliver an odd flip to every grey cell.
Still stuck? Show hint 3 →
Hint 3 of 3
Try pairing up grey cells, or grey cells with a shared white neighbour, to use each move well.
Show solution
Approach: count the cells to flip, then pair them
- In the target, 12 grey cells must each be flipped an odd number of times while the 13 white cells stay flipped an even number of times.
- Each move flips exactly two adjacent cells, so to give all 12 grey cells an odd flip you need at least 12 moves (no single move can settle two grey cells, since grey cells are never adjacent).
- Twelve moves are enough: for each grey cell, flip it together with one chosen white neighbour, arranging the choices so every white cell is touched an even number of times.
- So the smallest number of moves is 12.
Mark:
· log in to save