Chứng minh rằng trong 26 số nguyên khác nhau tùy ý nhỏ hơn 100 co thể chọn được hai số có ước chung lớn nhất khác 1
3 điểm hỏi đáp cho câu trả lời đúng
K
Khách
Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.
Những câu hỏi liên quan
13 tháng 5 2017
Phân hoạch \(100\) số tự nhiên đầu tiên thành các tập hợp sau:
\(A_1=\left\{1\right\}\)
\(A_2=\left\{2;4;6;8;...;100\right\}\)
\(A_3=\left\{3;9;15;...;99\right\}\)
\(A_5=\left\{5;25;35;55;...;95\right\}\)
Nghĩa là \(A_i\) với \(i\) nguyên tố chứa các bội của \(i\) mà không chia hết cho số nào nhỏ hơn \(i\) trừ số \(1\).
Giả sử có 27 số mà trong chúng không có ước chung lớn nhất khác 1.
Với mọi \(i\), trong mỗi \(A_i\) ta chỉ chọn được tối đa một số, vì nếu chọn 2 số thì chúng có ước chung là \(i\).
Có 25 số nguyên tố nhỏ hơn 100, tương ứng trong 25 \(A_i\) chỉ chọn được 25 số là tối đa.
Chọn thêm số 1 thì tối đa chọn được 26 số sao cho không có ước chung lớn nhất khác 1.
Nên nếu chọn 27 số thì trong chúng có ước chung lớn nhất khác 1.
M
24 tháng 8 2023
Để chứng minh rằng luôn chọn được từ mỗi nhóm một số sao cho hai số được chọn có ít nhất 1 chữ số giống nhau, ta sẽ sử dụng nguyên lý "Ngăn chặn trực tiếp" (Pigeonhole principle).
Giả sử chúng ta chia các số từ 1 đến n thành hai nhóm tùy ý, mỗi nhóm chứa một nửa số. Vì n lớn hơn hoặc bằng 19, chúng ta có ít nhất 10 số trong mỗi nhóm.
Xét các chữ số hàng đơn vị của các số từ 1 đến n. Chúng ta có 10 chữ số hàng đơn vị khác nhau từ 0 đến 9. Vì vậy, trong mỗi nhóm, chắc chắn sẽ có ít nhất một số có chữ số hàng đơn vị giống nhau.
Do đó, luôn chọn được từ mỗi nhóm một số sao cho hai số được chọn có ít nhất 1 chữ số giống nhau.
Tuy nhiên, bài toán không đúng với n = 18. Khi n = 18, chúng ta có thể chia các số từ 1 đến 18 thành hai nhóm sao cho mỗi nhóm không có số nào có chữ số hàng đơn vị giống nhau. Ví dụ: nhóm 1 chứa các số 1, 2, 3, 4, 5, 6, 7, 8, 9 và nhóm 2 chứa các số 10, 11, 12, 13, 14, 15, 16, 17, 18.
trong các số dưới 100, ta có 25 số nguyên tố
mà ở đây ta có 26 số.
=> Số số dôi ra là:
26-25=1
Theo nguyên lí Diricle=> có thể chọn được ít nhất hai số có ước chung lớn nhất khác 1=> điều phải chứng minh