Đ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 tốn đã được chứng minh.
Nếu khơng cĩ S
i
nà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
2
và S
5
do đĩ 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
tố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 tốn tổng quát sau:
CH
UY
ÊN
Đ
Ề
SỐ
H
ỌC
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.
Bài tốn 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.
Hướng dẫn 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 tốn; nếu i = 10 thì ta chọn được số N + 19 thỏa mãn yêu cầu bài tốn.
Nhận xét. Mấu chốt để giải bài tố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).
Bài tốn 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ĩ?
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)
- 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 tốn.
Suy ra số lượng lớn nhất các số phải tìm là 671.
CH
IN
H
P
H
ỤC
K
Ỳ
TH
I H
ỌC
S
IN
H
GI
ỎI
C
ẤP
H
AI
Dạng 2: Bài tốn về tính chất các phần tử trong tập hợp
* Cở sở phương phá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ụ minh họa:
Bài tốn 1. 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
m
vớ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
=
a
+
a
.
1
n
m
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 tố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
và cĩ 9 “lồng”
là 9 số 1, 2, 3, 4, 5, 6, 7, 8, 9).
Nhận xét. Để giải bài tốn này, ta cần tạo ra hai tập hợp gồm các phần tử nhỏ hợn 10 và
tổng số phần tử của hai tập hợp phải khơng nhỏ hơn 10. Từ đĩ suy ra tồn tại hai phần tử
của hai tập hợp bằng nhau.
Bài tốn 2. Cho X là tập hợp gồm 700 số nguyên dương khác nhau, mỗi số khơng lớn hơn