Chess board problem

I constructed the solution shown by employing the notion of greedily packing diagonals of selected points (blue) as densely as possible while avoiding having 4 selected points as vertices of any rectangle with sides parallel to the grid boundary. The most points that could be selected this way was $\boxed{24}$ .

To verify that this was in fact the maximum possible selected points, I formulated and solved the following integer linear program (ILP), which is a mathematical formulation of the posed problem. Let $\begin{aligned} x_{i,j} &\equiv 1, \text{ if point } (i,j) \text{ is selected (blue), and } 0 \text{ otherwise,} \\ \end{aligned}$

where $i \in {1, ..., R}$ is the row index and $j \in {1, ..., C}$ is the column index of points in a rectangular grid with $R$ rows and $C$ columns.

Then a mathematical programming formulation of this point selection problem is:

$\begin{aligned} &\max \; \sum_{i=1}^R \sum_{j=1}^C x_{i,j}\\ \text{subject to:}&\\ &x_{i,j} + x_{i,n} + x_{m,n} + x_{m,j} \le 3 , \quad \forall i \in \{1, ..., R-1\}, j \in \{1, ..., C-1\}, m \in \{i+1, ..., R\}, n \in \{j+1, ..., C\} \\ &x_{i,j} \in \{0,1\} , \qquad \qquad \qquad \qquad \forall i \in \{1, ..., R\}, j \in \{1, ..., C\} .\\ \end{aligned}$

In this ILP formulation, the objective counts the total number of points selected, which is to be maximized. The constraint set allows at most 3 selected points as vertices of any size rectangle with lower left corner at $(i,j)$ and upper right corner at $(m,n)$ and with sides parallel to the grid boundary . The binary variables $\{x_{i,j}\}$ require a point to be either selected or not. In addition to verifying that the maximum number of selected points is 24 for an 8 x 8 grid, this ILP also shows there are many alternative solutions, such as this $\boldsymbol{\rightarrow}$ :

Note: This solution is an update to that originally posted in order to align with the updated problem wording.

We divide the grid into 8 rows. Notice that all of the rows are identical.

We see that we cannot select the same pair of points in any 2 rows, since if we assemble the grid, then among those two rows, the two selected pairs will form a rectangle. Hence each pair of points can be used at most once in all rows.

We see that there are a maximum of 8C2 = 28 pairs of points among all the rows. This means that if we select 3 points in each row, there are a total of 3 pairs of points in each row and a total of 24<28 in all of the rows. We see that we can select 24 points:

$\bullet\bullet\bullet\circ\circ\circ\circ\circ\\ \bullet\circ\circ\bullet\bullet\circ\circ\circ\\ \bullet\circ\circ\circ\circ\bullet\bullet\circ\\ \circ\bullet\circ\circ\bullet\circ\circ\bullet\\ \circ\circ\bullet\circ\circ\bullet\circ\bullet\\ \circ\bullet\circ\bullet\circ\bullet\circ\circ\\ \circ\circ\bullet\circ\bullet\circ\bullet\circ\\ \circ\circ\circ\bullet\circ\circ\bullet\bullet$

It remains a problem that 25 points are impossible. We do a proof by contradiction. By the pigeonhole principle, there must be a column with at least 4 points on it. Looking at the 4 rows that the four points are on, we see that since there must not be 2 identical pairs, by pigeonhole there must be a row with at most 2 points. This is because the seven possible points each form a pair, and among 4 rows, one must have at most one pair, or 2 points.

Among the remaining 7 rows, there are at least 23 points, and at least 2 rows with at least 4 points. We see that those 2 rows share at most 1 point in common. Now notice that among the remaining 5 rows with at least 15 points, there must be one row with at least 4 points, or 5 rows with 3 points.

If there is one row with with at least 4 points, then there are 3 rows with 4 or more points. Since the first 2 share at most 1 point in common, there is at most 1 point that they do not contain. Therefore, the third row must share a pair in common with one of the first two rows, a contradiction.

If there are 5 rows with 3 pairs, then the only place to position a row of three is to have a point shared with each of the rows of four, and a third point on the point that the rows of fours do not share (If the rows of four do not overlap, we immediately have a contradiction). However, after placing 3 rows of 3, we will have exhausted all of the non-overlapped points of the rows of 4 and reached a contradiction

Therefore, the answer is 24 points.

FYI-My answer is incorrect!

Based on the solution already provided, I'm not sure that I understood the problem correctly, but here is what I did.

I drew out some rectangles with sides that are not parallel to the edges of the grid. I then counted up the number of points used to create all of those rectangles and found the answer to be 30.

*Image updated from original.