Possible Duplicate:

Placing checkers on an m x n board This problem seems to relate to the combinatoric design which is unfamiliar for me. Still, it arises my interests.

What is the maximum amount of checkers you can place on an $m \times n$ checkerboard such that **no four checkers make a rectangle** parallel to the rows and columns? Is there existed **a close form** for the relationship between **the number of checkers** and **the size of the checkerboard**.

Some simple observations

Let $\mathscr{C}(m,n)$ be the maximum number of checkers one can place on an $m\times n$ board without any four of them forming a rectangle with sides parallel to the board. We will refer to $m$ as the number of *rows* and $n$ as the number of *columns*.

The roles of $m,n$ are interchangeable, so the function $\mathscr{C}(m,n)$ is symmetric in the sense that $\mathscr{C}(m,n)=\mathscr{C}(n,m)$.

The function is strictly increasing with either argument:

$$ \mathscr{C}(m+1,n) \ge \mathscr{C}(m,n) + 1$$

and when $m,n \gt 1$ we have:

$$ \mathscr{C}(m+1,n+1) \ge \mathscr{C}(m,n)+ 3 $$

For smallish values of $m$ we can work out the maximum number of checkers:

$$ \mathscr{C}(1,n) = n \; ; \; \mathscr{C}(2,n) = n+1 $$

and if $m \ge \binom{n}{2}$ the exact maximum can be reached:

$$ \mathscr{C}(m,n) = \binom{n}{2} + m $$

by placing two checkers on each of $\binom{n}{2}$ rows and one checker on each of the remaining rows (if any).

The challenge is then to obtain good estimates for the intermediate cases, especially when $m,n$ are approximately equal.

**Partial pairwise block designs**

Consider an $m\times n$ incidence matrix with $1$'s in place of checkers on a grid, otherwise $0$'s. In this way we define a combinatorial design, not necessarily uniform, with the rows representing $m$ blocks (lines) and the columns representing $n$ varieties (points).

The requirement that no rectangle is formed by the checkers amounts simply to the condition that no pair of column indexes $(j_1,j_2)$ appears in more than one block (row), equivalently no pair of rows (lines) intersect in more than one point. We do not require that all blocks have an equal number of points (which defines a *uniform* block design) nor that all points are incident with an equal number of lines (a *regular* block design). Some may find the language of finite geometries more appropriate here.

so what is the generalization of this question? and is there existed **a close form**? and how to apply some counting skills in this problem and maybe applied some knowledge in the **combinatorics design** like my duplicated questions.