Việt Nam TST 2010(Đề thi-Đáp án-Danh sách đội tuyển) - Page 4

number_theory · 19-04-2010, 10:35 AM

Trích:

Nguyên văn bởi meou

Theo mình thây thì bài 5 kha' quen nhưng phức tạp, không biết có bác nào giải ra đuợc ngay trong phòng thi không?

Bài này thậm chí trong lớp mình cũng được học rồi.Chắc với các cao thủ TST thì không có vấn đề đâu!

Coloveka · 19-04-2010, 10:42 AM

mấy bài đó ở mình phải tự học chứ thầy cô ít khi dạy lắm

vnmo · 19-04-2010, 11:09 AM

mình từng thi tst năm ngoái. mình thấy đề năm nay dễ lấy điểm hơn năm ngoái. ít nhất là bài bất đẳng thức, bài hình học, bài số ngày 1. bài tổ hợp ngày đầu nếu mình nhớ ko nhầm thì có 1 bài tương tự trong 1 số toán học tuổi trẻ năm 1993, 1994 gì đó( bạn nào có những số báo năm đó xác minh lại hộ mình). thực ra mình nói điều này ra chỉ để chứng minh thêm điều mà các bạn đã nói: ban ra đề thi chưa sáng tạo. năm ngoái mình chỉ làm dc 1 bai hinh va bai bdt.bài số năm ngoái khó hơn năm nay nhiều. dù sao mình tin rằng người giỏi nhất sẽ dc chọn. nhưng sẽ co những bạn trúng tủ liệu có còn gặp may ở IMO??????

math10A1 · 19-04-2010, 02:33 PM

um,đoán già đoán non mãi.Theo mình thì năm nay điểm chuẩn TST là 21,không hơn ko kém đâu.

pte.alpha · 19-04-2010, 05:16 PM

Thấy các bạn nói nhiều đến định lý Hall và định lý Lucas, tôi có hỏi các thầy thì được trả lời rằng "Các định lý này khi dùng phải chứng minh" (ít nhất là ở VMO và Vietnam TST, còn IMO thì không biết)

Ngoài ra, tôi cũng quan tâm đến câu hỏi "Liệu có cách giải các bài 5 và 6 mà không sử dụng các định lý tương ứng không?".

Tạm thời, tôi thử đưa ra 1 ý tưởng cho bài 5:

Tôi gọi ý tưởng này là "chọn theo thứ tự vật lý". Để cho tiện, ta phát biểu bài toán dưới dạng ngôn ngữ tập hợp.

Có n tập con k phần tử $A_1, A_2, ..., A_n $ của {1, 2, ..., n}, trong đó mỗi phần tử xuất hiện đúng k lần. Chứng minh rằng có thể chọn các phần tử phân biệt $a_1, a_2, ..., a_n $ sao cho $a_i \in A_i $.

Ý tưởng làm như sau: Cứ chọn theo thứ tự vật lý các phần tử từ trái sang phải, từ trên xuống dưới. Lúc nào không chọn được nữa thì dừng lại xử lý.

Ví dụ 1: {1, 2, 3}, {2, 3, 5}, {2,4, 5}, {1, 3, 4}, {1, 4, 5}

Ta chọn 1 ở tập (xóa hết các 1 khác), 2 ở tập 2 (xóa hết các 2 khác), 4 ở tập 3 (xóa hết các 4 khác), 3 ở tập 4 (xóa hết các 3 khác) và 5 ở tập 5.

Ví dụ 2: {1, 3, 4}, {2, 3, 5}, {2, 4, 5}, {1, 2, 4}, {1, 3, 5}

Ta chọn 1 ở tập 1, 2 ở tập 2, 4 ở tập 3. Sang đến tập 4 thì ta bí. Ta quay trở lại các tập trước thì thấy có thể lấy 3 làm diện cho 1 còn 1 làm đại diện cho 4.

Ví dụ 3: {3, 6, 7}, {5, 6, 7}, {1, 3, 4}, {2, 3, 5}, {2, 4, 5}, {1, 2, 4} ...

