Đến nội dung

Hình ảnh

Cho S={1;2;3;...;2009}, A là tập con của S

- - - - - tổ hợp

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

#1
JeongHyeon

JeongHyeon

    Binh nhì

  • Thành viên mới
  • 11 Bài viết

Cho S={1;2;3;...;2009}, A là tập con của S, A có n phần tử. Tìm n nhỏ nhất sao cho với mọi cách chọn trong tập A thì trong A luôn có hai số a,b mà a=3b



#2
Arthur Pendragon

Arthur Pendragon

    Trung sĩ

  • Thành viên
  • 134 Bài viết

Mình nghĩ như này không biết đúng không:

Chia tập S thành 2 tập con: B gồm các phần tử thuộc S và chia hết cho 3 (có 669 phần tử); C là phần bù của B trong S, có 1340 phần tử. 

Nếu n nhỏ hơn hoặc bằng 1340 thì ta có thể chọn tập A là tập con của C, khi đó không tồn tại hai số a và b sao cho a=3b, do tất cả các phần tử trong C đều không chia hết cho 3.

Nếu n lớn hơn 1340 thì ta phải lấy ít nhất 1 phần tử thuộc tập B, gọi là b, khi đó b=3a với $1\leq a\leq 669$, $a \in \mathbb{N}$. Xảy ra 2 khả năng:

+) Nếu a thuộc C thì lấy thêm a vào tập A

+) Nếu a thuộc B thì tập A đã thỏa mãn yêu cầu bài toán.

Tóm lại, n nhỏ nhất là bằng 1342


Bài viết đã được chỉnh sửa nội dung bởi Arthur Pendragon: 23-09-2018 - 22:46

"WHEN YOU HAVE ELIMINATED THE IMPOSSIBLE, WHATEVER REMAINS, HOWEVER IMPROBABLE, MUST BE THE TRUTH"

-SHERLOCK HOLMES-             






Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: tổ hợp

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

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