Let be an integer. In the country of Sibyl, there are towns arranged as the vertices of an 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 if is odd, and if is even.
We say a drone covers a vertex if it takes a turn at that vertex.
Construction: Let denote the vertical lines and denote the horizontal lines of the grid.
For , make one drone go along the outer boundary of the grid, and let of the drones traverse the rectangles enclosed by for all , and let of the drones traverse the rectangles enclosed by for all . These drones cover all roads in Sibyl.
For , again make one drone go across the boundary, and let of the drones traverse the rectangles enclosed by for all , and let of the drones traverse the rectangles enclosed by for all . One notes that these drones cover all roads in Sibyl.
Estimate: Suppose drones suffice. We will first show for all that . Fix the top-left corner of the grid and call any drone that passes through this town to be cornered. Suppose is the set of drones that are cornered. Let denote the set of drones (not in ) that cross a street in respectively. Note that any drone that covers some vertex in is either in or and any drone in covers two vertices in and any drone in covers one vertex in other than . Since each of the vertices on the top edge needs to be covered, . Similarly, . Adding, we get , hence , proving the claim.
Now suppose is odd. If possible, suppose . Following the notation in the last part, we see that equality must hold: and . 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 (a vertical dominator) or both (a horizontal dominator). Since every drone passes through either or , 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 and one of 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 , they both cover the top-right corner, contradiction. Similarly, there can be at most one vertical dominator through . But is at least one (some drone needs to cover ), and leads to a contradiction modulo in , so is exactly , and there is a horizontal and a vertical dominator through .
By a similar reasoning, there is a vertical and a horizontal dominator through the bottom-right corner, . But the horizontal dominator through and the vertical dominator through 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 .