Maths Olympiad Prep

Track / Stage 5 / 398 of 400 #998 of 1964

Problem 998

AIME late
Combinatorics Difficulty 6.0 Prove it

13.75 On an infinitely large grid paper, each cell is colored either black or white (not necessarily following any specific pattern). A grasshopper jumps between black cells, and a worm jumps between white cells, each time jumping over any number of cells in a vertical or horizontal direction. Prove that they can become adjacent after at most 3 jumps in total.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

[Proof] Suppose the two are in different rows and columns; otherwise, one less jump is needed. Consider the intersection of the row where the flea is and the column where the grasshopper is. If it is a black square, let the grasshopper jump to this square; if it is a white square, let the flea jump to this square. Let's assume the former. At this point, the two insects are in the same column, with the grasshopper on a black square and the flea on a white square. If these two squares are not adjacent, there must be two adjacent squares between them, one of which is black and the other white. Thus, by letting the grasshopper and the flea each jump once, they can enter these two adjacent squares, with the grasshopper entering the black square and the flea entering the white square. Up to this point, the two have jumped at most 3 times.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.