5
$\begingroup$

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"

$\endgroup$
  • 3
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercise- and programming-contest-style problems for you is unlikely to achieve that. You might find this page helpful in improving your question. Also, where did you encounter this problem? Can you cite the original source for it? $\endgroup$ – D.W. May 5 at 18:01
  • 1
    $\begingroup$ Have you tried small examples first, before trying on $n \geq 100$? For example, what how many objects can you place to fit these constraints on a $3 \times 3$ grid? You can do at least 4 clearly, I think 5 and 6 also work. Can you generalize an approach to work on larger grids? $\endgroup$ – ryan May 5 at 21:38
5
$\begingroup$

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<100$ and $M_{91}=910 \gt 8 \times 113.$

  • 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?

$\endgroup$
  • $\begingroup$ how to decide at which places we have to place objects?? Do we have any algorithm for it?? $\endgroup$ – Viplaw Srivastava May 7 at 8:39
  • $\begingroup$ can you show me the distribution for n=57 $\endgroup$ – Viplaw Srivastava May 7 at 17:00
  • $\begingroup$ Here is Python code that produces $M_{q^2+q+1}$ with prime $q$. $\endgroup$ – Apass.Jack May 18 at 17:35
2
$\begingroup$

Here is one way to do it. I figured this out through experimentation.

For any grid of size $n \geq 100$ we completely fill out the following diagonals:

$$[0, -1, 2, -5, 8, -15, 20, -31, -42, 48, 67, -76]$$

We fill these out from top left to bottom right where diagonal $0$ is the top-left to bottom-right diagonal (slope -1) starting at index $G_{0,0}$. Diagonal $i$ is the slope -1 diagonal starting at index $G_{0,i}$ if $i \geq 0$ or the slope -1 diagonal starting at index $G_{|i|,0}$ if $i < 0$. This means diagonal 20 starts at $G_{0,20}$ and diagonal -5 starts at $G_{5,0}$. The first few on a small $10 \times 10$ grid would look like this:

  |0123456789
 -+----------
 0|1010000010
-1|1101000001
-2|0110100000
-3|0011010000
-4|0001101000
-5|1000110100
-6|0100011010
-7|0010001101
-8|0001000110
-9|0000100011

After you have determined one of the entries in the diagonal does not cause a rectangle, the rest will follow by symmetric translation$^*$. For instance in this example, consider entry $G_{5,0}$. It lines up with the following entries vertically: $$[G_{0,0}, G_{1,0}]$$ And the following entries horizontally: $$[G_{5,4}, G_{5,5}, G_{5,7}]$$ We can take each pair of these to determine which diagonal would have to be present to form a rectangle:

  • $G_{0,0}$ and $G_{5,4}$ need entry $G_{0,4}$ on diagonal $4$.
  • $G_{0,0}$ and $G_{5,5}$ need entry $G_{0,5}$ on diagonal $5$.
  • $G_{0,0}$ and $G_{5,7}$ need entry $G_{0,7}$ on diagonal $7$.
  • $G_{1,0}$ and $G_{5,4}$ need entry $G_{1,4}$ on diagonal $3$.
  • $G_{1,0}$ and $G_{5,5}$ need entry $G_{1,5}$ on diagonal $4$.
  • $G_{1,0}$ and $G_{5,7}$ need entry $G_{1,7}$ on diagonal $6$.

This is why the "next" available diagonal is diagonal $8$ because all others would cause rectangles with the existing diagonals. You can use similar logic to show that diagonals $[-2, -3, -4]$ would have cause rectangles earlier. This logic can apply to all of the diagonals above for grids of size $83 \times 83$ or larger.


We can prove this setting will always give over $8n$ entries present $P(n)$. For $n \geq 76$, the number of entries present with the given diagonals is:

$$\begin{align*} P(n) &= n + (n-1) + (n-2) + (n-5) + (n-8) + (n-15) + (n-20) + (n-31) + (n-42) + (n-48) + (n-67) + (n-76)\\ P(n) &= 12n - 315\\ \end{align*}$$

Clearly for $n = 100$ this satisfies:

$$1200-315 =885 \geq 800$$

