[huynhcongbang]

Tiếp theo, ta xét bài của Thanh Hóa.

Bài gốc là đề thi Olympic SV quốc tế 2010. Tuy nhiên đề bài chỉ dừng lại ở việc đánh giá chặn trên cho số ô có thể tô để không có hình chữ nhật nào.

Bằng cách thay $n$ tùy ý bởi số nguyên tố, ta có thể xây dựng được một cách tổng quát như bên dưới (có liên quan đến yếu tố số học):

Cho số nguyên tố $p$. Trên bàn cờ hình vuông có cạnh ${{p}^{2}}+p+1$, tìm số lớn nhất các ô có thể tô màu sao cho không tồn tại hình chữ nhật có 4 đỉnh cùng màu và các cạnh song song với các cạnh của hình chữ nhật.
Lời giải.
Ta đếm số bộ $(A,B,C)$ với hai cột $A,B$ và hàng $C$ giao nhau tại hai ô được tô màu.
(1) Đếm theo hàng. Gọi ${{x}_{i}}$ là số ô được tô màu ở hàng thứ $i$.
Số các cặp các ô được tô màu thuộc cùng một hàng là $S=\sum\limits_{i=1}^{{{p}^{2}}-p+1}{C_{{{x}_{i}}}^{2}}$.
(2) Đếm theo hai ô $A,B.$
Số cách chọn hai cột $A,B$ là $C_{{{p}^{2}}+p+1}^{2}$ và có không quá một hàng $C$ tương ứng cắt hai hàng tại hai ô được tô màu (do giả thiết không có hình chữ nhật) nên $S\le C_{{{p}^{2}}+p+1}^{2}$.
Gọi $\alpha $ là số lượng lớn nhất các ô vuông có thể tô thì $$\sum\limits_{i=1}^{{{p}^{2}}+p+1}{{{x}_{i}}}= \alpha .$$
Suy ra $C_{{{p}^{2}}+p+1}^{2}\ge \sum\limits_{i=1}^{{{p}^{2}}+p+1}{C_{{{x}_{i}}}^{2 }}\ge \frac{1}{2}\left( \frac{1}{{{p}^{2}}+p+1}{{\alpha }^{2}}-\alpha \right)$ nên $\alpha \le (p+1)({{p}^{2}}+p+1).$
Ta sẽ chỉ ra một cách tô thỏa mãn đề bài.
Xét các bộ $(a,b,c)$ mà $0\le a,b,c\le p-1$ với $a+b+c>0$ thì có tất cả ${{p}^{3}}-1$ bộ.
Ta xem 2 bộ $(a,b,c)$ và $(d,e,f)$ thuộc cùng một lớp khi và chỉ khi $\exists k\in \left\{ 1,2,3,...,p-1 \right\}$ sao cho $a\equiv kd,b\equiv ke,c\equiv kf(\bmod p)$ nên có tất cả ${{p}^{2}}+p+1$ lớp và ta đánh số chúng từ 1 đến ${{p}^{2}}+p+1$.
Nếu có hai bộ $(a,b,c)$ và $(d,e,f)$ lần lượt thuộc lớp $i,j$ mà $ad+be+cf$ chia hết cho $p$ thì tô màu ô $(i,j)$.
Thật vậy, mỗi hàng có đúng $p+1$ ô. Ta sẽ chứng minh rằng $ax+by+cz\equiv 0(\bmod p)$ có đúng $p+1$ nghiệm (2 nghiệm thuộc một lớp thì coi như là một nghiệm).
Có ${{p}^{2}}-1$ bộ $(x,y)$ mà ứng với chúng, tồn tại duy nhất $z$ sao cho $ax+by+cz$ chia hết cho $p$. Mỗi lớp có $p-1$ nghiệm nên có $p+1$ nghiệm. Nhân số lượng này với số cột, ta có đpcm.
Tiếp theo, ta sẽ chứng minh rằng không tồn tại hình chữ nhật.
Hệ sau có không quá một nghiệm
$$\left\{ \begin{align}
& ax+by+cz\equiv 0(\bmod p) \\
& dx+ey+fz\equiv 0(\bmod p) \\
\end{align} \right.$$
Giả sử $\frac{b}{e}\ne \frac{c}{f}$ hay $bf\ne ce$ thì với mọi ${{x}_{0}}$, tồn tại duy nhất ${{y}_{0}}$ sao cho
$by+cz=\alpha ,ey+fz=\beta $.
Tuy nhiên, có $p$ giá trị ${{x}_{0}}$ và nghiệm $(0,0,0)$ bị loại đi nên có không quá $p-1$ nghiệm.
Chú ý rằng nếu $(x,y,z)$ là nghiệm của hệ đồng dư trên thì $(kx,ky,kz)$ cũng thỏa mãn, dẫn đến có không quá 1 nghiệm.
Từ đó ta có điều kiện đủ của bài toán.
Vậy GTLN cần tìm là $\alpha =(p+1)({{p}^{2}}+p+1)$.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]