MathDB

Let

C

be the set of points

(x,y)

with integer coordinates in the plane where

1\leq x\leq 900

and

1\leq y\leq 1000

. A polygon

P

with vertices in

C

is called emerald if

P

has exactly zero or two vertices in each row and each column and all the internal angles of

P

are

90^\circ

270^\circ

. Find the greatest value of

k

such that we can color

k

points in

C

such that any subset of these

k

points is not the set of vertices of an emerald polygon.
https://cdn.discordapp.com/attachments/954427908359876608/1299737432010395678/image.png?ex=671e4a4f&is=671cf8cf&hm=ce008541975226a0e9ea53a93592a7469d8569baca945c1c207d4a722126bb60&
On the left, an example of an emerald polygon; on the right, an example of a non-emerald polygon.

Problem Statement