Cho bảng vuông 13x13. Người ta tô màu đỏ ở S ô vuông của bảng sao cho không có 4 ô đỏ nào nằm ở 4 góc của một hình chữ nhật. Hỏi giá trị lớn nhất của S có thể là bao nhiêu

Gọi $\displaystyle x_{i}$ là số ô được tô đỏ ở dòng thứ i
Ta có: $\displaystyle S=x_{1} +x_{2} +...+x_{13}$ ở hàng thứ i số các cặp ô đỏ là $\displaystyle C_{x_{i}}^{2} =\frac{x_{i}( x_{i} -1)}{2}$
Vậy tổng số các cặp ô đỏ là: $\displaystyle A=\frac{x_{1}( x_{1} -1)}{2} +\frac{x_{2}( x_{2} -1)}{2} +...+\frac{x_{13}( x_{13} -1)}{2}$
Chiếu các cặp ô đỏ xuống thành một hàng ngang nào đó, theo giả thiết thì không có cặp ô đỏ nào có hình chiếu trùng nhau
Vậy $\displaystyle C_{13}^{2} =78\geqslant A=\frac{x_{1}( x_{1} -1)}{2} +\frac{x_{2}( x_{2} -1)}{2} +...+\frac{x_{13}( x_{13} -1)}{2}$
$\displaystyle \Leftrightarrow \sum _{i=1}^{13} x_{i}^{2} -\sum _{i=1}^{13} x_{i} \leqslant 156$
Áp dụng BĐT Bunhiacopxki ta có:
$\displaystyle  \begin{array}{{>{\displaystyle}l}}
\left(\sum _{i=1}^{13} x_{i}\right)^{2} \leqslant 13\left(\sum _{i=1}^{13} x_{i}^{2}\right) \Rightarrow \frac{S^{2}}{13} -S\leqslant 156\\
\Leftrightarrow S^{2} -13S-2028\leqslant 0\\
\Leftrightarrow S\leqslant 52
\end{array}$
Dấu = xảy ra khi và chỉ khi $\displaystyle x_{1} =x_{2} =...=x_{13} =4$ (mỗi dòng có 4 ô được tô đỏ)
Vậy giá trị lớn nhất của S = 52