Then for any $n' = n + 1$ where $n \geq 100$ we simply get:

$$\begin{align*} P(n') & \geq 8n'\\ 12 + P(n) & \geq 8n+8\\ 12 & \geq 8 & \square \end{align*}$$


$^*$ I add this asterisk because this is not quite always correct. It is correct for $n \geq 100$ but not in general. Consider the following diagonals on a $7 \times 7$ grid: $$[0, -1, 2, -5, 6]$$ We get:

  |0123456
 -+-------
 0|1010001
-1|1101000
-2|0110100
-3|0011010
-4|0001101
-5|1000110
-6|0100011

We see this is fine for $n = 7$, however, when we move to $n=8$, this diagonals will not work:

  |01234567
 -+--------
 0|10100010
-1|11010001<
-2|01101000
-3|00110100
-4|00011010
-5|10001101<
-6|01000110
-7|00100011
   ^      ^

There is a rectangle made of the rows and columns I've pointed out. So this does not always hold with translation symmetry because sometimes the grid size is actually helping us by preventing further rows and columns from conflicting on the diagonals.


My procedure for finding this was just to "select the next non-conflicting diagonal" and this actually works really well for small grids. For instance, it is perfect for $n \leq 13$ we get (best comes from A072567):

 n | best | I filled | diagonals to use
---+------+----------+-----------------
 2 |    3 |        3 | 0, -1           
 3 |    6 |        6 | 0, -1, 2           
 4 |    9 |        9 | 0, -1, 2           
 5 |   12 |       12 | 0, -1, 2           
 6 |   16 |       16 | 0, -1, 2, -5           
 7 |   21 |       21 | 0, -1, 2, -5, 6           
 8 |   24 |       24 | 0, -1, 2, -5                      
 9 |   29 |       29 | 0, -1, 2, -5, 8                      
10 |   34 |       34 | 0, -1, 2, -5, 8                                 
11 |   39 |       39 | 0, -1, 2, -5, 8                                 
12 |   45 |       45 | 0, -1, 2, -5, 8, -11                                 
13 |   52 |       52 | 0, -1, 2, -5, 8, -11, 12           
14 |    ? |       54 | 0, -1, 2, -5, 8                                 
15 |    ? |       59 | 0, -1, 2, -5, 8                                 
16 |    ? |       65 | 0, -1, 2, -5, 8, 15

You can see there is a pattern arising, but it's not consistent as you can see it changes when we get to certain values of $n$. To show how close of an approximation this gets, we can use the examples in Apass.Jack's answer:

  n | best | I filled | diagonals to use
----+------+----------+-----------------
 21 |  105 |       98 | 0, -1, 2, -5, 8, -15, 18
 31 |  186 |      171 | 0, -1, 2, -5, 8, -15, 20, -27, 30
 91 |  910 |      777 | 0, -1, 2, -5, 8, -15, 20, -31, -42, 48, 67, -76
133 | 1596 |     1335 | 0, -1, 2, -5, 8, -15, 20, -31, -42, 48, 67, -76, -100, 112

So it's clearly a lower bound. There also doesn't seem to be a known pattern in the diagonals other than the trivial pattern of "this is what I calculated under these constraints". What is interesting is if we only use non-negative diagonals then we get pattern A025582. However, I cannot find a pattern for positive and negative diagonals.

$\endgroup$
  • 1
    $\begingroup$ Nice answer. The solution runs great on codechef. $\endgroup$ – Apass.Jack May 21 at 20:06
  • $\begingroup$ Thanks, glad to see it works (didn't actually test it). It also appears to be pretty fast which is good for Python. $\endgroup$ – ryan May 21 at 21:45
0
$\begingroup$

Exchanging rows and columns makes no difference. You need on average 8 items per row, so I'd try to find something with exactly 8 items per row. And any two rows must have at most one column in common.

So we put 8 items into the first eight columns of the first row. Row 2 has 1 item in column 1, and seven more in columns 9..15. Row 3 has 1 item in column 2, one in column 9, and six in columns 16..21. Similar for rows 4 to 8, showing that you need at least 36 columns (n ≥ 36).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.