Điền số vào bảng vuông

Đề bài:
Điền vào các ô vuông của bảng vuông $3n\times 3n$ các số 0 và 1 sao cho với mỗi ô vuông chứa số 1 thì tổng của $6n-1$ số trên hàng và cột chứa ô vuông đó không vượt quá 2. Tìm giá trị lớn nhất của tổng tất cả các số trong bảng.

Lời giải:
Chia bảng vuông đã cho thành $n^2$ bảng vuông $3\times3$. Với mỗi bảng vuông con có chứa ô vuông thuộc đường chéo chính, ta sẽ điền 4 số 1 vào các ô ở hàng 1 và cột 1, trừ ô vuông nằm trên đường chéo chính. Tất cả các ô vuông còn lại điền số 0. Khi đó, tổng tất cả các số trong bảng là $4n$.
Ta sẽ chứng minh với mọi cách điền, tổng tất cả các số sẽ không vượt quá $4n$.
Ta chia các số 1 trong bảng thành 3 loại: Loại 1 gồm các số 1 không cùng hàng hoặc cùng cột với bất kỳ số 1 nào khác, loại 2 gồm các số 1 cùng hàng với 1 số 1 khác, loại 3 gồm các số 1 cùng cột với 1 số 1 khác.
Giả sử có $x$ số 1 loại 1, $y$ số 1 loại 2 và $z$ số 1 loại 3.
Nhận thấy: $x$ số 1 loại 1 phủ $x$ hàng và $x$ cột, $y$ số 1 loại 2 phủ $\displaystyle \frac{y}{2}$ hàng và $y$ cột, $z$ số 1 loại 3 phủ $z$ hàng và $\displaystyle \frac{z}{2}$ cột, suy ra: $\displaystyle 6n\geq2x+\frac{3y}{2}+\frac{3z}{2}\ge\frac{3}{2}(x+y+z)$
Từ đó dẫn tới: $x+y+z\le4n$, đpcm.