Stars in Array

Form two $n\times m$ arrays: a c-array and an r-array. Consider an $ij$ cell in the original array that contains a star. Let $u_j$ be the total number of stars in its column, $v_i$ the number of stars in its row. Place $\displaystyle \frac{1}{u_j}$ in the corresponding cell of the c-array and $\displaystyle \frac{1}{v_i}$ into the corresponding cell of the r-array. Fill all other cells in the two arrays with zeros.

Let's denote the elements of the c- and r-arrays as $c_{ij}$ and $r_{ij},$ respectively. Then every column of the c-array sums up to $1$ and so is every row of the r-array. Therefore.

$\displaystyle \sum_{j=1}^m\sum_{i=1}^nc_{ij}=m\gt n=\sum_{i=1}^n\sum_{j=1}^mr_{ij}=\sum_{j=1}^m\sum_{i=1}^nr_{ij}.$

Necessarily, then, for some $i,j,$ $\displaystyle \frac{1}{u_j}=c_{ij}\gt r_{ij}=\frac{1}{v_i},$ so that $u_j\lt v_i$ which solves the problem.

In the following we're going to invoke the pigeonhole principle twice:

If $x_1,...,x_r$ are real numbers, then there exists an index $i'$ with $x_{i'} \geq \frac{1}{r} \sum_{i=1}^r x_i.$

Let $M$ be the $n \times m$-matrix containing the stars. Define the following (random) variables:

1. $X_j \in \{ 1,...,n \}$: For the $j$th column of $M$ we randomly chose a row $i$ such that a star inhabits cell $(i,j).$

2. $\displaystyle Y_i = \sum_{j=1}^m \mathbf{1}[X_j=i]$: For the $i$th row we count how many of its stars have been selected.

3. $r_i$ = number of stars in row $i.$

4. $c_j$ = number of stars in column $j.$

Choose the row $i'$ we expect the most stars to be chosen from. Because $\displaystyle \sum_{i=1}^n E[Y_i] = E[\sum_{i=1}^n Y_i] = m,$ this row will satisfy

(1)

$\displaystyle E[Y_{i'}] \geq \frac{m}{n} \gt 1\qquad$ (Pigeonhole principle & $m\gt n$ )

Further $\displaystyle E[Y_{i'}] = \sum_{j=1}^m P(X_j=i')$ with $r_{i'}$ nonzero summands. Thus we find a column $j'$ with

(2)

$\displaystyle P(X_{j'}=i') \geq \frac{E[Y_{i'}]}{r_{i'}} \gt \frac{1}{r_{i'}}\qquad$ (Pigeonhole principle & (1))

Finally

$\displaystyle c_{j'} = \frac{1}{P(X_{j'} = i')} \lt r_{i'}\qquad$ (Uniform distribution & (2)).

This is problem M1214 from the Russian Kvant magazine (n 8, 1990). The problem is by A. Razborov, Solution 1 is by N. Vasilyev; Solution 2 is by Long Huynh Huu.