Đến nội dung

Hình ảnh

CMR:Cả 1978 tập đều có một phần tử chung.

- - - - -

  • Please log in to reply
Chủ đề này có 1 trả lời

#1
QUANVU

QUANVU

    B&S-D

  • Hiệp sỹ
  • 4378 Bài viết
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.

Bài viết đã được chỉnh sửa nội dung bởi dark templar: 16-03-2013 - 12:33

1728

#2
salida

salida

    Binh nhất

  • Thành viên
  • 34 Bài viết
Đầ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




0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh