Đếm bằng 2 cách trong đề HSG tỉnh 2017

[huynhcongbang]

Quan sát các bài tổ hợp trong đề thi HSG tỉnh năm nay, ta thấy rằng có nhiều bài theo tinh thần của đếm bằng 2 cách, phương pháp kinh điển nhưng dường như không bao giờ lỗi thời.

Mọi người xem post 47 trong link bên dưới:

http://mathscope.org/showthread.php?t=51387&page=4

Chẳng hạn các bài: 15, 21, 25, 29 đều có thể giải được nhờ đếm bằng 2 cách.

Mình xin chọn phân tích bài số 15 của Lào Cai như sau:

Mình tin rằng bài gốc của đề này lấy từ bài Ukraine 2013; nhưng nguồn gốc sâu hơn của nó có lẽ là từ bài toán về góc cùng màu khá nổi tiếng.

Trong mặt phẳng cho $6$ điểm phân biệt (không có 3 điểm nào thẳng hàng). Mỗi đoạn thẳng nối 2 điểm được tô bởi một trong hai màu.
a) Chứng minh rằng có 1 tam giác có 3 cạnh cùng màu (Dirichlet dễ dàng).
b) Chứng minh rằng có 2 tam giác có 3 cạnh cùng màu (Dirichlet phức tạp) -> cách gọn đẹp nhất là dùng đếm bằng 2 cách: giả sử có $x$ tam giác như thế thì có $3x$ góc có 2 cạnh cùng màu trong các tam giác thỏa mãn và $20-x$ góc trong các tam giác không thỏa. Đưa về đánh giá số góc cùng màu tại 1 đỉnh là xong.
c) Tổng quát bài toán khi thay 6 bởi $n$, số tam giác cùng màu ít nhất là mấy.

Trở lại bài toán của Lào Cai, ở đây ta thấy thay vì đếm góc cùng màu, ta đếm góc cùng hướng (vectơ cùng hướng ra hoặc cùng hướng vào).
Dưới đây là cách giải cho bài toán này (có phát triển thêm việc tìm min):

Cho đa giác lồi có $17$ đỉnh ${{A}_{1}}{{A}_{2}}{{A}_{3}}...{{A}_{17}}$ và với hai đỉnh ${{A}_{i}},{{A}_{j}}$ bất kỳ trong số các đỉnh của đa giác, ta định hướng cho đoạn thẳng nối chúng để có vectơ: $\overrightarrow{{{A}_{i}}{{A}_{j}}}$ hoặc $\overrightarrow{{{A}_{j}}{{A}_{i}}}$. Sau khi thực hiện với mọi cặp đỉnh, gọi $S$ là số tam giác có tổng các vectơ đặt trên $3$ cạnh là $\overrightarrow{0}$.

a) Tìm giá trị nhỏ nhất của $S.$
b) Tìm giá trị lớn nhất của $S$.

Lời giải.

a) Giá trị nhỏ nhất của $S$ là $0$.
Ta xét cách xây dựng vectơ như sau: với hai đỉnh ${{A}_{i}},{{A}_{j}}$ mà $i>j$, ta định hướng $\overrightarrow{{{A}_{i}}{{A}_{j}}}$. Khi đó, trong mỗi tam giác, luôn có một đỉnh có $2$ vectơ hướng ra, như thế thì tổng các vectơ trên các cạnh của chúng không thể là $\overrightarrow{0}$ được.
b) Ta gọi một góc là khác hướng nếu đỉnh của nó là một trong các đỉnh của đa giác đã cho, trên hai cạnh, hai vectơ đã chọn có hướng đi ra và đi vào. Như thế ta thấy rằng:
- Tam giác thỏa mãn điều kiện đề bài, gọi là tam giác “đẹp”, có số góc khác hướng là $3.$
- Tam giác không thỏa mãn có số góc khác hướng là $1.$

Tổng số tam giác là $C_{17}^{3}$ nên rõ ràng, có tổng cộng
$S\cdot 3+(C_{17}^{3}-S)\cdot 1=680+2S$ góc khác hướng.
Tại một đỉnh ${{A}_{i}}$ nào đó, gọi $x,y$ lần lượt là số vectơ có gốc là ${{A}_{i}}$, có ngọn là ${{A}_{i}}$. Khi đó, số góc khác hướng tại ${{A}_{i}}$ là $xy$. Tuy nhiên, $x+y=16$ nên $xy\le \frac{{{(x+y)}^{2}}}{4}=64$.
Do đó, tổng số góc khác hướng tại tất cả các đỉnh không vượt quá $17\cdot 64=1088$.
Suy ra
$680+2S\le 1088\Leftrightarrow S\le 204.$
Để có mô hình thỏa mãn, ta thấy rằng tại mỗi đỉnh, số vectơ vào và ra phải bằng nhau và bằng $8.$ Ta xây dựng như sau:
Với mỗi đỉnh $i$, ta có $2$ trường hợp:
* Nếu $j<i$ và $j$ cùng tính chẵn lẻ với $i$ thì nối từ $\overrightarrow{{{A}_{i}}{{A}_{j}}}$; nếu $j$ khác tính chẵn lẻ với $i$ thì nối $\overrightarrow{{{A}_{j}}{{A}_{i}}}.$
* Nếu $j>i$ và $j$ cùng tính chẵn lẻ với $i$ thì nối từ $\overrightarrow{{{A}_{j}}{{A}_{i}}}$; nếu $j$ khác tính chẵn lẻ với $i$ thì nối $\overrightarrow{{{A}_{i}}{{A}_{j}}}.$
Dễ dàng kiểm tra được các xây dựng trên thỏa mãn ràng buộc của bài toán.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[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]