Chủ đề này có 1 trả lời

[WhjteShadow]

Bài toán: Cho $A$ là một bảng $n$ hàng $n$ cột với $n\geq 2$, kí hiệu phần tử ở hàng $i$ cột $j$ là $a_{ij}$. Với mọi $k,l$, hoặc $a_{kl}$ là một số nguyên thuộc $[1,n]$ hoặc $a_{kl} = 0$ và $\sum_{i=1}^{n} a_{ki} + \sum_{j=1}^{n} a_{jl} \geq n$. Chứng minh bất đẳng thức:

$$\sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} \geq \dfrac{n^2}{2},$$

và chỉ ra một trường hợp có dấu bằng.

[Donald Trump]

Phản chứng. Gọi $c_i$ là tổng các số trên cột $i$, $h_i$ là tổng các số trên hàng $i$. Do $\sum h_i < n^2/2$ nên ta có thể giả sử $h_n = \min\left \{ h_i,c_i|i=\overline{1,n} \right \} \Rightarrow h_n < n/2$ $\Rightarrow $ hàng $n$ chứa nhiều hơn $n/2$ số $0$. Do khi đổi chỗ các hàng và cột với nhau thì tính chất của bàng không thay đổi nên ta có thể giả sử $a_{ni} = 0$ với mọi $i=\overline{1,q}$ ($q>n/2$).Từ giả thiết $h_n+c_i\geq n \forall i = \overline{1,q}$ nên $c_i\geq n-h_n \forall i=\overline{1,q}$. Mà $q>n/2$ và $h_n < n/2$ nên $\sum c_i = \sum_{i=1}^{q} c_i + \sum_{i>q}^{} c_i \geq \sum_{i=1}^{q} c_i + \sum_{i>q}^{} h_n \geq n\cdot n/2 = n^2/2$ (vô lý). Vậy giả sử sai hay bài toán được chứng minh. $\square$

Dấu bằng chỉ có thể xảy ra khi $n$ chẵn, để chỉ ra có thể điền $a_{ij} = 0$ nên $i+j$ lẻ, còn lại điền số $1$.

PS. Bài này nên xếp vào mục tổ hợp thì đúng hơn.