Theo cách trên, ta chọn được các đại diện là 3, 5, 1, 2, 4 và đến đây thì bí. Ta quay lại trước tìm cách thay thế, nhưng cách thay thế ở đây phức tạp hơn: 6 đại diện cho 1, 3 đại diện cho 3 và 1 đại diện cho 4.

Ý tưởng là như vậy. Bây giờ cần tìm cách trình bày sao cho gọn gàng, súc tích và chặt chẽ.

lovemaths_hn · 19-04-2010, 06:11 PM

Trích:

Nguyên văn bởi Nhím

Đề thi năm nay rõ ràng là có sơ suất cực kỳ lớn. Nên tổ chức thi tuyển lại cho công bằng !

Thanks bạn nha! Được như bạn nói thì tốt quá nhỉ!

Ngày đầu mình làm được bài 1,3, và chém một ít bài 2. Ngày hai làm dược bài 5,6. Không biết tình hình các đội khác thế nào nhỉ?Giờ thì đành ngồi đợi kết quả thôi, không biểt bao giờ thì có kết quả nhỉ.

pte.alpha · 19-04-2010, 09:28 PM

Nhìn danh sách trên đã thấy 6 ứng viên rồi. Tuy nhiên, cần kiểm tra lại lời giải cho chắc chắn. Với các bài 1, 2, 4 thì không nói, nhưng các bài 3, 5, 6, đặc biệt là các bài tổ hợp thì rất dễ sai hoặc lý luận không chặt chẽ.

Cũng tiếc cho bạn gì ở trên làm được 3, 5, 6 mà lại không làm được 2, 4. Có lẽ là làm mấy bài kia (nhất là bài 3) cũng mất hết thời gian rồi.

Như mọi năm thì TST chấm cũng khá nhanh, quan trọng là kế hoạch chấm của Bộ thế nào thôi.

**Mr Stoke** · 19-04-2010, 09:40 PM

Bài 6 nếu không dùng định lý Lucas có thể dùng đa thức đồng dư, nhưng vẫn phải bám vào cái khai triển 3-adic.

nbkschool · 19-04-2010, 09:56 PM

Nghe nói 1 PTNK,1 THSP Trình và Hưng đều 4 bài.Phú Yên cả 3 người làm ngày 1 khá tốt.

**Traum** · 19-04-2010, 10:23 PM

Trích:

Nguyên văn bởi pte.alpha

Thấy các bạn nói nhiều đến định lý Hall và định lý Lucas, tôi có hỏi các thầy thì được trả lời rằng "Các định lý này khi dùng phải chứng minh" (ít nhất là ở VMO và Vietnam TST, còn IMO thì không biết)

Ngoài ra, tôi cũng quan tâm đến câu hỏi "Liệu có cách giải các bài 5 và 6 mà không sử dụng các định lý tương ứng không?".

Tạm thời, tôi thử đưa ra 1 ý tưởng cho bài 5:

Tôi gọi ý tưởng này là "chọn theo thứ tự vật lý". Để cho tiện, ta phát biểu bài toán dưới dạng ngôn ngữ tập hợp.

Có n tập con k phần tử $A_1, A_2, ..., A_n $ của {1, 2, ..., n}, trong đó mỗi phần tử xuất hiện đúng k lần. Chứng minh rằng có thể chọn các phần tử phân biệt $a_1, a_2, ..., a_n $ sao cho $a_i \in A_i $.

Ý tưởng làm như sau: Cứ chọn theo thứ tự vật lý các phần tử từ trái sang phải, từ trên xuống dưới. Lúc nào không chọn được nữa thì dừng lại xử lý.

Ví dụ 1: {1, 2, 3}, {2, 3, 5}, {2,4, 5}, {1, 3, 4}, {1, 4, 5}

Ta chọn 1 ở tập (xóa hết các 1 khác), 2 ở tập 2 (xóa hết các 2 khác), 4 ở tập 3 (xóa hết các 4 khác), 3 ở tập 4 (xóa hết các 3 khác) và 5 ở tập 5.

