Let $N \geqslant 3$ be an integer. In the country of Sibyl, there are $N^2$ towns arranged as the vertices of an $N \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 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. Proposed by Sutanay Bhattacharya and Anant Mudgal
Problem
Source: India EGMO TST 2023/3
Tags: combinatorics
10.12.2022 19:36
The answer is $N$ if $N$ is odd and $N-1$ if $N$ is even. Clearly it suffices to show the bound for when $N$ is odd. Consider all roads connecting a town on the border to a town on the inner $(N-2) \times (N-2)$ grid. There are $4(N-2)$ such roads. Call these good. Some of these are vertical, and the rest horizontal. Call a drone path type $X$ if it covers all rows and type $Y$ if it covers all columns. (Note that there is only one possible path which is both type $X$ and $Y$, but it does not use any good roads. Note that a drone path either covers at most $2$ good roads, or covers $4$, which occurs only when it is type $X$ or $Y$. There are $2(N-2) \equiv 2 \pmod 4$ good roads which are vertical, so there must be some two leftover after all mutually disjoint type $Y$ paths are removed. Similarly, there must be two vertical roads leftover after the mutually disjoint type $X$ paths are removed. These $4$ roads will require at least $2$ paths to cover. Therefore, the total number of paths is at least $2 \cdot \frac{N-3}{2} + 2 = N-1$. But for equality to hold, all except two of the paths must be type $X$ or $Y$. But none of these cover any of the corner squares. And note that for two paths to cover the leftover $4$ roads, each of them can cover at most two corners, and hence must cover exactly two corners. But one of the paths must cover two horizontal corners, and one covers two vertical corners, so all corners cannot be covered through these paths. Therefore, at least $N$ drones are required when $N$ is odd. Constructions are not too hard so I'll skip them. $\blacksquare$
11.12.2022 11:00
Consider the leftmost $n-1$ vertical edges of the bottom row and topmost $n-1$ horizontal edges of the last column.Any drone removed,removes at most two edges ,so directly proves the bound for even.It also characterises the potential equality cases for odd $n$,as any two of the edges uniquely define a drone.Its not hard to see a contradiction here.