Cho $100$ số tự nhiên lẻ nằm trên dãy $1;3;5;....;199$
Tìm số tự nhiên $k$ min sao cho khi chọn $k$ số tùy ý trong $100$ số đã cho thì bao giờ cũng chon được 2 số trong $k$ số đã chọn mà 1 trong 2 số dó là bội của số kia.
Tìm số tự nhiên $k$ min sao cho khi chọn $k$ số tùy ý trong $100$ số đã cho thì bao giờ cũng chon được 2 số trong $k$ số đã chọn mà 1 trong 2 số dó là
Bắt đầu bởi cvp, 21-12-2011 - 23:21
#1
Đã gửi 21-12-2011 - 23:21
#2
Đã gửi 22-12-2011 - 12:35
Ta chọn các số có dạng $3^{p_{i}}.a_{i}$ với ($p_{i}\geq 0$, $a_{i}$ lẻ và không chia hết cho 3 <1>)
Suy ra $199\geq a_{i}\geq 1$
Lại thấy từ <1>, ta có trong 100 số lẻ trên có 33 số chia hết cho 3 suy ra $a_{i}$ chỉ có thể nhận $100-33=67$ giá trị khác nhau.
Vậy nên nếu ta chọn $k$ bằng $68$ thì theo nguyên lý $dirichlet$ thì tồn tại $a_{j}=a_{k}$ do đó trong 2 số $3^{p_{j}}.a_{j};3^{p_{j}}.a_{j}$ có một số chia hết cho số kia
Vậy nên $k$ bé nhất là 68
Chú ý: Ta sẽ chỉ ra tập hợp có 67 số tự nhiên lẻ trong dãy trên mà không thỏa mãn và đó là tập các số lẻ $67,69,...,199$
Thật vậy nếu trong tập 67 số này có $a$ khác $b$ mà $a$ chia hết cho $b$ suy ra $a\geq 3b$ (do số lẻ nên chia cho nhau thì thương $\geq 3$)
Suy ra $199\geq a\geq 3b \geq 3.67=201$ vô lý.
Vậy $kmin= 68$
Suy ra $199\geq a_{i}\geq 1$
Lại thấy từ <1>, ta có trong 100 số lẻ trên có 33 số chia hết cho 3 suy ra $a_{i}$ chỉ có thể nhận $100-33=67$ giá trị khác nhau.
Vậy nên nếu ta chọn $k$ bằng $68$ thì theo nguyên lý $dirichlet$ thì tồn tại $a_{j}=a_{k}$ do đó trong 2 số $3^{p_{j}}.a_{j};3^{p_{j}}.a_{j}$ có một số chia hết cho số kia
Vậy nên $k$ bé nhất là 68
Chú ý: Ta sẽ chỉ ra tập hợp có 67 số tự nhiên lẻ trong dãy trên mà không thỏa mãn và đó là tập các số lẻ $67,69,...,199$
Thật vậy nếu trong tập 67 số này có $a$ khác $b$ mà $a$ chia hết cho $b$ suy ra $a\geq 3b$ (do số lẻ nên chia cho nhau thì thương $\geq 3$)
Suy ra $199\geq a\geq 3b \geq 3.67=201$ vô lý.
Vậy $kmin= 68$
Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 22-12-2011 - 13:41
- cvp và perfectstrong thích
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh