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
Toán Trung học Phổ thông và Thi Đại học →
Đại số →
Tổ hợp - Xác suất và thống kê - Số phức →
Chia $n$ kẹo cho $k$ người sao cho mỗi người nhận được ít nhất $l$ viên và nhiều nhất $h$ viênBắt đầu bởi Leonguyen, 01-05-2024 tổ hợp |
|
|||
|
Toán Trung học Cơ sở →
Đại số →
Tổ hợp gây lúBắt đầu bởi huucong, 30-04-2024 tổ hợp |
|
||
|
Toán Trung học Cơ sở →
Đại số →
Không biết sai ở đâuBắt đầu bởi huucong, 30-04-2024 tổ hợp |
|
||
Toán Trung học Phổ thông và Thi Đại học →
Đại số →
Tổ hợp - Xác suất và thống kê - Số phức →
Không biết sai ở đâu: Chọn ngẫu nhiên 5 hs từ đội văn nghệ sao cho lớp nào cũng có học sinh được chọn, hỏi có bao nhiêu cáchBắt đầu bởi huucong, 30-04-2024 tổ hợp |
|
|||
Toán thi Học sinh giỏi và Olympic →
Tổ hợp và rời rạc →
Có bao nhiêu cách viết số nguyên dương n thành tổng các số nguyên dương?Bắt đầu bởi Explorer, 24-04-2024 tổ hợp, đếm, nguyên dương và . |
|
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh