Problem

Source: China Northern MO 2010 p4 CNMO

Tags: combinatorics, combinatorial geometry



As shown in the figure, chess pieces are placed at the intersection points of the $64$ grid lines of the $7\times 7$ grid table. At most $1$ piece is placed at each point, and a total of $k$ left chess pieces are placed. No matter how they are placed, there will always be $4$ chess pieces, and the grid in which they are located the points form the four vertices of a rectangle (the sides of the rectangle are parallel to the grid lines). Try to find the minimum value of $k$.