1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

This is the Zarankiewicz problem. It has also appeared on Mathoverflow several times, for example here.

$\endgroup$
  • $\begingroup$ Also note this is putting edges in a bipartite graph and hoping to avoid cycles of length 4. $\endgroup$ – Pat Devlin Jan 27 '17 at 14:06
  • $\begingroup$ @Brendan McKay, This is a high school problem, can you use induction or some other combinatorics skills $\endgroup$ – Mclalalala Mar 6 '17 at 3:32

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.