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
#1
Đã gửi 23-09-2018 - 08:39
#2
Đã gửi 23-09-2018 - 22:34
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
- Hr MiSu và JeongHyeon thích
"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