Library / /21 of 30

, 2023

Combinatorics Difficulty 8.4 Shortlist Prove it Saudi Arabia

On a line, 200 points are marked and numbered $1, 2, 3, \ldots, 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 \le i < j \le 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.

Solution

For every pair $(i, j)$ where $1 \le i \le 100$ and $101 \le j \le 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 \to 200$ ;
2. $1 \to a \to 200$ where $a \in \{2, 3, \dots, 199\}$ ,
3. $1 \to k \to 201 - k \to 200$ , where $k \in \{2, 3, \dots, 100\}$ ,
4. $1 \to k \to a \to 201 - k \to 200$ , where $k \in \{2, 3, \dots, 100\}$ and $k < a < 201 - k$ .

Counting the different paths above from each type, there are
$1 + 198 + 99 + \sum_{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. $\square$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.