Diễn Đàn MathScope

Diễn Đàn MathScope (http://forum.mathscope.org/index.php)
-   2012 (http://forum.mathscope.org/forumdisplay.php?f=175)
-   -   Hướng tới kỳ thi chọn đội tuyển Việt Nam dự IMO 2012 (http://forum.mathscope.org/showthread.php?t=29035)

namdung 18-02-2012 07:55 AM

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.

Mashimaru 18-02-2012 10:14 AM

Trích:

Nguyên văn bởi namdung (Post 137506)
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?

Em nghĩ ý của bài này là dựa vào định lý Mantel-Turan (không biết có đúng không ạ):
Đị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}] $.

namdung 18-02-2012 10:50 AM

Trích:

Nguyên văn bởi Mashimaru (Post 137515)
Em nghĩ ý của bài này là dựa vào định lý Mantel-Turan (không biết có đúng không ạ):
Định lý. Đồ thị vô hướng $n $ và có hơn $[\frac{n^2}{4}] $ cạnh thì có tam giác.

....
Vậy kết quả của bài toán là $2[\frac{210^2}{4}] $.

Hiếu hơi nhầm 1 chút. Đây là đồ thị có hướng. Hiếu đang giải bài vô hướng.

Mashimaru 18-02-2012 10:53 AM

Trích:

Nguyên văn bởi namdung (Post 137517)
Hiếu hơi nhầm 1 chút. Đây là đồ thị có hướng. Hiếu đang giải bài vô hướng.

Em đang làm bài có hướng thầy ơi. Ý em là từ đồ thị vô hướng có thể tạo ra đồ thị có hướng bằng cách với mỗi cạnh $AB $ thì tạo ra 2 cung $AB $ và $BA $.

thinhptnk 18-02-2012 02:12 PM

Trích:

Nguyên văn bởi namdung (Post 137506)
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 $.

Ta có thể sử dụng phương pháp pqr để chứng minh BĐT này (nói chung nhìn vào bài này xuất hiện rất nhiều tư tưởng hiện đại, pqr là một trong số đó). Một vấn đề cũng thú vị là yêu cầu tìm giá trị nhỏ nhất của $P=(2-a)(2-b)(2-c) $ (cùng giả thiết, điểm rơi lệch tâm).

namdung 18-02-2012 05:15 PM

Trích:

Nguyên văn bởi Mashimaru (Post 137518)
Em đang làm bài có hướng thầy ơi. Ý em là từ đồ thị vô hướng có thể tạo ra đồ thị có hướng bằng cách với mỗi cạnh $AB $ thì tạo ra 2 cung $AB $ và $BA $.

OK. Tuy nhiên vì đây là đường 1 chiều nên phải hiểu là: nếu có đường đi từ A --> thì không có đường đi từ B đến A nữa.

conami 18-02-2012 05:15 PM

Trích:

Nguyên văn bởi namdung (Post 137506)
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.

Bài 2 này sử dụng một số tính chất của số chính phương modulo.
Đặ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 $.


Traum 19-02-2012 12:59 AM

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} $.

Mashimaru 19-02-2012 07:34 AM

Trích:

Nguyên văn bởi namdung (Post 137543)
OK. Tuy nhiên vì đây là đường 1 chiều nên phải hiểu là: nếu có đường đi từ A --> thì không có đường đi từ B đến A nữa.

Dạ, nếu vậy thì vẫn có thể dựa vào định lý Mantel-Turan, nhưng trong trường hợp tổng quát hơn:
Đị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 $.

lihoangto 19-02-2012 02:24 PM

Trích:

Nguyên văn bởi namdung (Post 137506)

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 $.

Em xin làm bài này bằng cách pqr.
Đặ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

Nguyenhuyen_AG 19-02-2012 03:41 PM

Đâ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].$$

namdung 19-02-2012 07:55 PM

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:

Nguyên văn bởi lihoangto (Post 137656)
Em xin làm bài này bằng cách pqr.
Đặt $ p=a+b+c , q=ab+bc+ca , r=abc $

...

<=> $13 \ge (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ẩn thận hơn ở chỗ này.

5434 19-02-2012 08:43 PM

Trích:

Nguyên văn bởi namdung (Post 137668)


Cần cẩn thận hơn ở chỗ này.

Chỗ này sửa dễ thôi.
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

hotraitim 19-02-2012 09:15 PM

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 )} $

5434 19-02-2012 09:19 PM

Trích:

Nguyên văn bởi hotraitim (Post 137678)
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 )} $

Bài nầy có 1 cách là xài SOS T_TT_TT_T


Múi giờ GMT. Hiện tại là 02:34 PM.

Powered by: vBulletin Copyright ©2000-2024, Jelsoft Enterprises Ltd.

[page compression: 33.72 k/35.42 k (4.80%)]