Kvant Math Problem 335
Represent the marked cell centers by a $0$-$1$ matrix.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 10m27s
Source on kvant.digital
Problem
- In a square of $7\times7$ cells, the centers of $k$ cells are marked. Moreover, no four marked points form the vertices of a rectangle with sides parallel to the sides of the square. What is the largest possible $k$ for which this is possible?
- Solve the same problem for a square of $13\times13$ cells.
S. B. Gashkov, A. A. Grigoryan
All-Union Mathematical Olympiad for School Students (1975, grades 8–10)
Exploration
Represent the marked cell centers by a $0$-$1$ matrix. Rows and columns correspond to the $n$ rows and columns of the board. A marked center is a $1$.
A rectangle with sides parallel to the board is determined by two rows and two columns. Thus four marked points form such a rectangle exactly when there exist two rows having marked points in the same two columns.
Hence the condition is equivalent to the following: for any two distinct rows, the sets of marked columns intersect in at most one column.
Let $r_i$ be the number of marked points in row $i$. Every row contributes $\binom{r_i}{2}$ pairs of columns. Since no pair of columns can occur in two different rows, the total number of column pairs counted this way is at most $\binom{n}{2}$. Therefore
$$\sum_{i=1}^{n}\binom{r_i}{2}\le \binom{n}{2}.$$
For $n=7$ this becomes
$$\sum \binom{r_i}{2}\le 21.$$
If $k=\sum r_i$, then maximizing $k$ under this constraint suggests keeping the $r_i$ as equal as possible, because $\binom{x}{2}$ is convex. Testing possibilities, $k=21$ gives average row sum $3$. Taking all seven rows of size $3$ yields exactly
$$7\binom{3}{2}=21,$$
so the bound is tight if such a configuration exists. A configuration with seven $3$-element subsets of a $7$-set, every pair of columns occurring exactly once, is the Fano plane incidence structure. Thus $k=21$ is achievable.
For $n=13$ we obtain
$$\sum \binom{r_i}{2}\le 78.$$
If $k=39$, average row sum is $3$. Taking all thirteen rows of size $3$ gives
$$13\binom{3}{2}=39\le 78,$$
so the pair-counting bound alone is far from sufficient.
A stronger estimate is needed. Write
$$\sum r_i(r_i-1)\le 13\cdot12=156.$$
By Cauchy,
$$k^2=\left(\sum r_i\right)^2 \le 13\sum r_i^2 =13\left(\sum r_i(r_i-1)+k\right) \le 13(156+k).$$
Hence
$$k^2-13k-2028\le0.$$
The positive root is $52$, since
$$52^2-13\cdot52-2028=0.$$
Thus $k\le52$.
Now check attainability. Equality in Cauchy requires all $r_i$ equal, so $r_i=4$. Then $k=52$. Equality in the pair-counting estimate requires every pair of columns to occur in exactly one row. Thus we need thirteen $4$-subsets of a $13$-set such that every pair of points lies in exactly one block. This is precisely the projective plane of order $3$, which exists. Therefore $k=52$ is attainable.
The delicate point is proving the upper bound $52$ and identifying the equality conditions.
Problem Understanding
We have an $n\times n$ board, with $n=7$ and $n=13$. Some cell centers are marked. Four marked centers form an axis-parallel rectangle exactly when they lie in two rows and two columns.
The condition says that no such rectangle may occur.
This is a Type C problem. We must determine the largest possible number $k$ of marked centers and prove both attainability and optimality.
The core difficulty is obtaining a sufficiently strong upper bound. A simple count of pairs of columns yields the exact answer for $n=7$, but not for $n=13$. For $13\times13$ one must combine the pair count with Cauchy's inequality and then identify an extremal configuration.
The answers are
$$k_{\max}=21 \quad (n=7),$$
and
$$k_{\max}=52 \quad (n=13).$$
The reason is that extremal configurations correspond to finite projective geometries: the Fano plane for $n=7$ and the projective plane of order $3$ for $n=13$.
Proof Architecture
Let $r_i$ denote the number of marked points in the $i$-th row.
Lemma 1. The absence of rectangles is equivalent to the statement that any two rows have marked points in at most one common column. This follows directly from the definition of an axis-parallel rectangle.
Lemma 2. For an $n\times n$ board,
$$\sum_{i=1}^{n}\binom{r_i}{2}\le\binom{n}{2}.$$
Each pair of marked columns in a row determines a column pair, and no column pair can occur in two different rows.
Lemma 3. For $n=7$,
$$k=\sum r_i\le21.$$
This follows from Lemma 2 and the inequality $\binom{x}{2}\ge x-2$ for integers $x\ge0$.
Lemma 4. The bound $21$ is attained by seven $3$-element subsets of a $7$-set in which every pair of elements occurs exactly once.
Lemma 5. For $n=13$,
$$k^2\le13(156+k).$$
This follows from Lemma 2 and Cauchy's inequality.
Lemma 6. Lemma 5 implies $k\le52$.
Lemma 7. Equality $k=52$ is attained by thirteen $4$-element subsets of a $13$-set in which every pair of elements occurs exactly once.
The hardest part is the derivation of the sharp upper bound $52$ and the verification that equality conditions match an existing incidence structure.
Solution
Let the board have size $n\times n$. For each row $i$, let $r_i$ be the number of marked points in that row.
Four marked points form a rectangle with sides parallel to the board exactly when there are two rows containing marked points in the same two columns. Hence the condition of the problem is equivalent to the following:
For any two distinct rows, the sets of marked columns have at most one common element.
For a fixed row $i$, the marked columns determine $\binom{r_i}{2}$ pairs of columns. Since the same pair of columns cannot occur in two different rows, the total number of such pairs does not exceed the total number of column pairs. Therefore
$$\sum_{i=1}^{n}\binom{r_i}{2}\le\binom{n}{2}.$$
We first consider the case $n=7$.
Since
$$\binom{x}{2}=\frac{x(x-1)}2\ge x-2 \qquad (x\ge0),$$
we obtain
$$21\ge\sum_{i=1}^{7}\binom{r_i}{2} \ge\sum_{i=1}^{7}(r_i-2) =k-14.$$
Thus
$$k\le35.$$
This estimate is not sharp. To sharpen it, write
$$\sum_{i=1}^{7}\binom{r_i}{2}\le21.$$
The function $\binom{x}{2}$ is convex. For a fixed value of $k=\sum r_i$, the quantity $\sum\binom{r_i}{2}$ is minimized when the $r_i$ differ by at most $1$.
Assume $k\ge22$. Then the average row sum exceeds $3$, so the minimum of $\sum\binom{r_i}{2}$ occurs for one row of size $4$ and six rows of size $3$:
$$\sum\binom{r_i}{2} \ge \binom42+6\binom32 =6+18 =24.$$
This contradicts the inequality $\sum\binom{r_i}{2}\le21$.
Hence
$$k\le21.$$
To show that $21$ is attainable, number the columns by the elements of the set
$${0,1,2,3,4,5,6}.$$
Take the seven rows corresponding to the seven triples
$${0,1,3},; {1,2,4},; {2,3,5},; {3,4,6},; {4,5,0},; {5,6,1},; {6,0,2}.$$
Each row contains three marked points. Every pair of columns occurs in exactly one row. Consequently two rows have at most one common marked column, so no rectangle appears.
The number of marked points is
$$7\cdot3=21.$$
Therefore
$$k_{\max}=21.$$
Now consider $n=13$.
From
$$\sum_{i=1}^{13}\binom{r_i}{2}\le78$$
we obtain
$$\sum_{i=1}^{13}r_i(r_i-1)\le156.$$
Hence
$$\sum_{i=1}^{13}r_i^2 = \sum_{i=1}^{13}r_i(r_i-1)+\sum_{i=1}^{13}r_i \le156+k.$$
Applying Cauchy's inequality,
$$k^2 = \left(\sum_{i=1}^{13}r_i\right)^2 \le 13\sum_{i=1}^{13}r_i^2 \le 13(156+k).$$
Therefore
$$k^2-13k-2028\le0.$$
Since
$$52^2-13\cdot52-2028=0,$$
the positive root equals $52$, and thus
$$k\le52.$$
To attain this bound, take the incidence matrix of the projective plane of order $3$. It has $13$ points and $13$ lines. Each line contains $4$ points, each pair of points lies on exactly one line, and each pair of lines meets in exactly one point.
Use the $13$ points as columns and the $13$ lines as rows. Mark the cells corresponding to incidences.
Every row contains $4$ marked points, so the total number of marks is
$$13\cdot4=52.$$
Because two rows meet in exactly one column, no two rows contain the same pair of columns. Hence no rectangle is formed.
Thus
$$k=52$$
is achievable, and the upper bound is sharp.
Therefore
$$\boxed{k_{\max}=21 \text{ for } 7\times7,\qquad k_{\max}=52 \text{ for } 13\times13.}$$
Equality holds for the configurations described above.
Verification of Key Steps
The first delicate step is the translation into row intersections. Suppose two rows contain marked points in columns $a$ and $b$. Then the four cells determined by those rows and columns are marked, producing a rectangle. Conversely, every axis-parallel rectangle arises from two rows and two columns. Thus the condition is exactly that any two rows share at most one marked column.
The second delicate step is the bound for the $7\times7$ case. If $k=22$, the average row sum is $22/7$. Among all integer row sums totaling $22$, the most balanced distribution is $(4,3,3,3,3,3,3)$. Its pair count equals $24$. Any less balanced distribution increases the pair count because $\binom{x}{2}$ is convex. Since $24>21$, $k=22$ is impossible. This confirms that $21$ is the largest feasible value.
The third delicate step is the derivation of $k\le52$ for the $13\times13$ case. Starting from
$$\sum r_i(r_i-1)\le156,$$
one gets
$$\sum r_i^2\le156+k.$$
Cauchy's inequality gives
$$k^2\le13\sum r_i^2.$$
Combining them yields
$$k^2\le13(156+k).$$
Solving the quadratic exactly gives the root $52$. Any arithmetic slip here would destroy the sharp bound.
Alternative Approaches
For the $7\times7$ case one may identify the problem immediately with a family of subsets of a $7$-element set having pairwise intersections of size at most $1$. Counting pairs of columns yields the upper bound $21$, and the Fano plane supplies a configuration achieving it. This approach is shorter but relies on recognizing the underlying design.
For the $13\times13$ case one may use a standard inequality from incidence theory. Let $c_j$ denote the number of marked points in column $j$. Counting ordered pairs of marked points lying in the same row and applying the incidence bound known as Fisher's inequality leads to the same extremal value. The argument given above is preferable because it uses only elementary pair counting and Cauchy's inequality, while still reaching the sharp bound.