Problem

Source: 2017 Indonesia MO, Problem 8

Tags: combinatorics



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.