Problem 28 · 2019 Math Kangaroo
Stretch
Logic & Word Problems
careful-countingspatial-reasoning
A graph consists of 16 points and several connecting lines, as shown in the diagram. An ant is at point A. With every move the ant can move from the point where it currently is, along one of the connecting lines, to an adjacent point. At which of the points P, Q, R, S and T can the ant be after 2019 moves?
Show answer
Answer: B — only at P, R, S or T, not at Q
Show hints
Hint 1 of 3
Two-colour the 16 points so every line joins different colours.
Still stuck? Show hint 2 →
Hint 2 of 3
After an odd number of moves the ant must sit on the colour opposite to A's.
Still stuck? Show hint 3 →
Hint 3 of 3
2019 is odd, so the ant ends on the opposite colour class from its start.
Show solution
Approach: bipartite two-colouring and parity
- The graph is bipartite: colour the points so each edge joins the two colours.
- A starts on one colour; after 2019 (odd) moves it must be on the other colour.
- Of P, Q, R, S, T only Q shares A's colour, so the ant can be at P, R, S or T but not at Q.
Mark:
· log in to save