Hướng tới kỳ thi chọn đội tuyển Việt Nam dự IMO 2012 Kỳ thi chọn học sinh giỏi quốc gia môn Toán đã trôi qua hơn 1 tháng. Kết quả kỳ thi có lẽ sẽ được công bố chính thức trong vài ngày tới. 42 học sinh xuất sắc nhất sẽ được chọn ra để chuẩn bị cho kỳ thi chọn đội tuyển Việt Nam tham dự IMO 2012 tại Argentina (Vietnam TST 2012). Tôi lập ra chủ đề này để thảo luận một số chủ đề, một số bài toán TST các năm trước và một số bài toán "tầm cỡ" TST để các bạn thí sinh hình dung được mức độ của đề thi TST, cũng như trao đổi một số vấn đề về kinh nghiệm thi. Kỳ thi TST sẽ diễn ra trong 2 ngày, mỗi ngày làm 3 bài toán trong vòng 4 tiếng, như vậy gồm 6 bài toán thuộc các phân môn: Đại số, Hình học, Số học, Tổ hợp. Trong đề thi Vietnam TST, mỗi ngày đều có một bài ở mức độ trung bình, một bài trung bình khó và một bài khó. Mời các cựu TST, cựu IMO, những bạn học sinh đã trải qua kỳ thi này vào chia sẻ kinh nghiệm về cả chuyên môn lẫn tâm lý thi, chiến thuật thi với các đàn em. Dưới đây tôi xin gửi một số bài toán "cỡ TST" để các bạn tham khảo, luyện tập. 1. (Trung bình khó) Cho a, b, c là các số thực dương thỏa mãn điều kiện $a^2 + b^2 + c^2 = 3 $. Chứng minh rằng $(2-ab)(2-bc)(2-ca) \ge 1 $. 2. (VMO 2004, Trung bình khó) Gọi S(n) là tổng các chữ số của số nguyên dương n viết trong hệ thập phân. Hãy tìm giá trị nhỏ nhất của S(n) trong đó n là số nguyên dương chia hết cho 2003. 3. (Trận đấu toán học Nga 2010, khó) Một quốc gia có 210 thành phố. Ban đầu giữa các thành phố chưa có đường. Người ta muốn xây dựng một số con đường một chiều nối giữa các thành phố sao cho: Nếu có đường đi từ A đến B và từ B đến C thì không có đường đi từ A đến C.Hỏi có thể xây dựng được nhiều nhất bao nhiêu đường? 4. (Canadian MOCP 2010, trung bình) Cho tam giác ABC có $A > 90^0, AB < AC $, O là tâm đường tròn ngoại tiếp. M, N là trung điểm của BC và AO và D là giao điểm của MN và AC. Biết rằng $AD = \frac{1}{2}(AB+AC). $ Hãy tìm độ lớn góc A. |
Trích:
Định lý. Đồ thị vô hướng $n $ và có hơn $[\frac{n^2}{4}] $ cạnh thì có tam giác. Quan sát định lý, ta nhận thấy có thể xây dựng đồ thị vô hướng $n $ đỉnh với $[\frac{n^2}{4}] $ cạnh mà không có tam giác. Thật vậy, ta quy nạp: với $n = 1, 2 $ thì nhận xét đúng. Giả sử nhận xét với $n $, ta xét $n+2 $. Để ý rằng $[\frac{(n+2)^2}{4}] = [\frac{n^2}{4}] + n + 1 $. Trước hết chọn ra hai đỉnh A, B rồi dùng giả thiết quy nạp, ta xây dựng đồ thị $[\frac{n^2}{4}] $ cạnh với $n $ đỉnh còn lại. Sau đó, với mỗi đỉnh còn lại, nối chúng với đúng một trong hai đỉnh $A, B $, đồng thời nối $A, B $ với nhau, ta có thêm $n + 1 $ cạnh. Chú ý rằng với hai đỉnh $X, Y $ khác $A, B $, mà trong đồ thị có cạnh $XY $, vì ta nối $AB $, nên nếu nối $XA $ thì phải nối $YB $. Tuy nhiên đều này không gây ra mâu thuẫn, vì giả sử có 3 đỉnh $X, Y, Z $ khác $A, B $ mà có các cạnh $XY, XZ $ (thì không có $YZ $), và ta có thể nối $XA, YA, ZB $. Nhận xét được chứng minh. Xem xét trường hợp đồ thị có hướng $n $ đỉnh, ta thấy có thể xây dựng $2[\frac{n^2}{4}] $ cạnh (mỗi cạnh vô hướng làm thành 2 cung có hướng). Mặt khác, ta chứng minh không thể có nhiều cạnh hơn thế được. Thật vậy, ta vẫn sử dụng quy nạp. Với $n = 3,4 $ ta có thể kiểm tra trực tiếp. Giả sử kết luận này đúng với $n $, xét đồ thị $G $ có hướng $n + 2 $ đỉnh với $2[\frac{(n + 2)^2}{4}] + 1 = 2[\frac{n^2}{4}] + 2n + 3 $ cạnh. Nếu trong $G $ có 2 đỉnh $A, B $ sao cho có các cung $AB $ và $BA $ thì do giả thiết quy nạp, đồ thị con của $G $ cảm sinh bởi $n $ đỉnh còn lại chỉ có tối đa $2[\frac{n^2}{4}] $ cạnh, hơn nữa mỗi đỉnh $X $ trong số $n $ đỉnh này chỉ có thể tạo 2 cạnh trong số 4 cạnh $AX, XA, BX, XB $ (do nếu có $AX $ thì không có $BX $, cũng như nếu có $XA $ thì không có $XB $ và ngược lại), do vậy tổng số cạnh của $G $ không vượt quá $2[\frac{n^2}{4}] + 2n + 2 $ (các cạnh trong $n $ đỉnh còn lại, các cạnh nối giữa chúng với $A, B $, $AB $ và $BA $). Nếu $G $ không có hai đỉnh $A, B $ nào như nói trên (tức nếu có cung $AB $ thì không có cung $BA $), ta chọn 2 đỉnh $A, B $ sao cho trong đồ thị có cung $AB $. Theo giả thiết đồ thị con cảm sinh bởi $n $ đỉnh còn lại của $G $ (ngoài $A, B $) có tối đa $2[\frac{n^2}{4}] $ cạnh, đồng thời mỗi đỉnh $X $ trong số $n $ đỉnh này chỉ tạo 1 cạnh với $A $ hoặc 1 cạnh với $B $ (bởi nếu có cung $XA $ thì không có cung $AX $, cũng như có cung $XB $ thì không có cung $BX $ và ngược lại). Vậy tổng số cạnh của $G $ không vượt quá $2[\frac{n^2}{4}] + 2n + 1 $ (gồm các cạnh trong $n $ đỉnh còn lại, các cạnh nối chung với $A, B $, và $AB $), ta cũng gặp điều vô lý. Tóm lại nhận xét này cũng được chứng minh. Vậy kết quả của bài toán là $2[\frac{210^2}{4}] $. |
Trích:
|
Trích:
|
Trích:
|
Trích:
|
Trích:
Đặt $p=2003 $, $p $ là số nguyên tố. Trước hết ta dễ dàng thấy được $S(n) > 1 $ vì $10^{k} $ không là bội của $2003 $. Xét$ S(n)=2 $, có $2 $khả năng xảy ra TH1:$ n=2.10^{k} $. Trường hợp này không thoả mãn do $p $ không là ước của $10^{k} $và $2 $. TH2: $n=10^{a}+10^{b} (0 \ge b < a) $ Vì $n \vdots 2003 \Rightarrow 10^{a} \equiv -10^{b} (mod p) \Rightarrow 10^{a-b} \equiv -1 (mod p) $ Đặt $k = a - b \Rightarrow 10^{k} \equiv 10^{a-b} \equiv -1 (mod p) $ Do $2^{10} = 1024 \equiv 10^{7} (mod p) $ nên ta có: $(2^{5k})^{2} = 2^{10k} \equiv (10^{7})^{k} \equiv -1 (mod p) $ Do đó $-1 $ là số chính phương modulo $p $, suy ra $p $ có dạng $4t+1 $, đây là điều vô lí. Xét $S(n)=3 $. Ta chứng minh đây là giá trị nhỏ nhất của $S(n) $ Thật vậy, ta có: $2^{10} \equiv 10^{7} (mod p) \Rightarrow 2 \cdot 10^{700} \equiv 2^{1001} = 2^{\dfrac{p-1}{2}} \equiv -1 (mod p) $ (do $2003 $ không co dạng $8t+1 $ hay $8t-1 $ nên $2 $không phải là số chính phương modulo $p $) $\Rightarrow 2 \cdot 10^{700} + 1 \vdots p $ Đặt $n=2 \cdot 10^{700} + 1. $Rõ ràng $n $ là bội của $p=2003 $ và $S(n)=3 $. Vậy $S(n) $ nhỏ nhất bằng $3 $. |
Bài 3: Nhận xét 1: nếu giữa 3 thành phố $A,B,C $ mà có 3 con đường một chiều thì chiều của chúng là $A\rightarrow B\rightarrow C $ hoặc $C\rightarrow B\rightarrow A $. Chứng minh: Hiển nhiên Nhận xét 2: Cứ $4 $ thành phố $A, B, C, D $ thì có 2 thành phố mà giữa chúng không có con đường nào. Chứng minh: Giả sử ngược lại, cứ hai thành phố bất kì trong 4 thành phố $A,B,C,D $ thì có 1 con đường một chiều. Không mất tính tổng quát, ta xét 3 thành phố $A,B,C $. Theo nhận xét 1, chiều của các con đường trong 3 thành phố này là $A\rightarrow B\rightarrow C $ hoặc ngược lại. Không mất tổng quát xem hướng của chúng là $A\rightarrow B\rightarrow C $. Xét thành phố $D $. Nếu có $D\rightarrow A $ thì sẽ không có $C\rightarrow D $. Tức là sẽ phải có $D\rightarrow C $. Nhưng khi đó ta có $D\rightarrow C \rightarrow A $ và $D\rightarrow A $ nên không thỏa mãn. Vai trò của $A,B,C $ như nhau nên ta cũng không có $D\rightarrow B $ hay $D\rightarrow C $. Như vậy thì ta phải có $A\rightarrow D, B\rightarrow D $ và $C\rightarrow D $. Nhưng khi đó $A\rightarrow B\rightarrow D $ và $A\rightarrow D $ nên cũng không thỏa mãn. Vậy điều giả sử là sai. Bổ đề được chứng minh. Trở lại bài toán. Với bổ đề thì ta sẽ có 4 thành phố bất kì thì có hai thành phố không được nối với nhau bởi một con đường ( hướng tùy ý). Áp dụng định lý Turan ta có tổng số con đường không vượt quá $(1-\frac{1}{3})\frac{n^2}{2} = \frac{210^2}{3} $. Xét một cách xây đường như sau: Chia 210 thành phố thành 3 nhóm $X,Y,Z $ mỗi nhóm có 70 thành phố. Ta xây các con đường từ mỗi thành phố trong nhóm X, đến mỗi thành phố trong nhóm Y. Tương tự Y đến Z và Z đến X. Tổng số con đường được xây là $3\times 70^2 = \frac{210^2}{3} $. Dễ thấy là cách xây này thỏa mãn điều kiện bài toán. Kết luận: $\frac{210^2}{3} $. |
Trích:
Định lý. Đồ thị vô hướng $n $ đỉnh không có $k $-clique thì có không quá $[\frac{(k-2)n^2}{2(k-1)}] $ cạnh. Chứng minh của định lý vẫn dựa vào quy nạp và ta vẫn có chú ý rằng có thể dựng đồ thị vô hướng $n $ đỉnh, $[\frac{(k-2)n^2}{2(k-1)}] $ cạnh và không có $k $-clique. Với bài toán, trước hết ta cũng vô hướng hoá đồ thị các đường đi và thành phố để tạo ra đồ thị $G $. Nhận xét rằng $G $ không chứa 4-clique. Thật vậy, giả sử $G $ có 4-clique với các đỉnh $A, B, C, D $. Dễ thấy trước khi vô hướng hoá, trong $A, B, C, D $ có một đỉnh vừa có cung vào vừa có cung ra (giả sử mỗi đỉnh chỉ có cung vào hoặc ra, vậy nếu $A $ có 3 cung ra thì $B, C, D $ phải có toàn cung vào, và ngược lại, vô lý khi ta xét đồ thị con cảm sinh bởi $B, C, D $). Vậy giả sử trong $G $ có các cung $AB $ và $BC $. Theo giả thiết thì trong $G $ phải có cung $CA $. Xét định hướng cạnh $AD $: 1. Nếu ta định hướng $AD $ thì xét tam giác $ABD $, do đã có các cung $AB $ và $AD $ nên cạnh $BD $ định hướng thành cung $BD $ hay $DB $ đều gây ra mâu thuẫn. 2. Nếu ta định hướng $DA $ thì xét tam giác $ABD $, đo dã có các cung $DA $ và $AB $ nên phải có cung $BD $. Lúc này đều vô lý như trường hợp 1 xảy ra với tam giác $BCD $ đã định hướng các cung $BC $ và $BD $. Vậy trong vô hướng hoá của $G $ không có 4-clique. Theo định lý Mantel-Turan, $G $ theo ý nghĩa của đề bài (định hướng mỗi cạnh thành 1 trong 2 cung có thể) có không quá $[\frac{(4-2)\cdot 210^2}{2(4 - 1)}] = \frac{210^2}{3} $ cung. Ta cũng có thể xây dựng $\frac{210^2}{3} $ dựa trên hình ảnh của đồ thị 3 phía. Thậy vậy, phân hoạch tập đỉnh của $G $ thành $A[1..70], B[1..70] $ và $C[1..70] $. Xét tập cung $E(G) = \{A_iB_j, B_jC_k, C_kA_i 1 \leq i, i, k \leq 70\} $, dễ thấy chúng có $3 \cdot 70^2 = \frac{210^2}{3} $ cung (với mỗi bộ $B_iC_j $ tạo ra 3 cung). Vậy kết quả của bài toán là $\frac{210^2}{3} $. Mình xin đóng góp một bài cho các bạn sắp đi thi luyện tập. Đây là bài luyện Putnam của trường mình. Vì viết sau thầy Nam Dũng nên mình đặt đây là bài 5 vậy. 5. Cho $\{a_1, \cdots, a_n\} $ và $\{b_1, \cdots, b_n\} $ là các dãy số nguyên dương thoả mãn đồng thời các điều kiện: $a_1 < a_2 < \cdots < a_n $, $b_1 > b_2 > \cdots > b_n $, và $\{a_1, \cdots, a_n, b_1, \cdots, b_n\} = \{1, 2, \cdots 2n\} $. Chứng minh rằng $\sum_{i = 1}^{n} |a_i - b_i| = n^2 $. |
Trích:
Đặt $ p=a+b+c , q=ab+bc+ca , r=abc $ Theo đề bài ta có $p^2 - 2q =3 \Leftrightarrow q=\frac{p^2-3}{2} $ C/minh $(2-ab)(2-bc)(2-ca)=8-4q+2pr-r^2 \geq 1 $ $\Leftrightarrow 7 \geq \frac{4(p^2-3)}{2}+r^2-2pr $ $\Leftrightarrow 13 \geq 2p^2+r^2-2pr (*) $ $\Leftrightarrow 13 \geq (p-r)^2+p^2 $ Theo bđt Schur:$ r \geq \frac{p(4q-p^2)}{9} = \frac{p(p^2-6)}{9} $ $\Rightarrow VT(*) \leq [p-\frac{p(p^2-6)}{9}]^2 +p^2 $ Cần c/m $[p-\frac{p(p^2-6)}{9}]^2 +p^2 \leq 13 $ $\Leftrightarrow p^6-30p^4+306p^2-1053 \leq 0 $ $\Leftrightarrow (p^2-9)(p^4-21p^2+117) \leq 0 $ đúng vì $ p^2 \leq 3(a^2+b^2+c^2)=9 $ và $p^4-21p^2+117 > 0 $. Vậy ta có đpcm |
Đây cũng là một bài toán rất thú vị. Bài 6: (Làm mạnh Việt Nam TST 1996) Với $a,b,c$ là các số thực bất kỳ, khi đó ta luôn có $$(a+b)^4+(b+c)^4+(c+a)^4\ge \frac{4}{7}[a^4+b^4+c^4+(a+b+c)^4].$$ |
Cảm ơn các bạn đã ủng hộ chủ đề này bằng cách giải, phân tích, bình luận các bài toán và đề xuất thêm một số bài tập. Tôi xin tiếp tục danh sách các bài đề nghị với 2 bài toán lấy từ China MO 2003: Bài 7. Tìm số phần tử lớn nhất của tập S các số nguyên dương thỏa mãn đồng thời các điều kiện sau: 1) Các phần tử của S không vượt quá 100. 2) Với mọi a, b thuộc S, tồn tại c thuộc S sao cho (a, c) = (b, c) = 1. 3) Với mọi a, b thuộc S, tồn tại d thuộc S sao cho (a, d) > 1, (b, d) > 1. Bài 8. Tìm tất cả các bộ số nguyên dương (a, m, n) sao cho: (1) a > 1, m > 1; (2) $a^m + 1 | a^n + 203 $. ------------------------------ Trích:
|
Trích:
Xét * $2q \geq 3 $ tương tự. * $2q < 3 $ $8-4q+2pr-r^2=2(3-2q)+2pr+1-r^2+1>1 $ Ta có dpcm |
Chứng minh với mọi số thực dương a,b,c thì: $a^{3}+b^{3}+c^{3}+3abc\geq \sum ab\sqrt{2\left ( a^{2}+b^{2} \right )} $ |
Trích:
|
Múi giờ GMT. Hiện tại là 02:34 PM. |
Powered by: vBulletin Copyright ©2000-2024, Jelsoft Enterprises Ltd.