Chips do not form rectangle on board

Question

Given is an $n\times n$ board with $n\geq 3$. We place a chip in some cells, so that no four chips form a rectangle with sides parallel to the sides of the board. How many chips can we place, at most?

We can place $2n$ chips in positions $(i,i)$ for $1\leq i\leq n$, $(i,i+1)$ for $1\leq i\leq n-1$, and $(n,1)$. Is it possible to improve?

Answer 1

$$\begin{array}{cccc}X&X&X&-\\ -&X&-&X\\ X&-&-&X\\ -&-&X&X\end{array}$$

The $X$'s are coins. This is a counterexample with $N = 4$.

---

In general, consider $S_k \subset \{1, \ldots, N\}$ consisting of the columns which are filled in row $k$.

The requirement is precisely $|S_k \cap S_\ell| \leq 1$ for all $k \neq \ell$.

---

An asymptotic lower bound from finite projective planes:

Collections of subsets of $\{1,\ldots, n\}$ such that any pair intersects in at most one are fairly interesting.

A special case of these are given by finite projective planes, where the set is the set of points and the subsets are the lines. This is a much stricter requirement, of course. There may be a clean solution for the maximum in general in your case.

Finite projective planes give us $n^2+n+1$ points, $n^2+n+1$ lines, and $n+1$ points per line.

This gives an $N\times N$ matrix, with $N = n^2+n+1$, with $(n+1)N \approx N\sqrt{N}$ coins.

So this is an asymptotic lower bound (at least restricted to $N$ of this form where $n$ is a prime power).

---

An asymptotic upper bound:

Let $s_k = |S_k|$. Then we can't repeat a pair, so

$\sum_k {s_k \choose 2} \leq {N \choose 2}$.

Thus $\sum_k s_k(s_k-1) \leq N(N-1)$.

Let's maximize $\sum_k s_k$ subject to $\sum_k s_k(s_k-1) \leq M$.

Let $\mathbf{s}$ be the vector $(s_1,s_2,\ldots,s_N)$. Then

We have $\mathbf{s} \cdot (\mathbf{s} - \mathbf{1}) \leq M$ and we want to bound $\mathbf{s}\cdot \mathbf{1}$.

We have $\mathbf{1} \cdot \mathbf{s} \leq |\mathbf{s}||\mathbf{1}| = \sqrt{N} \mathbf{s}$

So we get $\mathbf{1} \cdot \mathbf{s} \leq \sqrt{N}\sqrt{M + \mathbf{1}\cdot \mathbf{s}}$.

So we have $A \leq \sqrt{N} \sqrt{M+A}$. Squaring we get $A^2 \leq N (M+A)$. So we have $(A - N)A \leq NM$. Thus $A-N \leq \sqrt{NM}$. Thus $A \leq \sqrt{NM}+N$.

Thus $\sum_k s_k \leq \sqrt{N} \sqrt{N(N-1)} + N \approx N \sqrt{N}$.

---

Some amusement:

The kids card game Spot It! has 55 cards, each with 8 animals (and 57 different animals in total). All the cards are different, and any pair of cards has exactly one pair of animals in common. This is $\mathbb{PF}_7$ with two missing lines (probably for printing reasons).

There's also Spot It Jr.! with 31 cards and 6 animals per card (and 31 different animals in total). This is $\mathbb{PF}_5$.

Answer 2

Yes it is possible to improve on $2n$.

Consider $n=6$ and place the chips at $$ \begin{array}{cccccc} (1,1) & & & & (1,5) & \\ (2,1) & (2,2) & & & & (2,6) \\ (3,1) & & (3,3) & & & \\ & (4,2) & (4,3) & (4,4) & & & \\ & (5,2)& & & (5,5) & \\ & & (6,3) & & & (6,6) \end{array} $$ Simple inspection shows that no four of these form a rectangle; the inspection is aided by the fact that any rectangle must include two points in the same row. I leave as an exercise to the reader the proof that this configuration has more than 12 chips.

As to the question of the maximum number oof chips placeable in this manner, I would not be surprised to learn that problem is NP hard.

Answer 3

I can always reach $3n-3$. Write our disposition of chips as follows : the $n$ columns are written as $S_1,\cdots,S_n$ where $S_i \subseteq \{1,\cdots,n\}$ and the condition that we have no rectangles of chips is equivalent to $|S_i \cap S_j| \le 1$, as in aes's answer ; having a rectangle means there is two columns in which the rectangle appears, and a rectangle appears in these two columns if and only if these two columns both have chips in some pair of rows, which explains the criterion.

Split in the cases $n$ even and $n$ odd. In the case $n$ even, let $$ S_1 = \{ 1,\cdots,n/2 \}, \quad S_2 = \{n/2,\cdots,n\} $$ and in the case $n$ odd, we pick $$ S_1 = \{1,\cdots,(n+1)/2\}, \quad S_2 = \{ (n+1)/2,\cdots, n \}. $$ We have $S_1 \cap S_2 =\{(n+1)/2\}$ or $\{n/2\}$ depending on whether $n$ odd or even.

Now we will pick the remaining columns with only two elements, so ensuring that their intersection contains at most one element is equivalent to picking them distinct. But an easy way of ensuring that $S_1 \cap S_k$ and $S_2 \cap S_k$ have at most one element is to build $S_k$ by picking one element in $S_1 \backslash S_2$ and one element in $S_2 \backslash S_1$. This means there are

• $n$ even, $|S_1| = n/2$, $|S_2| = n/2+1$, so there are $(n/2-1)(n/2) = \frac{n^2}4 - \frac n2 \ge n-2$ ways of doing this since $(n/2-1)(n/2)-(n-2) = \frac{(n-3)^2 - 1}4 \ge 0$ for $n \ge 4$ (this fits in our assumptions on $n$),
• $n$ odd, $|S_1| = |S_2| = \frac{n+1}2$, so there are $\frac{(n-1)^2}4 \ge n-2$ ways of doing this since $\frac{(n-1)^2}4 -(n-2) = \frac{(n-3)^2}4 \ge 0$.

Counting the number of chips realized in both cases, we get $3n-3$.

However, this is sadly far from being generally optimal ; it is not even correct for $n=6$, where I have this arrangement of $16 > 15 = 3 \times 6 - 3$ chips : $$ \begin{matrix} - & - & \bullet & \bullet & - & - \\ - & \bullet & \bullet & - & \bullet & - \\ - & \bullet & - & \bullet & - & \bullet \\ \bullet & \bullet & - & - & - & - \\ \bullet & - & - & \bullet & \bullet & - \\ \bullet & - & \bullet & - & - & \bullet \\ \end{matrix} $$ I obtained this by trying to fill the first three columns and then "fill in the last columns" as in the case where I restricted my attention to the first two columns and got $3n-3$. This gave me some extra room, but the combinatorics involved in "filling in the last columns" do not look simpler, so the solution does not look very pretty ; however, it suggests that the solution should be a little bit more than linear in $n$. The asymptotic solution $n \sqrt n$ of aes doesn't sound bad.

Hope that helps,