SAUDI ARABIAN IMO Booklet 2023

Question

On a line, 200 points are marked and numbered 1, 2, 3, , 200 from left to right. Various crickets jump around the line. Each starts at point 1, jumping on the marked points and ending up at point 200. In addition, each cricket jumps from a marked point to another marked point with a greater number. When all the crickets have finished jumping, it turns out that for every pair (i, j) with 1 i < j 200, there was a cricket that jumped directly from point i to point j, without visiting any of the points in between the two. Show that the number of crickets was at least 10000 and that there is a way that 10000 crickets could jump satisfying the conditions above.

Accepted Answer

For every pair (i, j) where 1 i 100 and 101 j 200 there is a cricket that jumped from i to j and no cricket can do two such jumps. Therefore there are at least 100^2 = 10000 crickets. Consider the following paths of crickets: 1. 1 200; 2. 1 a 200 where a 2, 3, , 199, 3. 1 k 201 - k 200, where k 2, 3, , 100, 4. 1 k a 201 - k 200, where k 2, 3, , 100 and k < a < 201 - k. Counting the different paths above from each type, there are 1 + 198 + 99 + _k=2^100 (200 - 2k) = 10000 such paths, and one can check that for every pair of marked points there is a cricket doing the jump between the points.