Ví dụ 2: {1, 3, 4}, {2, 3, 5}, {2, 4, 5}, {1, 2, 4}, {1, 3, 5}

Ta chọn 1 ở tập 1, 2 ở tập 2, 4 ở tập 3. Sang đến tập 4 thì ta bí. Ta quay trở lại các tập trước thì thấy có thể lấy 3 làm diện cho 1 còn 1 làm đại diện cho 4.

Ví dụ 3: {3, 6, 7}, {5, 6, 7}, {1, 3, 4}, {2, 3, 5}, {2, 4, 5}, {1, 2, 4} ...

Theo cách trên, ta chọn được các đại diện là 3, 5, 1, 2, 4 và đến đây thì bí. Ta quay lại trước tìm cách thay thế, nhưng cách thay thế ở đây phức tạp hơn: 6 đại diện cho 1, 3 đại diện cho 3 và 1 đại diện cho 4.

Ý tưởng là như vậy. Bây giờ cần tìm cách trình bày sao cho gọn gàng, súc tích và chặt chẽ.

Hướng giải: ta giả sử là với mọi cách chọn thì ta chỉ chọn ra được bộ có độ dài lớn nhất $m $ là $(i,A_i) $ thỏa mãn là $i\in A_i , i = 1,2,..,m $.

Đặt $S = \{1,..,m\} $, $X_0 = \bigcup\limits_{i=m+1}^{n}A_i $.
Nếu có $x\in X_0 $ mà $x\notin S $, thì tồn tại $j $ mà $m+1\le j\le n $ và $x\in A_j $, khi đó ta có bộ
$1 \in A_1,...,m\in A_m, x\in A_j $ sẽ lớn hơn bộ ban đầu (trái với giả thiết).
Vậy ta có $X_0\subset S $.
Ta xét một dãy các phép biến đổi tập hợp được định nghĩa như sau.
$X_{h+1} = \bigcup\limits_{i\in X_{h}}A_i, \forvall h = 0,1,2,... $,

Với cách xây dựng trên thì ta sẽ có với mọi $h $ thì do $X_0\subset S $ nên $X_0 \subset X_1 $ ( do $i\in A_i $ với mọi $i\in X_0 $).
Tiếp tục ta sẽ có $X_{h} \subset X_{h+1} $ với mọi $h = 0,1,2... $.

Đến đây ta sẽ xét 2 trường hợp :

Trường hợp 1: tồn tại $p_0 > m $ nhỏ nhất $\bigcup\limits_{i\in X_{p_0}}X_i $ chứa một phần tử $x > m $. Không mất tổng quát, xem $x \in A_{q_0} $. Với $q \in X_{p_0} - X_{p_0-1} $ nhỏ nhất ( vì tính nhỏ nhất của $p $)
Ta có $x\in A_{q_0} $, với $q_0 $ thì tồn tại $p_1 $ nhỏ nhất mà $q_0\in\bigcup\limits_{i\in X_{p_1}}A_i $, và gọi $q_1 $ nhỏ nhất mà $q_0 \in A_{q_1} , q_1 \in X_{p_1}-X_{p_1-1} $ (do tính nhỏ nhất của $q_0 $).

Cứ như thế ta có dãy $x,q_0,q_1,..,q_l $ với $q_l\in X $ thỏa mãn:
$x\in A_{q_0}, q_0\in A_{q_1},.., $$q_{l-1}\in A_{q_l} $, Do $q_l $ thuộc $X $ nên tồn tại $r\in \{m+1,...,n\} $ mà $q_l\in X_r $. Kết hợp với các $a_i $ còn lại ta có bộ có độ dài $m+1 $ thỏa mãn, trái với giải thiết.

