Nguyên lý Dirichlet

[rogp10]

1. Trong dãy số 1; 2; 3; 4; …; 199; 200 chọn ra k số bất kỳ. Tìm k bé nhất để luôn tồn tại một cặp bội số - ước số trong k số vừa chọn.
2. Trong các hợp số từ 4 đến 528, chọn 9 số bất kỳ. Chứng tỏ rằng trong 9 số luôn có 2 số không nguyên tố cùng nhau.

[noname00 (HK boy)]

Có 46 số nguyên tố không quá 200:

{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199}

Với k \le 46, luôn có khả năng xảy ra 1 trường hợp ta lấy đúng k số nguyên tố, dẫn đến không tồn tại 1 cặp bội số - ước số nào trong k số đã chọn.

to be continued…

[rogp10]

Còn 1 điều kiện nữa để không có cặp chia hết là chênh lệch không đủ lớn.

[rogp10]

Do 101; 102; …; 199; 200 không có cặp nào thỏa điều kiện (vì 101\cdot 2 > 200) nên k > 100.

Chứng minh k = 101 thỏa đề bài:
Mỗi số nguyên dương đều phân tích được ra dạng n = 2^k\cdot q trong đó q là số lẻ, k \in N. Ta phân tích 200 số rồi gom nhóm theo q. Hai số m, n cùng nhóm khi & chỉ khi \exists k \in Z, n = 2^k\cdot m. Có 100 số lẻ từ 1 đến 200 nên có 100 nhóm tương ứng. Nhưng 101 số trong 100 nhóm thì phải có ít nhất hai số cùng nhóm.

Vậy k_{min} = 101 \blacksquare

[rogp10]

2. Trong các hợp số từ 4 đến 528, chọn 9 số bất kỳ. Chứng tỏ rằng trong 9 số luôn có 2 số không nguyên tố cùng nhau.