Problem

Source: India EGMO TST 2023/3

Tags: combinatorics



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