Trường hợp 2: không tồn tại $p_0 $ như trên. Khi đó ta có $X_{h} \subset S $ với mọi $h $ và do $X_{h}\subset X_{h+1} $ nên đến lúc nào đó thì chúng sẽ thành một hằng tập hợp là $X^* $
Nhưng rõ ràng là với mọi $\bigcup\limits_{i\in X^*}} A_i = X^* \subset X^* $. Do đó ta có $A_i\subset X^* $ với mọi $i\in X_h $. Rõ ràng khi đó $\sum\limits_{i\in X^*}|A_i| = k\times|X^*| (*) $. Nhưng có một điều là $A_{s} $ lại chứa một phần tử thuộc tập $X_0 $ với $s $ nào đó thuộc $[m+1,n] $. Do $s>m $ nên $s \notin X^* $ đó ta có $\sum\limits_{i\in X^*}|A_i| < k\times|X^*| $ mâu thuẫn với (*). Do đó trường hợp này không xảy ra.

Điều trên đã kết thúc chứng minh của bài toán.

**namdung** · 20-04-2010, 04:12 PM

Trích:

Nguyên văn bởi dragon_pt

Mình nghĩ cũng tầm chục người $\geq 4 $.
Ăn nhau trình bày và chém gió

.

Điều đặc biệt là năm nay thi xong không có thí sinh nào lên đây chém gió. Rõ ràng họ đã học được bài học: chém gió lúc này chả có lợi tí nào cả.

Hiện nay chưa thấy ai đưa ra lời giải đầy đủ cho bài 3.

**Traum** · 20-04-2010, 07:17 PM

Lời giải trên do mình nghĩ ra khi đọc gợi ý của pte.alpha, trong lúc tìm link cho bài toán tổng quát của định lý Hall (là định lý gì đó quên mất rồi) thì có link này [Only registered and activated users can see links. ], lời giải của nó chính là lời giải mà mình đã post ở trên, viết một cách tường minh hơn.

Chú ý là cách giải trên cũng giải quyết được cho bài toán tổng quát của định lý Hall là :

Trong một đồ thị 2 mảng $G(X,Y,E) $ và số tự nhiên $d $. Biết rằng với $I $ là tập các đỉnh bất kì thuộc $X $ thì tập các đỉnh kề với ít nhất 1 đỉnh trong $I $ là $N(I) $ và $|N(I)| \ge |I| - d $. Khi đó tồn tại ít nhất $|X|-d $ cạnh $xy $ đôi một không có đỉnh chung.

Định lý Hall là trường hợp ứng với $d = 0 $.

**Traum** · 20-04-2010, 07:47 PM

Trích:

Nguyên văn bởi namdung

Điều đặc biệt là năm nay thi xong không có thí sinh nào lên đây chém gió. Rõ ràng họ đã học được bài học: chém gió lúc này chả có lợi tí nào cả.

Hiện nay chưa thấy ai đưa ra lời giải đầy đủ cho bài 3.

Gợi ý thầy ơi

, hôm trước ngồi nghĩ tí nhưng chịu, không ra, chỉ mò ra được cách tô thôi, còn chứng minh cho số 1006 là nhỏ nhất em vẫn chưa biết làm thế nào.

hieu_math · 20-04-2010, 07:51 PM

hi lần này đúng là ko thấy có ai lớn tiếng chém gió nữa thật. Thưa thầy, thấy có tại liệu nào về tổ hợp ko? có thể gửi cho em được ko ạ? địa chỉ e-mail của em là [Only registered and activated users can see links. ]. Em cảm ơn thầy.

**conga1qt** · 21-04-2010, 02:37 PM

Ai có lời giải câu 3 thì post dùm em với ạ ?
P/s: Eh_g8 là anh nào thế ạ ?

19-04-2010, 02:33 PM	#49
math10A1 +Thành Viên+ Tham gia ngày: Nov 2007 Bài gởi: 110 Thanks: 14 Thanked 51 Times in 20 Posts	um,đoán già đoán non mãi.Theo mình thì năm nay điểm chuẩn TST là 21,không hơn ko kém đâu. __________________ THE END. Đại Học thôi,lằng nhằng trên mang để làm gì ?

19-04-2010, 09:56 PM	#54
nbkschool +Thành Viên+ Tham gia ngày: Dec 2007 Đến từ: SMU Residence @Prinsep Hostel, 83 Prinsep Street, Singapore Bài gởi: 400 Thanks: 72 Thanked 223 Times in 106 Posts	Nghe nói 1 PTNK,1 THSP Trình và Hưng đều 4 bài.Phú Yên cả 3 người làm ngày 1 khá tốt. __________________ "Apres moi,le deluge"

