A field is made of $2017 \times 2017$ unit squares. Luffy has $k$ gold detectors, which he places on some of the unit squares, then he leaves the area. Sanji then chooses a $1500 \times 1500$ area, then buries a gold coin on each unit square in this area and none other. When Luffy returns, a gold detector beeps if and only if there is a gold coin buried underneath the unit square it's on. It turns out that by an appropriate placement, Luffy will always be able to determine the $1500 \times 1500$ area containing the gold coins by observing the detectors, no matter how Sanji places the gold coins. Determine the minimum value of $k$ in which this is possible.
Problem
Source: 2017 Indonesia MO, Problem 8
Tags: combinatorics
07.07.2017 12:31
Since it is a 1500 by 1500 area, it is only the position of two sides which must be determined. 1034? 517 squares in order to determine the position of each side
07.07.2017 17:44
I agree that the answer is $\boxed{1034}$. WLOG represent the coordinates of the squares with the elements of the set $\{1,2,\dots,2017\}^{\times 2}$ in the natural, grid-like way. For the construction, take the points $\{(1,518),(2,518),\dots,(517,518)\}$ and $\{(518,1),(518,2),\dots,(518,517)\}$. It is easy to see why this works. Now, note that if there are $1008$ consecutive squares sharing a row or column that do not contain a gold detector, and there exist $1008$ consecutive squares "parallel" and shifted by $1500$ vertically or horizontally respectively, then the latter set of squares must contain a gold detector. (This is much easier to phrase visually.) Now partition the field into $9$ rectangles given by the sets of coordinates $A_{i,j}=S_{i}\times S_{j}$ where $1\leq i,j\leq 3$, and $S_1=\{1,2,\dots,517\}$, $S_2=\{518,519,\dots,1500\}$, $S_3=\{1501,1502,\dots,2017\}$. Let $K(A_{i,j})$ give the number of gold detectors in the input rectangle, and consider some optimal placement of said detectors. From the observation it follows that $$K(A_{i,j})+K(A_{i,j+1})+K(A_{i+2,j})+K(A_{i+2,j+1})\geq 517$$and similarly $$K(A_{i,j})+K(A_{i+1,j})+K(A_{i,j+2})+K(A_{i+1,j+2})\geq 517$$Adding up all the inequalities produced gives $2(-K(A_{2,2})+\sum_{1\leq i,j\leq 3}K(A_{i,j}))\geq 4\cdot 517$, and thus $\sum_{1\leq i,j\leq 3}K(A_{i,j})\geq 1034$, which is the desired inequality $\blacksquare$