![]() | ![]() | | ![]() |
|
|
![]() |
Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé ! * Quy định về việc viết bài trong diễn đàn MathScope * Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây |
![]() ![]() |
|
![]() | #1 |
Administrator ![]() ![]() | Äếm bằng 2 cách trong Ä‘á» HSG tỉnh 2017 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. __________________ Sá»± im lặng của bầy mèo ![]() |
![]() | ![]() |
babyteen9x (03-11-2017), foollockholmes (05-11-2017), MATHSCOPE (03-11-2017), thaygiaocht (04-11-2017) |
![]() | #2 |
Administrator ![]() ![]() | 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)$. __________________ Sá»± im lặng của bầy mèo ![]() |
![]() | ![]() |