20-04-2010, 07:17 PM	#57
Traum Moderator Tham gia ngày: Nov 2007 Đến từ: cyber world Bài gởi: 413 Thanks: 14 Thanked 466 Times in 171 Posts	Lời giải trên do mình nghĩ ra khi đọc gợi ý của pte.alpha, trong lúc tìm link cho bài toán tổng quát của định lý Hall (là định lý gì đó quên mất rồi) thì có link này [Only registered and activated users can see links. ], lời giải của nó chính là lời giải mà mình đã post ở trên, viết một cách tường minh hơn. Chú ý là cách giải trên cũng giải quyết được cho bài toán tổng quát của định lý Hall là : Trong một đồ thị 2 mảng $G(X,Y,E) $ và số tự nhiên $d $. Biết rằng với $I $ là tập các đỉnh bất kì thuộc $X $ thì tập các đỉnh kề với ít nhất 1 đỉnh trong $I $ là $N(I) $ và $\|N(I)\| \ge \|I\| - d $. Khi đó tồn tại ít nhất $\|X\|-d $ cạnh $xy $ đôi một không có đỉnh chung. Định lý Hall là trường hợp ứng với $d = 0 $. __________________ Traum is giấc mơ.

21-04-2010, 02:37 PM	#60
conga1qt Moderator Tham gia ngày: Nov 2007 Đến từ: ANT Bài gởi: 266 Thanks: 9 Thanked 31 Times in 24 Posts	Ai có lời giải câu 3 thì post dùm em với ạ ? P/s: Eh_g8 là anh nào thế ạ ? __________________ Ăn mày thứ cấp :nemoflow: :secretsmile:

19-04-2010, 10:42 AM	#47
Coloveka +Thành Viên+ Tham gia ngày: Dec 2008 Đến từ: Trường THPT Chuyên Lê Khiết - Quảng Ngãi Bài gởi: 30 Thanks: 8 Thanked 2 Times in 2 Posts	mấy bài đó ở mình phải tự học chứ thầy cô ít khi dạy lắm

19-04-2010, 11:09 AM	#48
vnmo +Thành Viên+ Tham gia ngày: Apr 2010 Đến từ: bay qua bay lại giữa Hà Nội và Hà Tịnh Bài gởi: 12 Thanks: 2 Thanked 7 Times in 3 Posts	mình từng thi tst năm ngoái. mình thấy đề năm nay dễ lấy điểm hơn năm ngoái. ít nhất là bài bất đẳng thức, bài hình học, bài số ngày 1. bài tổ hợp ngày đầu nếu mình nhớ ko nhầm thì có 1 bài tương tự trong 1 số toán học tuổi trẻ năm 1993, 1994 gì đó( bạn nào có những số báo năm đó xác minh lại hộ mình). thực ra mình nói điều này ra chỉ để chứng minh thêm điều mà các bạn đã nói: ban ra đề thi chưa sáng tạo. năm ngoái mình chỉ làm dc 1 bai hinh va bai bdt.bài số năm ngoái khó hơn năm nay nhiều. dù sao mình tin rằng người giỏi nhất sẽ dc chọn. nhưng sẽ co những bạn trúng tủ liệu có còn gặp may ở IMO??????

