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 thi Học sinh giỏi và Olympic →
Số học →
$\sum_{n\vdots d,d=2k+1}\varphi (d)2^{\frac{n}{d}} \hspace{0.2cm} \vdots \hspace{0.2cm} n$Bắt đầu bởi hovutenha, 08-03-2024 tổ hợp, số học |
|
|||
Toán Trung học Cơ sở →
Toán rời rạc →
Con ếch và hạt nhânBắt đầu bởi HenryTung, 29-02-2024 xác suất, tổ hợp |
|
|||
|
Toán Trung học Phổ thông và Thi Đại học →
Hình học →
Hình học phẳng →
Hỏi có thể xây dựng mà mỗi phòng có đúng hai cửa hay không?Bắt đầu bởi Saturina, 16-02-2024 tổ hợp |
|
||
Toán Trung học Cơ sở →
Toán rời rạc →
Hỏi có thể xây dựng mà mỗi phòng có đúng hai cửa hay không?Bắt đầu bởi Saturina, 16-02-2024 tổ hợp |
|
|||
Solved
Toán Trung học Cơ sở →
Toán rời rạc →
Có 8 học sinh tham gia làm một bài kiểm tra trắc nghiệm. Sau khi kiểm tra, thấy rằng hai học sinh bất kì có chung nhiều nhất một câu trả lời.Bắt đầu bởi Saturina, 16-02-2024 tổ hợp |
|
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh