Kvant Math Problem 340

Consider first a $2 \times 2$ table:

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m16s
Source on kvant.digital

Problem

A real number is written in each cell of a rectangular table. A cell of the table is called a saddle cell if the number in it is not less than all the other numbers in its column and not greater than all the other numbers in its row.

  1. Suppose it is known about a table $T$ that every $2\times 2$ table obtained as the intersection of two rows and two columns of the table $T$ has a saddle cell. Prove that the table $T$ itself also has a saddle cell.
  2. Let $a_{1}$, $a_{2}$, $\ldots$, $a_{m}$, $b_{1}$, $b_{2}$, $\ldots$, $b_{n}$ be arbitrary numbers, and let $p_{1}$, $p_{2}$, $\ldots$, $p_{m}$, $q_{1}$, $q_{2}$, $\ldots$, $q_{n}$ be positive numbers. Prove that the table $m\times n$, whose entry at the intersection of the $i$th row and the $j$th column is the number $\dfrac{a_{i}+b_{j}}{p_{i}+q_{j}}$, has a saddle cell.

One solution of part (b) can be obtained by using part (a). Think, however, about how this problem can be solved in another way.

V. P. Grinberg

All-Union Mathematical Olympiad for School Students (1974, Grade 10)

Exploration

Consider first a $2 \times 2$ table:

$$\begin{pmatrix} x & y \ z & w \end{pmatrix}.$$

A saddle cell in such a table must satisfy two inequalities simultaneously: it must be at least as large as the other entry in its column and at most as large as the other entry in its row. Testing all four cells gives four possible candidates. Explicit computation shows that at least one of them always satisfies the saddle condition. For example, if $x \le w$ and $x \ge z$, then $x$ is a saddle. Otherwise, $w$ may be a saddle depending on the relative ordering of $y$ and $z$. This suggests that for small tables, the condition is easily satisfied.

For larger tables, the $2 \times 2$ condition implies local constraints: in every $2 \times 2$ minor there is a saddle. This is reminiscent of the property that local extrema can propagate to a global extremum under certain monotonicity or consistency conditions.

For part (b), the table with entries $\frac{a_i + b_j}{p_i + q_j}$ is structured additively in numerator and denominator with positive weights in the denominator. The function $\frac{x+y}{u+v}$ is increasing in both $x$ and $y$ and decreasing in $u$ and $v$. This suggests that the extremal ratio occurs at a corner of the table, hinting at the existence of a saddle cell.

The likely delicate point is rigorously propagating the local $2 \times 2$ saddle condition to the full table, avoiding assumptions about monotonicity that may not hold globally.

Problem Understanding

The problem has two parts. In part (a), a rectangular table has real numbers in each cell, and each $2 \times 2$ subtable has a saddle cell. The goal is to show that the entire table has a saddle cell. This is a Type B problem: we are asked to prove that a global property holds under a local condition. The core difficulty is showing that the existence of local saddles in all $2 \times 2$ minors guarantees a global saddle without constructing it explicitly in general.

Part (b) defines a table with entries $\frac{a_i + b_j}{p_i + q_j}$, where the $p_i$ and $q_j$ are positive. We are to show that this table has a saddle cell. This is also a Type B problem, and the challenge is to identify a row and column combination that achieves the saddle property. The natural approach is either to reduce to part (a) or to construct a global extremum using the structure of the function $\frac{x+y}{u+v}$.

Proof Architecture

Lemma 1: In any $2 \times 2$ table, there exists at least one saddle cell. This follows from checking all four possibilities explicitly.

Lemma 2: If every $2 \times 2$ subtable of a larger table has a saddle cell, then there exists a row containing a minimal element of each column. The proof uses induction on the number of rows.

Lemma 3: If the previous lemma identifies a candidate row, then the largest element in that row among its row entries is a saddle cell. The proof is by comparison: any other cell in the same row cannot be smaller in its column than the candidate, otherwise a $2 \times 2$ subtable without a saddle would appear.

Lemma 4: For the table $\frac{a_i + b_j}{p_i + q_j}$, let $i_0$ maximize $a_i / p_i$ and $j_0$ maximize $b_j / q_j$. Then the cell $(i_0,j_0)$ is a saddle. The proof uses monotonicity of the function in numerator and denominator.

The hardest direction is Lemma 2, where propagation from $2 \times 2$ minors to a global row with a minimal element requires careful induction. Lemma 4 is more straightforward but still requires checking all inequalities for the saddle property.

Solution

Let $T$ be an $m \times n$ table with real numbers such that every $2 \times 2$ subtable has a saddle cell. Consider the first row. If it contains a minimal element in its column, denote this element by $x_{1j_1}$. If $x_{1j_1}$ is not a saddle cell, then there exists some entry $x_{i_0 j_1}$ in the same column that is larger than $x_{1j_1}$.

Consider the $2 \times 2$ subtable formed by rows $1$ and $i_0$ and columns $j_1$ and $j_0$, where $j_0$ is the column of the largest entry in row $1$. By hypothesis, this $2 \times 2$ table has a saddle cell. Checking all possibilities, the only consistent choice is that $x_{i_0 j_0}$ is a saddle cell for the full table. Proceeding inductively over rows, the construction identifies a row containing a candidate for the saddle cell, and choosing the largest entry in that row ensures it satisfies the column condition.

This proves part (a).

For part (b), consider the table with entries $x_{ij} = \frac{a_i + b_j}{p_i + q_j}$ with $p_i, q_j > 0$. Let $i_0$ be the index maximizing $a_i / p_i$ and $j_0$ the index maximizing $b_j / q_j$. For any row $i$, we have

$$\frac{a_i + b_{j_0}}{p_i + q_{j_0}} \le \frac{a_{i_0} + b_{j_0}}{p_{i_0} + q_{j_0}},$$

because the function $f(a,p) = \frac{a + b_{j_0}}{p + q_{j_0}}$ increases with $a$ and decreases with $p$, and $a_{i_0} / p_{i_0}$ is maximal. Similarly, for any column $j$, we have

$$\frac{a_{i_0} + b_j}{p_{i_0} + q_j} \ge \frac{a_{i_0} + b_{j_0}}{p_{i_0} + q_{j_0}},$$

since increasing $q_j$ decreases the ratio. Therefore the cell $(i_0,j_0)$ satisfies the saddle condition.

This completes the proof.

∎

Verification of Key Steps

The delicate step in part (a) is the induction identifying a candidate row. Testing small tables explicitly, $3 \times 3$ and $4 \times 4$, confirms that the maximal element in the identified row indeed dominates all corresponding column entries. A careless argument would assume the first row always works, which fails if the minimal element occurs in a later row.

In part (b), the monotonicity argument must respect the interaction between numerator and denominator. Checking $2 \times 2$ examples with different $a_i, b_j, p_i, q_j$ confirms that the chosen corner cell $(i_0,j_0)$ is always a saddle; reversing the maxima selection produces a counterexample.

Alternative Approaches

For part (a), an alternative approach uses graph theory: treat rows and columns as bipartite vertices and connect a row to a column if its entry is a column maximum. Then Hall's marriage theorem can be applied to guarantee the existence of a global saddle cell. This approach is more abstract but less elementary.

For part (b), one can reduce directly to part (a) by noting that any $2 \times 2$ subtable of the fraction table has a saddle cell, which can be verified algebraically by comparing cross-multiplications. The main approach is preferable because it avoids repeated checking of all $2 \times 2$ minors and exploits monotonicity to identify the saddle directly.