Maths Olympiad Prep

Library / /2 of 2

Combinatorics Difficulty 9.1 IMO level Prove it India

Let N3N \ge 3 be an integer. In the country of Sibyl, there are N2N^2 towns arranged as the vertices of an N×NN \times N grid, with each pair of towns corresponding to an adjacent pair of vertices on the grid connected by a road. Several automated drones are each given the instruction to traverse a rectangular path starting and ending at the same town, following the roads of the country. It turned out that each road was traversed at least once by some drone. Determine the minimum number of drones that must be operating.

Solution

Answer: The desired minimum is NN if NN is odd, and (N1)(N-1) if NN is even.
We say a drone covers a vertex if it takes a 9090^\circ turn at that vertex.

Construction: Let v1,,vNv_1, \dots, v_N denote the NN vertical lines and h1,,hNh_1, \dots, h_N denote the NN horizontal lines of the grid.
For N=2nN = 2n, make one drone go along the outer boundary of the grid, and let (n1)(n-1) of the drones traverse the rectangles enclosed by v2i,v2i+1,h1,hNv_{2i}, v_{2i+1}, h_1, h_N for all 1in11 \le i \le n-1, and let (n1)(n-1) of the drones traverse the rectangles enclosed by h2i,h2i+1,v1,vNh_{2i}, h_{2i+1}, v_1, v_N for all 1in11 \le i \le n-1. These N1N-1 drones cover all roads in Sibyl.
For N=2n+1N = 2n + 1, again make one drone go across the boundary, and let nn of the drones traverse the rectangles enclosed by v2i,v2i+1,h1,hNv_{2i}, v_{2i+1}, h_1, h_N for all 1in1 \le i \le n, and let nn of the drones traverse the rectangles enclosed by h2i,h2i+1,v1,vNh_{2i}, h_{2i+1}, v_1, v_N for all 1in1 \le i \le n. One notes that these NN drones cover all roads in Sibyl.

Estimate: Suppose kk drones suffice. We will first show for all NN that kN1k \ge N-1. Fix the top-left corner AA of the grid and call any drone that passes through this town to be cornered. Suppose CC is the set of drones that are cornered. Let Lh,Lv\mathcal{L}_h, \mathcal{L}_v denote the set of drones (not in CC) that cross a street in h1,v1h_1, v_1 respectively. Note that any drone that covers some vertex in h1h_1 is either in CC or Lh\mathcal{L}_h and any drone in Lh\mathcal{L}_h covers two vertices in h1h_1 and any drone in CC covers one vertex in h1h_1 other than AA. Since each of the NN vertices on the top edge needs to be covered, 1+C+2LhN1 + |C| + 2|\mathcal{L}_h| \ge N. Similarly, 1+C+2LvN1 + |C| + 2|\mathcal{L}_v| \ge N. Adding, we get 2+2C+2Lh+2Lv2N2 + 2|C| + 2|\mathcal{L}_h| + 2|\mathcal{L}_v| \ge 2N, hence kC+Lh+LvN1k \ge |C| + |\mathcal{L}_h| + |\mathcal{L}_v| \ge N-1, proving the claim.

Now suppose NN is odd. If possible, suppose k=N1k = N-1. Following the notation in the last part, we see that equality must hold: 1+C+2Lh=N1 + |C| + 2|\mathcal{L}_h| = N and 1+C+2Lv=N1 + |C| + 2|\mathcal{L}_v| = N. Further, every drone must be in one of these three sets, and no point on the top edge apart from the top-left corner can be covered by two drones (else the bounds would not be tight).

Call a drone a dominator if it passes through both h1,hNh_1, h_N (a vertical dominator) or both v1,vNv_1, v_N (a horizontal dominator). Since every drone passes through either h1h_1 or v1v_1, and this reasoning applies any other corner, this implies that every drone must be a dominator. Indeed, if some drone is not a dominator, one can pick one of h1,hNh_1, h_N and one of v1,vNv_1, v_N so that it doesn't pass through any of the picked lines; and applying the above reasoning to the corner at the intersection of these two leads to a contradiction.

Now if there are two horizontal dominators through AA, they both cover the top-right corner, contradiction. Similarly, there can be at most one vertical dominator through AA. But C|C| is at least one (some drone needs to cover AA), and C=1|C| = 1 leads to a contradiction modulo 22 in 1+C+2Lh=N1 + |C| + 2|\mathcal{L}_h| = N, so C|C| is exactly 22, and there is a horizontal and a vertical dominator through AA.

By a similar reasoning, there is a vertical and a horizontal dominator through the bottom-right corner, DD. But the horizontal dominator through AA and the vertical dominator through DD both cover the top-right corner point. We noted before that no point on the top edge apart from the top-left corner can be covered by two drones, so this is a contradiction, showing kNk \ge N. \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 reproduced verbatim; metadata (topic, difficulty) added by this project.