Bài viết đã được chỉnh sửa nội dung bởi dark templar: 16-03-2013 - 12:33
CMR:Cả 1978 tập đều có một phần tử chung.
Bắt đầu bởi QUANVU, 18-03-2005 - 20:10
#1
Đã gửi 18-03-2005 - 20:10
Cho 1978 tập ,mỗi tập có 40 phần tử.Hai tập bất kì đều có đúng một phần tử chung.CMR:Cả 1978 tập đều có một phần tử chung.
1728
#2
Đã gửi 20-03-2005 - 04:08
Đầu tiên ta nhận xét là có ít nhất 41 tập hợp có cùng chung 1 phần tử. Thật vậy, xét 1 tập hợp bất kỳ: A có 40 phần tử (a_1,a_2,... a_40)
1977 tập hợp còn lại có x_1 tập chứa a1, x_2 tập chứa a_2,... x_40 tập chứa a_40
--> x_1+...+x_40 = 1977 (không thể có 2 tập nào cùng chứa a_i,a_j vì nếu không thì tập đó có 2 phần tử chung với A)
--> có ít nhất một x_k >= 1977/40 >=49 (cũng không cần lớn quá vậy)
Gọi 41 tập đó là A_1,...,A_41 có chung phần tử a
Xét 1 tập B bất kỳ khác. Giả sử B không chứa a.
--> B có 1 phần tử chung với A_1 là b_1 (b_1)
--> B có 1 phần tử chung với A_1 là b_2 (b_1 khác b_2 nếu không A_1 và A_2 có 2 phần tử chung là a và b_1 = b_2)
...
--> B có 1 phần từ chung với A_40 là b_40 (b_1.....b_40 khác nhau)
--> B có 1 phần tử chung với A_41 là 1 trong các số b_i --> vô lý
--> B phải chứa a
--> các tập còn lại cũng tương tự
--> đpcm
1977 tập hợp còn lại có x_1 tập chứa a1, x_2 tập chứa a_2,... x_40 tập chứa a_40
--> x_1+...+x_40 = 1977 (không thể có 2 tập nào cùng chứa a_i,a_j vì nếu không thì tập đó có 2 phần tử chung với A)
--> có ít nhất một x_k >= 1977/40 >=49 (cũng không cần lớn quá vậy)
Gọi 41 tập đó là A_1,...,A_41 có chung phần tử a
Xét 1 tập B bất kỳ khác. Giả sử B không chứa a.
--> B có 1 phần tử chung với A_1 là b_1 (b_1)
--> B có 1 phần tử chung với A_1 là b_2 (b_1 khác b_2 nếu không A_1 và A_2 có 2 phần tử chung là a và b_1 = b_2)
...
--> B có 1 phần từ chung với A_40 là b_40 (b_1.....b_40 khác nhau)
--> B có 1 phần tử chung với A_41 là 1 trong các số b_i --> vô lý
--> B phải chứa a
--> các tập còn lại cũng tương tự
--> đpcm
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh