APMO 2008, chứng minh tồn tại tập thoả mãn.

**psquang_pbc** · 06-04-2008, 12:55 AM

Students in a class form groups each of which contains exactly three members such that any two distinct groups have at most one member in common. Prove that, when the class size is 46, there is a set of 10 students in which no group is properly contained.

Dungcvp · 09-04-2008, 07:32 PM

Xét tập $S $ là tập gồm các học sinh mà bất cứ 3 học sinh nào của $S $ ko nằm trong một nhóm.Ta sẽ chứng minh $|S|\geq $ 10 .ta cm điều này bằng phép phản chứng.giả sử $|S| \leq $9.Với 2 học sinh bất kì trong $S $ tồn tại một học sinh ko $ \in S $ thuộc cùng một nhóm.
Số cách chọn 2 học sinh từ $S $ là $C_9^{2} $=36
mặt khác số học sinh ko nằm trong $S $ lớn hơn hoặc bằng 46-9=37
Suy ra tồn tại một học sinh ko nằm trong $S $và Từ đó suy ra tập $S $có thể mở rộng bằng cách thêm học sinh đó.(vô lí).Ta có ĐPCM

06-04-2008, 12:55 AM	#1
psquang_pbc +Thành Viên Danh Dự+ Tham gia ngày: Nov 2007 Bài gởi: 747 Thanks: 9 Thanked 111 Times in 72 Posts	APMO 2008, chứng minh tồn tại tập thoả mãn. Students in a class form groups each of which contains exactly three members such that any two distinct groups have at most one member in common. Prove that, when the class size is 46, there is a set of 10 students in which no group is properly contained. __________________ [Only registered and activated users can see links. ] No pain, no gain!

09-04-2008, 07:32 PM	#2
Dungcvp +Thành Viên+ Tham gia ngày: Jan 2008 Bài gởi: 16 Thanks: 0 Thanked 0 Times in 0 Posts	Xét tập $S $ là tập gồm các học sinh mà bất cứ 3 học sinh nào của $S $ ko nằm trong một nhóm.Ta sẽ chứng minh $\|S\|\geq $ 10 .ta cm điều này bằng phép phản chứng.giả sử $\|S\| \leq $9.Với 2 học sinh bất kì trong $S $ tồn tại một học sinh ko $ \in S $ thuộc cùng một nhóm. Số cách chọn 2 học sinh từ $S $ là $C_9^{2} $=36 mặt khác số học sinh ko nằm trong $S $ lớn hơn hoặc bằng 46-9=37 Suy ra tồn tại một học sinh ko nằm trong $S $và Từ đó suy ra tập $S $có thể mở rộng bằng cách thêm học sinh đó.(vô lí).Ta có ĐPCM thay đổi nội dung bởi: Dungcvp, 10-04-2008 lúc 07:07 PM