19-04-2010, 05:16 PM	#50
pte.alpha +Thành Viên+ Tham gia ngày: Apr 2009 Bài gởi: 216 Thanks: 8 Thanked 208 Times in 62 Posts	Thấy các bạn nói nhiều đến định lý Hall và định lý Lucas, tôi có hỏi các thầy thì được trả lời rằng "Các định lý này khi dùng phải chứng minh" (ít nhất là ở VMO và Vietnam TST, còn IMO thì không biết) Ngoài ra, tôi cũng quan tâm đến câu hỏi "Liệu có cách giải các bài 5 và 6 mà không sử dụng các định lý tương ứng không?". Tạm thời, tôi thử đưa ra 1 ý tưởng cho bài 5: Tôi gọi ý tưởng này là "chọn theo thứ tự vật lý". Để cho tiện, ta phát biểu bài toán dưới dạng ngôn ngữ tập hợp. Có n tập con k phần tử $A_1, A_2, ..., A_n $ của {1, 2, ..., n}, trong đó mỗi phần tử xuất hiện đúng k lần. Chứng minh rằng có thể chọn các phần tử phân biệt $a_1, a_2, ..., a_n $ sao cho $a_i \in A_i $. Ý tưởng làm như sau: Cứ chọn theo thứ tự vật lý các phần tử từ trái sang phải, từ trên xuống dưới. Lúc nào không chọn được nữa thì dừng lại xử lý. Ví dụ 1: {1, 2, 3}, {2, 3, 5}, {2,4, 5}, {1, 3, 4}, {1, 4, 5} Ta chọn 1 ở tập (xóa hết các 1 khác), 2 ở tập 2 (xóa hết các 2 khác), 4 ở tập 3 (xóa hết các 4 khác), 3 ở tập 4 (xóa hết các 3 khác) và 5 ở tập 5. Ví dụ 2: {1, 3, 4}, {2, 3, 5}, {2, 4, 5}, {1, 2, 4}, {1, 3, 5} Ta chọn 1 ở tập 1, 2 ở tập 2, 4 ở tập 3. Sang đến tập 4 thì ta bí. Ta quay trở lại các tập trước thì thấy có thể lấy 3 làm diện cho 1 còn 1 làm đại diện cho 4. Ví dụ 3: {3, 6, 7}, {5, 6, 7}, {1, 3, 4}, {2, 3, 5}, {2, 4, 5}, {1, 2, 4} ... Theo cách trên, ta chọn được các đại diện là 3, 5, 1, 2, 4 và đến đây thì bí. Ta quay lại trước tìm cách thay thế, nhưng cách thay thế ở đây phức tạp hơn: 6 đại diện cho 1, 3 đại diện cho 3 và 1 đại diện cho 4. Ý tưởng là như vậy. Bây giờ cần tìm cách trình bày sao cho gọn gàng, súc tích và chặt chẽ.

19-04-2010, 09:28 PM	#52
pte.alpha +Thành Viên+ Tham gia ngày: Apr 2009 Bài gởi: 216 Thanks: 8 Thanked 208 Times in 62 Posts	Nhìn danh sách trên đã thấy 6 ứng viên rồi. Tuy nhiên, cần kiểm tra lại lời giải cho chắc chắn. Với các bài 1, 2, 4 thì không nói, nhưng các bài 3, 5, 6, đặc biệt là các bài tổ hợp thì rất dễ sai hoặc lý luận không chặt chẽ. Cũng tiếc cho bạn gì ở trên làm được 3, 5, 6 mà lại không làm được 2, 4. Có lẽ là làm mấy bài kia (nhất là bài 3) cũng mất hết thời gian rồi. Như mọi năm thì TST chấm cũng khá nhanh, quan trọng là kế hoạch chấm của Bộ thế nào thôi.

19-04-2010, 09:40 PM	#53
Mr Stoke +Thành Viên Danh Dự+ Tham gia ngày: Dec 2007 Bài gởi: 252 Thanks: 40 Thanked 455 Times in 95 Posts	Bài 6 nếu không dùng định lý Lucas có thể dùng đa thức đồng dư, nhưng vẫn phải bám vào cái khai triển 3-adic.

20-04-2010, 07:51 PM	#59
hieu_math +Thành Viên+ Tham gia ngày: Sep 2009 Bài gởi: 46 Thanks: 0 Thanked 7 Times in 7 Posts	hi lần này đúng là ko thấy có ai lớn tiếng chém gió nữa thật. Thưa thầy, thấy có tại liệu nào về tổ hợp ko? có thể gửi cho em được ko ạ? địa chỉ e-mail của em là [Only registered and activated users can see links. ]. Em cảm ơn thầy.