How do we place $8n$ objects in a grid of size $n \times n$?

How do we place $8n$ objects on a square of size $n\times n$ in a form of grid such that no 4 of them form a rectangle with sides parallel to those of square? Each object occupies exactly one cell in the grid and two objects cannot occupy the same cell. We are given $n\geq 100$.

Example. The following can be a $7\times7$ portion of some large grid (say $200\times200$), where 0 and 1 denote empty and filled cells respectively):

0000111  
0101001
0011100
0110010
1010001
1001010
1100100

What approach one should follow to solve the problem?

Source: codechef.com MAY Long challenge "Ada Rooks 2"

Given a set of objects in a cell grid, if no 4-set of it forms a rectangle with sides parallel to the sides of the grid, we will call those objects rectangle-free.

The more general problem is to determine sequence A072567, whose $n$-th term $M_n$ is the size of maximal set of rectangle-free cells in an $n \times n$ cell grid. Its first 13 entries are

$$1, 3, 6, 9, 12, 16, 21, 24, 29, 34, 39, 45, 52, \cdots$$

It looks like the value of $M_{14}$ is unknown, which does not matter for the current problem, though.

We know that $M_{q^2+q+1}=(q+1)(q^2+q+1)$ when $q$ is a power of a prime number. In particular, letting $q=4,5,9,11,13$, we get $M_{21}=105$, $M_{31}=186$, $M_{91}=910$, $M_{133}=1596$, $M_{183}=2548$.

For a square grid of size $n\ge100$, we will select disjoint smaller square grids along its main diagonal line and fill the maximal set of rectangle-free cells in each of those smaller squares.

-
If $100\le n\le 113$, select a grid of size 91 since $91

-
If $114\le n\le 125$, select one grid of size 91 and one grid of 21 since $91+21\lt 114$ and $M_{91}+M_{21}=910 + 105\gt 8 \times 125.$

-
If $126\le n\le 132$, select one grid of size 91 and one grid of 31 since $91+31\lt 126$ and $M_{91}+M_{31}=910 + 186\gt 8 \times 132.$

-
If $133\le n\le 182$, select one grid of size 133 since $133\le 133$ and $M_{133}=1596\gt 8 \times 182.$

-
If $183\le n\le 300$, select one grid of size 183 since $183\le 183$ and $M_{183}=2548\gt 8 \times 300.$

-
if $200+100k\le n\lt200+100(k+1)$ for some $k\ge1$, select one grid of size 183 and $k$ grids of size 91 since $183+91k\lt 200+100k$ and $M_{183}+kM_{91}=2548+910k>800(300+100k)\gt8n$.

Now the problem is shifted to realize $M_{q^2+q+1}=(q+1)(q^2+q+1)$ for $q=4,5,9,11,13$. The realizations comes from finite projective planes that is built on top of finite fields, which is explained in detail here.

There are many packages that helps computation of finite fields.

Here is how to fill $21\times21$ grid with 105 objects. Note that there are exactly 5 objects in each row and each column.

000000000000000011111
010001000100010000001
000100010001000100001
001000100010001000001
000011110000000010000
010010000001001001000
000110000010010000100
001010000100000100010
000000000000111110000
010000010010100000010
000100100100100001000
001001000001100000100
000000001111000010000
010000101000000100100
000101001000001000010
001000011000010001000
100010001000100000001
100001000010000101000
100000100001010000010
100000010100001000100
111100000000000010000

Here is how to fill $31\times31$ grid with 186 objects, where empty cells are left as whitespaces. Note that there are exactly 6 objects in each row and each column.

111111
    1    1    1    1    1     1
  1    1    1    1    1       1
   1    1    1    1    1      1
 1    1    1    1    1        1
                    111111     
    1   1   1   1   1        1 
  1      1 1      1 1       1  
   1  1       1  1  1      1   
 1     1     1     11     1    
          11111          1     
    1  1  1       1  1     1   
  1   1   1        1   1     1 
   1     11     1     1   1    
 1      1 1      1      1   1  
               11111     1     
    1 1      1 1      1     1  
  1     1     11     1    1    
   1   1   1   1        1    1 
 1       1  1  1       1   1   
     11111               1     
    11     1     1     1  1    
  1  1       1  1       1  1   
   1 1      1      1 1      1  
 1   1        1   1   1      1 
1    1    1    1    1         1
1        1   1   1   1       1 
1       1  1       1  1    1   
1      1      1 1      1    1  
1     1     1     1     1 1    
11111                    1

Exercise 1. Refine the algorithm so that it uses only $M_{21}=105$, $M_{31}=186$, $M_{91}=910$, $M_{133}=1596$, i.e., without $M_{182}$.

Exercise 2. (Open problem) The smallest $n$ such that we can fill $8n$ rectangle-free objects in an $n\times n$ grid is 57 since $M_{57}=8\times57$ for $q=7$. What is the biggest $n$ such that we cannot fill $8n$ rectangle-free objects?

StackExchange Computer Science Q#109000, answer score: 5