ĐEM MỖI SỐ NÀY CHIA CHO 6 TA NHẬN ĐƯỢC SỐ DƯ THUỘC TẬP {0,1, 2,3,...
6
.
Đem mỗi số này chia cho 6 ta nhận được số dư thuộc tập {0,1, 2,3, 4,5} .
Nếu tồn tại S i
i
( 1, 2,...,6) chia hết cho 6 thì bài toán đã được chứng minh.
Nếu không có S
inào chia hết cho 6 thì ta có 6 số chia hết cho 6 chỉ nhận 5 loại số dư
khác nhau (1, 2,3, 4,5) ; theo nguyên lý Dirichlet tồn tại hai số chia cho 6 có cùng số dư,
chẳng hạn S
2và S
5do đó hiệu của hai số này sẽ chia hết cho 6, tức là c d e chia hết
cho 6. Bài toán đã được chứng minh.
(Ở đây “thỏ” là các số S
i, “lồng” là số dư trong phép chia cho 6).
Nhận xét. Ta có thể phát biểu bài toán tổng quát sau:
Trang 10
Cho n số tự nhiên a a
1
, ,...,
2
a
n
. Chứng minh rằng tồn tại một số chia hết cho n hoặc tồn tại
một vài số có tổng chia hết cho n.
VÍ DỤ 4. Chứng minh rằng:
a) Trong n số tự nhiên liên tiếp luôn tìm được một số chia hết cho n.
b) Trong 39 số tự nhiên liên tiếp luôn tìm được một số mà tổng các chữ số của nó chia
hết cho 11.
Giải:
a) Giả sử không tìm được số nào trong n số tự nhiên liên tiếp đã cho mà chia hết cho n.
Khi đó n số này chia cho n chỉ nhận được nhiều nhất là n – 1 số dư khác nhau
(1, 2,3,..., n 1) , theo nguyên lí Dirichlet tồn tại hai số chia hết cho n có cùng số dư, chẳng
hạn là a và b với a b , khi đó a – b chia hết cho n, điều này mâu thuẫn với 0 a b n .
Từ đó suy ra điều phải chứng minh.
b) Lấy 20 số tự nhiên liên tiếp đầu của dãy, ta luôn tìm được một số có chữ số hàng đơn
vị là 0 và có chữ số hàng chục khác 9. Giả sử đó là N và tổng các chữ số của N là s. Khi
đó 11 số N N , 1, N 2, N 3,... N 9, N 19 sẽ nằm trong 39 số đã cho. Vì N tận cùng
bằng 0 nên tổng các chữ số của N N , 1, N 2,..., N 9 lần lượt bằng s s , 1, s 2,..., s 9 .
Vì N tận cùng bằng 0 và có chữ số hàng chục khác 9 nên tổng các chữ số của N + 10
bằng s + 1, tổng các chữ số của N + 19 bằng s + 10.
Trong 11 số tự nhiên liên tiếp s s , 1, s 2, s 3,..., s 9, s 10 luôn tìm được một số chia
hết cho 11. Chẳng hạn số đó là s i (0 i 10) : Nếu 0 i 9 thì ta chọn được số N i
thỏa mãn yêu cầu bài toán; nếu i = 10 thì ta chọn được số N + 19 thỏa mãn yêu cầu bài
toán.
Nhận xét. Mấu chốt để giải bài toán câu b) là phải tìm ra 11 số trong 39 số đã cho có
tổng các chữ số thứ tự là 11 số tự nhiên liên tiếp, đồng thời sử dụng kết quả câu a).
VÍ DỤ 5. Cho các số tự nhiên từ 1 đến 2012. Hỏi có thể chọn ra được nhiều nhất bao
nhiêu số sao cho tổng của hai số bất kì trong chúng không chia hết cho hiệu của nó?
Giải
Nhận thấy, nếu hai số chia cho 3 cùng dư 2 thì hiệu của chúng chia hết cho 3, còn tổng
của chúng chia cho 3 dư 1; nên tổng của chúng không chia hết cho hiệu của chúng.
Trong các số tự nhiên từ 1 đến 2012, sẽ có 671 số chia cho 3 dư 2 là các số có dạng
3 k 2 ( k 0,1, 2,..., 670) . Khi đó hai số bất kì trong 671 số này có tổng chia 3 dư 1, hiệu
chia hết cho 3, nên tổng không chia hết cho hiệu của chúng. Ta sẽ chứng minh rằng chọn
được nhiều nhất 672( 671 1) số trong các số từ 1 đến 2012, thì trong 672 số này luôn
tìm được a b a b , ( ) sao cho a b 2 (Thật vậy, giả sử ngược lại thì hiệu giữa số nhỏ
nhất và số lớn nhất trong các số đã chọn sẽ không nhỏ hơn 3.671 2013 . Điều này mâu
thuẫn giả thiết với hiệu giữa số lớn nhất và số nhỏ nhất không vượt quá 2012 1 2011 ),
nghĩa là a – b bằng 1 hoặc 2.
- Nếu a – b = 1 thì hiển nhiên a + b chia hết cho a – b (= 1)
Trang 11
- Nếu a – b = 2 thì a + b là số chẵn nên a + b chia hết cho a – b (= 2).
Như vậy từ 2012 số đã cho không thể chọn được hơn 671 số thỏa mãn điều kiện bài
toán. Suy ra số lượng lớn nhất các số phải tìm là 671.
Dạng 2. BÀI TOÁN VỀ TÍNH CHẤT CỦA CÁC PHẦN TỬ TRONG
TẬP HỢP
Thông thường ta phải lập ra những tập hợp có tính chất cần thiết rồi sử dụng nguyên lí
Dirichlet để chứng tỏ có hai phần tử thuộc hai tập hợp bằng nhau.
VÍ DỤ 6. Cho sáu số nguyên dương đôi một khác nhau và đều nhỏ hơn 10. Chứng minh
rằng luôn tìm được 3 số trong đó có một số bằng tổng hai số còn lại.
Gọi sáu số nguyên dương đã cho là a a a a a a
1
, , , , ,
2
3
4
5
6
với 0 a
1
a
2
... a
6
10 .
Đặt A { , , , , } a a a a a
2
3
4
5
6
gồm 5 phần tử có dạng a
mvới m {2,3, 4,5, 6} .
Đặt B { a
2
a a
1
,
3
a a
1
,
4
a a
1
,
5
a a
1
,
6
a
1
} gồm 5 phần tử có dạng a
n
a
1
với
{2,3, 4,5, 6}
n .
Ta thấy các phần tử của hai tập hợp A và B đều thuộc tập hợp gồm 9 phần tử {1, 2,3,...,9}
trong khi tổng số phần tử của hai tập hợp A và B là 5 5 10 .
Theo nguyên lí Dirichlet tồn tại hai số bằng nhau mà chúng không thể thuộc cùng một
tập hợp, nên có một số thuộc tập hợp A bằng một số thuộc tập hợp B, tức là a
m
a
n
a
1
,
do đó a
n
a
m
a
1
.
Ba số a a a
m
, ,
n
1
đôi một khác nhau. Thật vậy, a
m
a
n
vì nếu a
m
a
n
thì a
1
0 trái với giả
thiết của bài toán.
Vậy tồn tại ba số a a a
m
, ,
n
1
trong các số đã cho mà a
n
a
m
a
1
(đpcm).
(Ở đây, có 10 “thỏ” là 10 số a a a a a a
2
, , , , ,
3
4
5
6
2
a a
1
,
3
a a
1
,
4
a a
1
,
5
a a
1
,
6
a
1