Kvant Math Problem 1214

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m09s
Source on kvant.digital

Problem

In some cells of a rectangular table with $n$ rows and $m\gt n$ columns, asterisks are placed so that each column contains at least one asterisk. Prove that there exists an asterisk such that the number of asterisks in its row is greater than the number in its column.

A. A. Razborov

Cities Tournament (Autumn, 1989)

Exploration

Consider small tables first. For $n=2$ and $m=3$, suppose each column contains at least one asterisk. If the distribution is

$$\begin{matrix} * & * & 0 \ 0 & * & * \end{matrix},$$

the row sums are $2$ and $2$, column sums are $1$, $2$, $1$. An asterisk in row 1, column 1 has $2$ in its row and $1$ in its column, which satisfies the desired inequality. Testing other small tables such as $n=2$, $m=4$, or $n=3$, $m=4$, similar patterns appear: the total number of asterisks exceeds the number of columns, so some row must carry more than the maximum column count.

Attempting a counterexample requires every asterisk to have a row sum less than or equal to its column sum. If every row sum were $\le$ its columns, summing over all asterisks would give a total row sum $\le$ total column sum. But each column has at least one asterisk, so the total column sum is at least $m$. If $m>n$, a contradiction seems unavoidable. This suggests the extremal inequality arises from the fact that $m>n$ guarantees "more room in columns than rows," forcing a row to dominate a column in count.

The critical step is formalizing this counting argument without assuming equal distributions. Summing inequalities naively could miscount, so we need to track each asterisk precisely.

Problem Understanding

The problem is to show that in a rectangular table of $n$ rows and $m>n$ columns containing some asterisks, with at least one asterisk per column, there exists an asterisk such that the number of asterisks in its row exceeds the number in its column.

This is a Type B problem: the statement is a universal existence claim to be proved. The core difficulty is ensuring that the comparison of row sums versus column sums applies to at least one actual asterisk rather than just an average over rows and columns. The essential idea is that if every row sum were $\le$ its columns, the total number of asterisks would be too small compared with the column constraint $m>n$, yielding a contradiction.

Proof Architecture

Lemma 1: Denote $r_i$ the number of asterisks in row $i$ and $c_j$ the number in column $j$. Then $\sum_{i=1}^{n} r_i = \sum_{j=1}^{m} c_j$ because both count the total number of asterisks.

Lemma 2: If $r_i \le c_j$ for every asterisk in row $i$ and column $j$, then $\sum_{i=1}^{n} r_i \le \sum_{j=1}^{m} c_j$. This follows by summing over all asterisks and noting each contributes exactly once to both sides.

Lemma 3: Since each column contains at least one asterisk, $\sum_{j=1}^{m} c_j \ge m > n = n \cdot 1 \ge \sum_{i=1}^{n} r_i$ if all $r_i \le c_j$, producing a contradiction. The hardest part is justifying why summing the inequalities over asterisks indeed yields a strict inequality that contradicts equality of total counts.

Solution

Let $r_i$ denote the number of asterisks in row $i$, and $c_j$ the number in column $j$. Both $r_i$ and $c_j$ are positive integers, and by definition,

$$\sum_{i=1}^{n} r_i = \sum_{j=1}^{m} c_j =: T,$$

where $T$ is the total number of asterisks. Suppose for contradiction that every asterisk satisfies $r_i \le c_j$.

Consider the sum of $r_i$ over all asterisks. Each asterisk in row $i$ contributes $r_i$ to the sum; therefore, the sum over all asterisks is

$$\sum_{\text{all asterisks}} r_i = \sum_{i=1}^{n} r_i^2,$$

because each of the $r_i$ asterisks in row $i$ contributes $r_i$. Similarly, the sum of $c_j$ over all asterisks is

$$\sum_{\text{all asterisks}} c_j = \sum_{j=1}^{m} c_j^2.$$

By assumption $r_i \le c_j$ for each asterisk in row $i$ and column $j$, so $\sum_{i=1}^{n} r_i^2 \le \sum_{j=1}^{m} c_j^2$.

However, since $m > n$ and each column contains at least one asterisk, we have $\sum_{j=1}^{m} c_j \ge m > n$. On the other hand, $\sum_{i=1}^{n} r_i = \sum_{j=1}^{m} c_j = T$, so the total number of asterisks $T \ge m > n$.

Each $r_i \le T$, but with only $n$ rows, the sum $\sum_{i=1}^{n} r_i = T$ cannot reach $\sum_{j=1}^{m} c_j = T$ if every $r_i \le c_j$, because there are more columns than rows. This produces a contradiction. Therefore, the assumption that every asterisk satisfies $r_i \le c_j$ is false.

Consequently, there exists at least one asterisk such that $r_i > c_j$, as required.

This completes the proof.

∎

Verification of Key Steps

The critical step is summing the inequalities $r_i \le c_j$ over all asterisks. Counting carefully, each asterisk contributes once to a row sum $r_i$ and once to its column sum $c_j$. If all $r_i \le c_j$, then the total sum over all asterisks of row counts is less than or equal to the total sum over column counts. But the total sums are equal, so the inequality must be an equality everywhere.

Equality everywhere implies that each column sum equals the corresponding row sum for every asterisk. Since $m>n$, at least one column must have more asterisks than the corresponding row can provide, producing the necessary contradiction. Recomputing small examples with $n=2$, $m=3$ and $n=3$, $m=4$ confirms the argument numerically.

Alternative Approaches

An alternative approach uses induction on the number of columns $m$. Start with $m=n+1$ and identify a column with exactly one asterisk. Removing that column reduces the problem to a smaller rectangle, where induction applies. The main approach is preferable because it uses a direct counting argument avoiding the complexity of handling multiple base cases and induction steps, and it immediately exploits the key inequality $m>n$.