Chọn tuỳ ý $m$ số trong các số nguyên lẻ từ 1 đến 1001. Tìm giá trị nhỏ nhất của $m$ để

Câu hỏi số 851277:

Vận dụng

Chọn tuỳ ý $m$ số trong các số nguyên lẻ từ 1 đến 1001. Tìm giá trị nhỏ nhất của $m$ để đảm bảo rằng có ít nhất một cặp số trong $m$ số được chọn mà một trong hai số đó chia hết cho số còn lại.

Quảng cáo

Xem lời giải

Câu hỏi:851277

Phương pháp giải

Tìm tập X gồm các số các số chia hết cho 3.

Viết các phần tử thuộc X dưới dạng $3^{s}.t$ trong đó $t$ lẻ và $t$ không chia hết cho 3 . Tìm các giá trị của t

Chứng minh $m = 335$ bằng nguyên lý Dirichlet

Giải chi tiết

Ta giả sử tập gồm các số nguyên dương lẻ từ 1 đến 1001 là $X = \left\{ {1;3;5;\ldots;1001} \right\}$.

Tập $X$ có 501 số lẻ, trong đó số các số chia hết cho 3 là: $\dfrac{999 - 3}{6} + 1 = 167$.

Viết các số đã cho dưới dạng $3^{s}.t$ trong đó $t$ lẻ và $t$ không chia hết cho 3 .

Vậy số các giá trị khác nhau có thể của $t$ là $501 - 167 = 334$.

Ta xét tập $A = \left\{ {335;336;\ldots;1001} \right\}$ có 334 phần tử

Ta thấy với $a < b$ bất kì thuộc A thì $3a \geq 3.335 > 1001 \geq b$.

Suy ra $3a > b > a$, tức là $b$ không thể là bội của $a$.

Do đó các phần tử trong A đôi một không chia hết cho nhau.

Như vậy $m \geq 335$.

Ta chứng minh $m = 335$ thoả mãn.

Thật vậy, nếu lấy 335 số thì theo nguyên lý Dirichlet thì tồn tại 2 số $x,y$ sao cho biểu diễn dưới dạng $3^{s}t$ thì hai số cùng nhận cùng giá trị $t$, tức là $x = 3^{s_{1}}t,y = 3^{s_{2}}t,\left( {s_{1} > s_{2}} \right)$.

Hai số này thỏa mãn đề bài.

Vậy $m$ nhỏ nhất là 335.

PH/HS 2K10 THAM GIA NHÓM ĐỂ CẬP NHẬT ĐIỂM THI, ĐIỂM CHUẨN MIỄN PHÍ!

Câu hỏi trước Câu tiếp theo

>> Học trực tuyến lớp 9 và Lộ trình UP10 trên Tuyensinh247.com Đầy đủ khoá học các bộ sách: Kết nối tri thức với cuộc sống; Chân trời sáng tạo; Cánh diều. Lộ trình học tập 3 giai đoạn: Học nền tảng lớp 9, Ôn thi vào lớp 10, Luyện Đề. Bứt phá điểm lớp 9, thi vào lớp 10 kết quả cao. Hoàn trả học phí nếu học không hiệu quả. PH/HS tham khảo chi tiết khoá học tại: Link