Problem 29 · 2016 Math Kangaroo
Stretch
Counting & Probability
caseworkcareful-counting
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 three fields that are adjacent in a horizontal or vertical line (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: A — less than 10
Show hints
Hint 1 of 3
Each move flips exactly three in-line cells, so a cell ends black only if it is flipped an odd number of times.
Still stuck? Show hint 2 →
Hint 2 of 3
Try to cover several needed black cells with each single move instead of one at a time.
Still stuck? Show hint 3 →
Hint 3 of 3
Look for a clever overlap of horizontal and vertical triples that hits the target with very few moves.
Show solution
Approach: find an efficient flip sequence
- A move toggles three adjacent cells in a line, so the goal is to flip exactly the target-black cells an odd number of times and the rest an even number.
- Because moves overlap, a single well-placed triple can settle several target cells at once.
- A careful set of fewer than ten moves produces the whole chessboard pattern, so the answer is less than 10 (A).
Mark:
· log in to save