Đế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]