Placing rooks on a chessboard

Question

We have a big chessboard with N rows and N columns (numbered 1 through N). Let's denote the square in row r and column c of the chessboard by (r,c). We want to place some rooks on the chessboard in such a way that the following conditions are satisfied:

1. Each square of the board contains at most one rook.
2. There are no four rooks forming a rectangle. Formally, there should not be any four valid integers r1, c1, r2, c2 (r1≠r2,c1≠c2) such that there are rooks on squares (r1,c1) , (r1,c2), (r2,c1) and (r2,c2).
3. The number of rooks is at least 8*N.

If there are multiple solutions, find any one. It is guaranteed that under the given constraints, a solution always exists.

Here N can take values from 100 to 1000 i.e. $100 <= N <= 1000$

Answer 1

The key to a solution to this question is related to an OEIS sequence,

A005282

Mian-Chowla sequence (a $B_2$ sequence): $a(1) = 1$; for $n>1$, $a(n) =$ smallest number $> a(n-1)$ such that the pairwise sums of elements are all distinct.

1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, 123, 148, 182, 204, 252, 290, 361, 401, 475, 565, 593, 662, 775, 822, 916, 970, ...

In the following, let $a_n$ denote the $n$-th element of this sequence.

I claim that when you put rooks on the $k$-th row in the following columns:

$k - 1 + a_n$ (where $n$ runs from 1 up to whatever fits on the board)

you won't get any rectangles. The top left would look like this:

RR.R...R
.RR.R...
..RR.R..
...RR.R.
....RR.R
.....RR.
......RR
.......R

Proof of the claim:

Since the pattern is repeating itself, we may assume the top row of the rectangle is the first row. So for a rectangle we'd need to have four points $(1, a_{n_1}), (1, a_{n_2}), (k, k - 1 + a_{n_3}), (k, k - 1 + a_{n_4})$ where $a_{n_1} = k - 1 + a_{n_3}$ and $a_{n_2} = k - 1 + a_{n_4}$. Rearranging we get $a_{n_1} + k - 1 + a_{n_4} = a_{n_2} + k - 1 + a_{n_3}$ so $a_{n_1} + a_{n_4} = a_{n_2} + a_{n_3}$ which is impossible by the definition of the sequence; all sums are pairwise distinct.

But, it turns out that

you can only fit 742 rooks for $N = 100$, which is not good enough, so we need to utilize the bottom left as well.

Therefore, the OEIS sequence needs to be modified

to include negative integers as well. And let's make it start at 0 because that's more convenient. The first numbers are:

0, 1, -2, 5, -8, 15, -20, 31, 42, -48, -67, 76, 100, -121, -153, 170, 192, -227, -256, 280, -368, 394, -420, 481, -551, -594, 657, -750, -827, 839, 896, -938, ...

In the following, let $b_n$ denote the $n$-th element of this sequence.

The top left would look like this:

Now we only need to show how many rooks we can fit.

The rooks corresponding to $b_1 = 0$ will be present on $N$ rows; on $b_2 = 1$ on $N-1$ rows; generally, the ones corresponding to $b_n$ on $N - |b_n|$ rows. Let $B(N)$ denote the largest $n$ such that $|b_n| < N$; then, total number of rooks that fit is $$\sum_{n=1}^{B(N)}(N-|b_n|)=B(N)N-\sum_{n=1}^{B(N)}|b_n|$$.

Here's a table with partial sums:
n b sum
1 0 0
2 1 1
3 -2 3
4 5 8
5 -8 16
6 15 31
7 -20 51
8 31 82
9 42 124
10 -48 172
11 -67 239
12 76 315
13 100 415

So for $N = 100$, $B(N) = 12$ and the number of rooks = $12 \times 100 - 315 = 885 > 8N$. You can check that it holds (with a wider margin) for other $N$ between 100 and 1000.

Answer 2

The main idea is

placing rooks along (parallel) diagonals

Solution (partial, works only for large $N$, namely $122$ or greater)

1. Assume that (1,1) is lower-left corner (like on a regular chessboards).
2. Let's denote each of the "lower-left-to-upper-right" diagonals by a number $a$ such the all squares on it are of the form $(r, r+a)$ (it's probably obvious why they should be).
3. Now, assume that the rooks are placed along some of the diagonals denoted with numbers $a_1, a_2, \dots, a_m$. Let's take 4 squares on those diagonals, 2 on the one row $r_1$ and 2 on the other $r_2$: $(r_1, r_1 + a_{i1}), (r_1, r_1 + a_{i2}), (r_2, r_2 + a_{i3}), (r_2, r_2 + a_{i4})$ (we can assume that $a_{i1}<a_{i2}$ and $a_{i3}<a_{i4}$ without the loss of generality).
4. If they form a rectangle, it should be $r_1+a_{i1}=r_2+a_{i3}$ and $r_1+a_{i2}=r_2+a_{i4}$. That means that $a_{i3}-a_{i1}=a_{i4}-a_{i2}$, or $a_{i1}+a_{i4}=a_{i2}+a_{i3}$. (Note that is can be that $a_{i1}=a_{i4}$ if we form a square, but the other pairs of $a_{ij}$ cannot be equal).
5. Now comes the main idea. If we choose all $a$'s such that no (different) $a_i$, $a_j$, $a_k$, $a_l$ exist where one of the relations $a_i+a_j=a_k+a_l$ or $2a_i=a_j+a_k$ holds, we get no rectangles.
6. Now we need to choose sufficient number of $a$'s (note that a diagonal number $a$ contains $N-|a|$ rooks).
7. The following set of $a$ satisfy the requirements from 5: $\{-48, -47, -45, -41, -36, -28, -18, -4, 17, 32, 48\}$ (it's found by a simple Python script, but is likely not optimal).
8. There are 11 numbers whose absolute values sum up to 364, so the total number of rook is $11N-364$. Unfortunately, it will be greater than $8N$ if $3N>364$, or (assuming only integer values for $N$) $N\geqslant122$.