Đề thi học sinh giỏi đồng bằng sông Cửu Long năm học 2008 – 2009 môn Toán - Bài 5

 SỞ GD – ĐT KIÊN GIANG	 KỲ THI HỌC SINH GIỎI ĐỒNG BẰNG SÔNG CỬU LONG
TRƯỜNG THPT CHUYÊN HUỲNH MẪN ĐẠT	 NĂM HỌC 2008 – 2009
ĐỀ THI ĐỀ NGHỊ MÔN : TOÁN
Thời gian : 180 phút
BÀI 5: TỔ HỢP-3Đ
Cho A là tập tất cả các phần tử với . Một chương trình máy tính chọn ngẫu nhiên 2008 phần tử từ tập A ( các phần tử khác nhau ) được một dãy . Tìm số tự nhiên n nhỏ nhất sao cho lấy bất kì n số hạng của dãy ta luơn tìm được 16 số hạng mà 2 số hạng bất kì trong 16 số hạng đĩ cĩ ít nhất là 2 thành phần khác nhau. 
Đáp án
Thang điểm
Trước hết ta chứng minh khơng là giá trị cần tìm.
Ta phân hoạch A thành các lớp rời nhau sao cho các phần tử trong mỗi tập hợp cĩ 5 thành phần cuối như nhau. 
Như vậy A được phân hoạch thành lớp mà mỗi lớp cĩ 4 phần tử.
0.25
0.25
Dãy cĩ 2008 số hạng, ta cĩ nên theo nguyên lý Dirichlet trong dãy cĩ 2 số hạng (khác nhau) cùng thuộc trong một lớp.
Ta cĩ nên theo nguyên lý Dirichlet trong 2006 số hạng cịn lại của dãy cĩ 2 số hạng (khác nhau) cùng thuộc trong một lớp. 
Thực hiện tương tự 15 lần mỗi lần ta thu được kết quả là 2 số hạng cùng thuộc trong một lớp ( ta cĩ thể thực hiện được vì ). Ta cĩ 30 số hạng khác nhau của dãy :. 
0.25
0.25
0.25
Lấy 16 phần tử bất kì trong các số hạng trên, theo nguyên lý Dirichlet cĩ ít nhất hai phần tử cùng chung một lớp, mà theo cách xây dựng các lớp, hai phần tử đĩ khơng thể cĩ quá 1 thành phần khác nhau. Vậy khơng là giá trị cần tìm.
0.5
Ta chứng minh 31 là số cần tìm.
Ta tiếp tục phân hoạch A thành 2 lớp rời nhau: .
 Thấy rằng mỗi lớp này đều cĩ số phần tử bằng nhau và bằng 2048 , hơn nữa trong mỗi lớp hai phần tử khác nhau đều cĩ ít nhất hai thành phần khác nhau. 
0.5
0.25
Theo nguyên lý Dirichlet, với 31 số hạng bất kì của dãy cĩ ít nhất 16 số hạng thuộc cùng một lớp. Ta thấy rằng hai số hạng bất kì trong số 16 số hạng này đều cĩ ít nhất là hai thành phần khác nhau.
Vậy là số cần tìm.
0.5