4. What is the maximum number of vertices of a regular 2016-gon that can be marked so that no four marked vertices are the vertices of any rectangle?
Answer: 1009.

Solution. Note that an inscribed quadrilateral is a rectangle if and only if its diagonals are diameters of the circumscribed circle. The 2016-gon has exactly 1008 pairs of diametrically opposite vertices. If no rectangle can be formed from the marked vertices, then only in one pair can both vertices be marked. Therefore, no more than \(1007 + 2 = 1009\) vertices can be marked.

On the other hand, number the vertices of the 2016-gon in order from 1 to 2016 and mark the first 1009 vertices. Only the vertices numbered 1 and 1009 will be diametrically opposite. Therefore, 1009 satisfies the condition of the problem.