Bài 28:Cho bảng hình vuông gồm 13x13 ô vuông.người tatoo màu đỏ ở S ô vuông của bảng sao cho không có 4 ô đỏ nào nằm ở bốn 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 $x_{i}$ là số ô đỏ ở dòng thứ i. Ta có S=$\sum_{i=1}^{13}x_{i}$ .Ở hàng thứ i số các cặp ô đỏ là$C_{x_{i}}^{2}=\frac{x_{i}\left ( x_{i}-1 \right )}{2}$
Vậy tổng số các cặp ô đỏ là $A=\sum_{i=3}^{13}\frac{x_{i}\left ( x_{i}-1 \right )}{2}$
Chiếu các cặp ô đỏ xuống một hàng ngang nào đó . Do giả thiết thì không có cặp ô đỏ nào có hình chiếu trùng nhau.Vậy
$C_{13}^{2}=78\geq A=\sum_{i=3}^{13}\frac{x_{i}\left ( x_{i}-1 \right )}{2}$
<=>$\sum_{i=1}^{13}x_{i}^{2}-\sum_{i=1}^{13}x_{i}\leq 156$
Theo BĐT Bunhiacopxki:
$\left ( \sum_{i=1}^{13} x_{i}\right )^{2}\leq 13\left ( \sum_{i=1}^{13}x_{i}^{2} \right )$ ta suy ra
$\frac{S^{2}}{13}-S\leq \sum_{i=1}^{13}x_{i}^{2}-\sum_{i=1}^{13}x_{i}\leq 156$
<=>$S^{2}-13S-2028\leq 0$
=> $S\leq 52$
Đẳng thức xảy ra khi $x_{1}=x_{2}=...=x_{13}=4$
Mỗi dòng có 4 ô tô đỏ .Ta có thể đễ dàng thực hiện được cách tô màu như vậy.Vậy $S_{Max}=52$