Phương pháp giải Toán 6 bằng nguyên lí Dirichlet

Phương pháp giải Toán 6 bằng nguyên lí Dirichlet. Tài liệu được biên soạn dưới dạng file PDF bao gồm 20 trang tổng hợp các kiến thức tổng hợp giúp các bạn tham khảo, ôn tập và đạt kết quả cao trong kỳ thi sắp tới. Mời các bạn đón xem!

Trang 1
S6-CHUYÊN ĐỀ 8. NGUYÊN LÍ DIRICHLET
PHN I. TÓM TT LÝ THUYT
1. Ni dung nguyên lí
Nếu nht
.n m r+
(trong đó
, , *m n r Î ¥
) con th vào
n
cái chung thì phi có ít nht mt chung
chứa không ít hơn
1m +
con th.
Chng minh
Gi s ngược li mi chung cha không quá
m
con th thì tng s th nht trong
n
chung s không
quá
.mn
con th :Mâu thun vi gi thiết là s th bng
.Vy phi có ít nht mt chung cha
không ít hơn
1m +
con th.
2. Nhn xét
Bản thân nguyên li Dirichlet khá đơn giản và d hiu, tuy nhiên vic ng dng nguyên lí này li không h
đơn giản .Vấn đề đây là phát hiện rachất Dirichlet “ trong các bài toán , dng toán của nh và sau đó
xác định trong đó đâu là chuồng và đâu là thỏ.Có những trưng hp chung và th gần như đã có sẵn,
nhưng có những trưng hp chúng ta phải “xây chung , to thỏ”.
PHN II.CÁC DNG BÀI
Dng 1: Toán chia hết
Khi chia s
a
cho s
0m ¹
luôn có
m
kh năng về s dư là 0,1,….,
1m -
(“m chuồng “).Do vậy, khi
chia
1m +
s khác nhau
1 2 1
, ,.....,
m
a a a cho m
+
ta s
1m +
s dư (“
1m +
thỏ”) và do đó luôn
có hai phép chia có cùng s dư.Giả s hai s b chia trong hai phép chia đó là
i
a
j
a
(vi
11j i m£ < £ +
). Ta (
)
ij
a a m- M
.
Bài 1:
Chng minh rng có th tìm được mt s dng
19781978.....197800...0
chia hết cho 2012.
Li gii
Xét dãy s :
2013 1978
1978,19781978,.....,19781978...1978
so
144444424444443
. Khi chia các s hng ca dãy này cho 2012 s
hai phép chia có cùng s dư. Giả s hai s hng của dãy trong hai phép chia đó
1978
19781978...1978
m so
a =
14444442 4444443
1978
19781978...1978
n so
b =
14444442 4444443
( vi
1 2013)nm£ < £
.
Hiu ca
a
b
chia hết cho 2012 hay
{
1978 4 0
19781978....1978 00...0 2012
m n so n so
ab
-
-= M
144444442 44444443
(đpcm)
Trang 2
Nhn xét: Phương pháp để gii dng toán này là to ra dãy s (theo cu to s) t yêu cu ca bài toán
(“to thỏ”) . Sau đó áp dụng nguyên lí Dirichlet cho các s hng ca dãy s mi (mi s hng thay cho
một “thỏ”, 2012 là số “chuồng”).
Bài 2:
Cho dãy
m
s t nhiên bt kì
12
, ,....,
m
a a a
. Chng minh rng tn ti mt s hng chia hết cho
m
hoc
tng ca mt s hng liên tiếp trong dãy chia hết cho
( *)mmÎ ¥
.
Li gii
Xét dãy s
1 1 2 1 2 1 2
, ,......., ....
mm
b a b a a b a a a= = + = + + +
Khi chia các s hng ca dãy này cho
m
thì xy ra một trong hai trường hp sau :
Có mt phép chia hết , chng hn :
k
bmM
, thì ta có điều phi chng minh :
12
( .... )
k
a a a m+ + + M
Không phép chia hết nào .Khi đó tồn ti hai phép chia có cùng s , chẳng hn
,
ij
bb
chia cho
m
( vơi
1 j i m£ < £
)
12
( ) ( .... )
++
+ + +
i j j j i
b b m hay a a a m
, ta có điều phi chng minh .
Nhn xét: Phương pháp “tạo th trong ví d này là da vào phép toán cng và yêu cu v tính liên tiếp
ca các s hạng trong dãy ban đầu của đề bài .
Bài 3:
Cho bn s t nhiên phân bit
a b c d> > >
. Chng minh rng:
( )( )( )( )( )( ) 12P a b a c a d b c b d c d= - - - - - - M
Li gii
Chia bn s phân bit
, , ,a b c d
cho 3 luôn có hai phép chia có cùng s
hiu hai s b chia đó chia hết cho 3 tn ti hiu hai s trong bn s
, , ,a b c d
chia hết cho 3. Do vy
P chia hết cho 3 (1)
Trong bn s
, , ,a b c d
nếu hai s có cùng s khi chia cho 4 thì P chia hết cho 4;trái li , khi chia
bn s đó cho 4 có đủ bốn trưng hp v s dư là 0,1,2,3 trong bn s
, , ,a b c d
hai s chn , hai s
l, gi s
,ac
chn
,bd
l
( ) 2ac- M
( ) 2bd- M
Do vy P chia hết cho 4 (2)
T (1),(2) và (3,4)=1 suy ra
3,4 12P hay PMM
(đpcm)
Bài 3:
Chng minh rng trong 19 s t nhiên liên tiếp bất kì ta luôn tìm được mt s có tng các ch s chia hết
cho 10.
Trang 3
Li gii
Trong 19 s t nhiên liên tiếp luôn tn ti 10 s t nhiên liên tiếp có ch s hàng chc ging nhau ,
hiu ch s hàng chục đó
a
(các ch s hàng trăm, hàng nghìn, ….(nếu có ) cũng giống nhau), còn các
ch s hàng đơn vị dãy 0;1;2;3;…;9.
Do đó tổng các ch s ca mi s cũng là một dãy 10 s t nhiên liên tiếp, vì thế tn ti s tng các
ch s chia hết cho 10.
Bài 4:
Cho 12 s t nhiên khác nhau có hai ch s. Chng minh rng không tn ti hai shiu là mt s
hai ch s như nhau.
Li gii
12 s t nhiên khác nhau, mà ch 11 s trong phép chia cho 11, do đó tồn ti hai s có cùng s
dư trong phép chia cho 11. Hiệu ca chúng là mt s chia hết cho 11, đó số có hai ch s như nhau.
Bài 5:
Chng minh rng trong 11 s t nhiên bt kì bao gi cũng tồn ti ít nht 2 s có hiu chia hết cho 10.
Li gii
Vi 11 s t nhiên khi chia cho 10 ta được 11 s dư, một s t nhiên bt kì khi chia cho 10 có 10 kh
năng dư là 0 ; 1 ; 2 ; 3 ; ... ; 9.
Vì có 11 s mà chỉ 10 kh năng dư, theo nguyên lí Đi-rích-lê, tn ti ít nht 2 s khi chia cho 10 có
cùng s do đó hiệu ca chúng chia hết cho 10 (đpcm).
Bài 6:
Chng minh rng tn ti sdng 19941994...199400...0 chia hết cho 1995.
Li gii
Ta có 19941994...199400...0 = 19941994...1994
100...0
Xét 1995 s dng: 1994 ; 19941994 ; ... ; .
+) Nếu mt trong các s trên chia hết cho 1995 thì d dàng có điều phi chng minh.
+) Nếu các s trên đều không chia hết cho 1995 thì khi chia tng s cho 1995 s ch có 1994 kh năng dư
là 1 ; 2 ; 3 ; ... ; 1994.
Vì có 1995 s dư mà chỉ 1994 kh năng dư, theo nguyên Đi-rích-lê tn ti ít nht 2 s khi chia cho
1995 có cùng s dư, hiệu ca chúng chia hết cho 1995.
Khi đó 1994...199400...0 chia hết cho 1995 (đpcm).
Bài 7:
Chng minh rng tn ti s t nhiên k sao cho (1999^k - 1) chia hết cho104.
Li gii
Xét 104 s có dng: 1999^1 ; 1999^2 ; ... ; 1999^104.
Trang 4
Ly tt c các s trên chia cho 104 s ch có 103 kh năng dư là 1 ; 2 ; 3 ; ...; 103 (ch : s không có s
dư 0 vì 1999 và 104 là hai s nguyên t cng nhau nên 1999 mũ bao nhiêu cũng không chia hết cho 104)
Mà dãy s trên có 104 s nên s có ít nht hai s khi chia cho 104 có cng s dư.
Gi hai s có cng s dư khi chia cho 104 là 1999^a và 1999^b (vi a > b)
Ta có: 1999^a - 1999^b 104 => 1999^b[1999^(a-b) 1] 104
Mà UCLN(1999^b, 104) là 1 (vì là hai s nguyên t cng nhau) nên 1999^(a-b) 1 104
Đặt k = a b, ta có 1999^k 1 104 (đpcm)
Bài 8:
Chng minh rng tn ti mt s ch viết bi hai ch s chia hết cho 2003.
Li gii
Xét 2003 s dng 1 ; 11 ; 111 ; ... ;
+) Nếu có mt s chia hết cho 2003 thì ta được sô 11...1100..00 2003 (đpcm)
+) Nếu không có mt s nào chia hêt cho 2003 thì s có 2002 kh năng 1 ; 2 ; 3 ; ...; 2002.
Mà dãy s trên có 2003 s hng nên s có ít nht hai s khi chia cho 2003 có cng s
Gi hai s có cng s dư khi chia cho 2003 là
m chu so1
11...11
và
n chu so1
111...111
(vi n > m)
Khi đó
n chu so1
111...111
-
m chu so1
11...11
=
n m chu so 0
11...110...00000
2003 (đpcm).
Dng 2: Toán suy lun
Bài 1:
10 đội bóng thi đấu vi nhau vòng tròn một lượt , mỗi đội phải đấu đng một trn vi mỗi đội khác
.Chng minh rng vào bt c lc nào cũng có hai đội đã đấu s trận như nhau.
Li gii
ràng nếu trong 10 đội bóng có 1 đội chưa đấu mt trận nào thì trong các đi còn lại không có đội nào
đã thi đấu 9 trận . N vậy mỗi đội chs trận đấu hoc t 0 đến 8 hoc t 1 đến 9 .Vy theo nguyên
Dirichlet phi có ít nhất hai đội có s trận đã đấu như nhau.
Bài 2:
Trong 45 hc sinh làm bài kim tra không ai b điểm dưới 2 và ch 2 hc sinh được điểm 10 .Chng
minh rng ít nhất cũng tìm được 6 hc sinh có điểm kim tra bằng nhau ( điểm kim tra là mt s t nhiên
t 0 đến 10).
Li gii
S hc sinhđiểm kim tra t 2 đến 9 là : 45 2 =43
Ta có : 43 = 8.5 + 3
Trang 5
Như vậy , khi phân chia 43 hc sinh vào 8 loại điểm kim tra ( t 2 đến 9 ) thì theo nguyên lí Dirichlet
luôn tn ti ít nht 5 + 1 = 6 hc sinh có điểm kim tra giống nhau (đpcm)
Bài 3:
17 nhà Toán hc viết thư cho nhau trao đổi v 3 vấn đề khoa hc , mỗi người đều trao đổi với 16 người
còn li và mi cặp 2 người ch trao đổi vi nhau mt vấn đề .Chng minh rng có ít nht 3 nhà Toán hc
trao đổi vi nhau v cùng mt vấn đề.
Li gii
Gi A là mt nhà Toán hc nào đó trong 17 nhà Toán hc thì A phải trao đi với 16 người còn li v 3
vấn đề khoa hc ( kí hiu là vấn đề I,II,III).
Vì 16 = 3.5 + 1 nên A phải trao đổi vi ít nht 5 + 1 = 6 nhà Toán hc khác v cùng mt vấn đề ( theo
nguyên lí Dirichlet) .
Gi 6 nhà Toán hc cng trao đi vi A v mt vấn đề (chng hn là vấn đề 1) là
1 2 6
, ,.....,A A A
.Ta thy
6 nhà Toán hc này lại trao đổi vi nhau v 3 vấn đề nên có hai kh năng xy ra:
1) Nếu có 2 nhà Toán hc nào đó cng trao đổi vi nhau v vấn đề I thì cùng vi A s có 3 nhà Toán hc
cng trao đổi v vấn đề I.
2) Nếu không có 2 nhà Toán hc nào cng trao đổi vi nhau v vấn đề I , thì 6 nhà Toán hc này ch trao
đổi vi nhau v 2 vấn đề II và III.Theo nguyên lí Dirichlet , ít nht 3 nhà Toán hc cng trao đổi vi
nhau v mt vấn đề ( II hoc III).
Vy luônít nht 3 nhà Toán hc trao đổi vi nhau v cùng mt vấn đề .
Nhn xét: Trong ví d trên ta đã phải phân chia bài toán thành hai lp và s dng hai ln nguyên
Dirichlet : Ln th nht vi 16 th3 chung ; ln th hai vi 6 th và 2 chung.
Bài 4:
Chng minh rng tn ti mt s t nhiên gm toàn ch s 1 chia hết cho 2013.
Li gii
Xét 2014 có dạng 1,11,111,.,
{
2014 1
11...1
. Theo nguyên lý Dirichlet thì tn ti hai scùng s khi chia
cho 2013. Gi s hai s đó
{
1
11...1
n
a =
,
{
1
11...1
k
b =
vi n>k.
Khi đó
{
1
11...1.10 2013
k
n k
ab
-
-= M
.
(2007,10 ) 1
k
=
nên s
{
1
11...1
n k
c
-
=
chia hết cho 2013
Bài 5:
Cho 5 s t nhiên phân bit
1 2 3 4 5
a a a a a> > > >
. Xét tích
Trang 6
1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
( )( )( )( )( )( )( )( )( )( )P a a a a a a a a a a a a a a a a a a a a= - - - - - - - - - -
Chng minh rng
228P M
Li gii
Ta có
25
288 3 .2=
1. Chng minh
2
3P M
Xét 4 s
1 2 3 4
, , , ,a a a a
: Ta thy tn ti hai s có cùng s dư khi chia cho 3, giả s
1
a
2
a
=>
12
( ) 3aa- M
Li xét
2 3 4 5
, , ,a a a a
trong 4 s này li tn ti 2 s cùng s dư khi chia cho 3, giả s
4
a
5
a
=>
45
( ) 3aa- M
Do vy
9P M
(1)
2. Chng minh
5
2P M
Trong 5 s đã cho có 3 số cùng nh chn l.
Nếu 3 s chn, 2 s l, chng hn là :
,
22
2ak=
,
33
2ak=
,
44
21ak=+
,
55
21ak=+
Khi đó:
1 2 1 3 2 3 4 5
16( )( )( )( ).P k k k k k k k k M= - - - -
Trong đó 3 số
1 2 3
,,k k k
2 s cùng nh chn l, chng hn
1
k
2
k
, thì
12
( ) 2kk- M
. Vy
32P M
Nếu 3 s l, 2 s chn thì chứng minh tương tự ta cũng có
32P M
Vy trong mi trưng hợp ta đều có
32P M
(2)
T (1), (2) và (9,32)=1 suy ra
9,32P M
hay
288P M
(đpcm).
Bài 6:
Chng minh rng trong
1n +
s bt kì thuc tp hp
{ }
1;2;3;....;2n
luôn tìm được hai s s này là
bi ca s kia.
Li gii
Viết n+1 s lấy ra dưới dng
1
12
1 1 2 2 1 1
2 , 2 ,...., 2
n
k
kk
nn
a b a b a b
+
++
= = =
trong đó
1 2 1
, ,....,
n
b b b
+
là các s l,
Ta có:
1 2 1
1 , ,...., 2 1.
n
b b b n
+
£ £ -
. Mt khác trong khong t 1 đến 2n-1 có đng n số l nên tn ti hai
s m, n sao cho
nm
bb=
. Khi đó, trong hai số
n
a
m
a
mt s là bi ca s kia (đpcm)
Bài 7:
Xét 100 s t nhiên
1 2 100
0 , ,...., 100a a a
tng bng 200 .Chng minh rng trong 100 s đó
luôn tn ti mt vài stng bng 100.
Trang 7
Li gii
1. Nếu
1 2 100
... 2a a a= = = =
thì ta chn 50 s bất kì đều có tng bng 100.
2. Nếu
12
aa¹
thì ta lp dãy sau
1 2 1 2 1 2 3 1 2 99
, , , ... ...a a a a a a a a a a+ + + + + + + +
( các s hng này có giá tr t 1 đến 199).
- Nếu tn ti mt s hang nào trong dãy chia hết cho 100 thì s hạng đó bằng 100
- Nếu không có s hng nào chia hết cho 100 thì trong 100 s này khi chia cho 100 s có hai s hng
cùng s . Hiệu ca chúng cho ta tng cn tìm.
Bài 8:
Cho 69 s t nhiên khác 0 phân biệt và không vượt quá 100 .Chng minh rng có th chnđược 4 s trong
69 s đó thỏa mãn tng ca ba s bng s còn li
Li gii
Gi s 69 s đã cho
1 3 1 4 1 69
1 ... 100a a a a a a£ + < + < < + £
. Khi đó
1
32a £
. Xét hai dãy
sau:
1 3 1 3 1 69
1 ... 132(1)a a a a a a< + < + < < + £
3 2 4 2 69 2
1 ... 132(2)a a a a a a£ - < - < < - £
T (1) và (2) ta có 134 s hng có giá tr t 1 đến 132, suy ra có 2 s bng nhau mi s thuc mt dãy,
chng hn:
12mn
a a a a+ = -
(vi
3 69)mn£ < £
tc là ta tìm được 4 s
12
; ; ;
nm
a a a a
vi
12m
a a a<<
12mn
a a a a+ + =
(đpcm)
Bài 9:
Chng minh rng trong 39 s t nhiên liên tiếp bt kì luôn có ít nht mt s có tng cácch s chia hết
cho 11.
Li gii
Gi s 39 s t nhiên liên tiếp đó
1 2 39
...a a a< < <
.
Trong 20 s hạng đầu tiên ca dãy này s có hai s tn cùng là 0 mt s (trong hai s này) ch s
đứng trưc s tn cùng khác 9. Gi s này là N.
Xét các s
1, 2,..., 19N N N+ + +
thuc 39 s đã cho. Khi đó:
( ) ( )S N i S N i+ = +
vi
1,2,...,9i =
( 19) ( ) 10S N S N+ = +
.
(kí hiu S(a) là tng các ch s ca a).
Trong 11 s t nhiên liên tiếp
( ), ( ) 1,..., ( ) 9, ( ) 10S N S N S N S N+ + +
luôn có mt s chia hết cho
11, chng hn:
( ) 11S N m+ M
vi
{ }
1;2;...;9;19m Î
Vy
Nm+
là s tha mãn.
Trang 8
Bài 10:
Cho 15 s t nhiên phân bit, khác 0, không lớn hơn 28. Chứng minh rng trong 15 s đó luôn tìm được ít
nht mt b 3 s mà s này bng tng ca hai s còn li hoc mt cp 2 s mà s này gấp đôi số kia.
Li gii
Gi 15 s t nhiên sp xếp theo th t t nh đến ln là :
1 2 15
, ,...,a a a
.
Xét dãy s:
1 2 1 2 3 1 14 15 1
, ,...,b a a b a a b a a= - = - = -
. Các s hng ca dãy s này giá tr t 1 đến
27 và đôi một khác nhau.
Þ
Dãy s
1 2 15 1 2 14
, ,..., ; , ,...,a a a b b b
có 29 s hạng nhưng chỉ nhn 28 giá tr khác nhau (t 1 đến 28).
Theo nguyên lí Dirichlet, tn ti hai s bng nhau, chng hn:
(1 14,1 15)
mn
b a m n= £ £ £ £
Hay
1 1 1 1m n m n
a a a a a a
++
- = Û = +
.
- Nếu n = 1 thì
11
2
m
aa
+
=
- Nếu
1n ¹
thì 3 s
11
,,
nm
a a a
+
phân bit
11mn
a a a
+
=+
.
Vy ta ch vic chn 3 s
11
,,
nm
a a a
+
hoc 2 s
11
,
m
aa
+
s tha mãn yêu cầu đề bài.
Bài 11:
Chn 5 người bt kì. Chng minh rng có ít nhất 2 người có cùng s người quen trong 5 người đó.
Li gii
Mỗi người trong s 5 người kh năng về s ngưi quen (t 0 đến 4). Ta xét hai trưng hp sau:
1. Nếumột người không quen ai trong s 4 ngưi còn li thì rõ ràng không có ai quen c 4 người. Như
vậy, 5 người mà ch 4 kh năng về s người quen (t 0 đến 3) nên theo nguyên Dirichletít nht
hai ngườicùng s người quen.
2. Nếu mỗi người đều có ít nht một người quen. Khi đó 5 người mà ch có 4 kh năng về s người quen
(t 1 đến 4), theo nguyên lí Dirichlet có ít nhất hai người có cùng s người quen
Bài 12:
6 đội bóng thi đấu vi nhau vòng tròn một lượt, mỗi đội đấu đng một trn vi mỗi đội khác. Chng
minh rng vào bt c thời điểm nào cũng có ba đội trong đó từng cặp đã đấu vi nhau hoặc chưa đấu vi
nhau trn nào.
Li gii
Gi s 6 đội bóng đá là A, B, C, D, E, F. Xét đội A, Vì A phải đấu t 0 đến 5 trn nên theo nguyên
Dirichlet ta suy ra. Hoặc A đã đấu hoặc A chưa đấu vi ít nhất 3 đội khác. Không mt tính tng quát, gi
s A đã đấu vi B, C, D
- Nếu B, C, D tng cặp chưa đấu với nhau thì bài toán được chng minh.
- Nếu B, C, D có 2 đội đã đấu vi nhau, ví d là C thì 3 đội A, B, C tng cp đã đấu vi nhau
Trang 9
Như vậy bt c lc nào cũng có 3 đội trong đó từng cặp đã đấu vi nhau hoặc chưa đấu vi nhau trn nào.
Bài 13:
Một đồi thông có
800 000
cây thông. Trên mi cây thông có không quá
500 000
chiếc lá. Chng minh
rng ít nhất cũng 2 cây thông có cng số lá như nhau ở trên cây.
Li gii
Ta hãy tưởng tượng mi cây thông là mt "thỏ", như vậy có 800.000 "thỏ" được nht vào không quá
500.000 "chiếc lng". Lng 1 ng vi cây thông có 1 chiếc lá trên cây, lng 2 ng vi cây thông có 2
chiếc lá trên cây v.v... S th lớn hơn số lng, theo nguyên tắc Điriclê ít nhất có 1 lng nhốt không ít hơn
2 th nghĩa là có ít nhất 2 cây thôngcùng s.
Bài 14:
Mt lp hc có 40 hc sinh. Chng minh rng có ít nht 4 hc sinh có tháng sinh ging nhau
Li gii
Một năm có 12 tháng. Ta phân chia 40 hc sinh vào 12 tháng đó. Nếu mi tháng có không quá 3 hc sinh
được sinh ra thì s hc sinh không quá:
3.12 36=
: vô lý.
Vy tn ti mt tháng có ít nht 4 hc sinh trùng tháng sinh ( trong bài này 40 th là 40 hc sinh, 12 lng
là 12 tên tháng).
Bài 15:
Cho dãy s gm 5 s t nhiên bt kì
1 2 3 4 5
, , , , a a a a a
. Chng minh rng tn ti mt s chia hết cho 5
hoc tng ca mt s s liên tiếp trong dãy đã cho chia hết cho 5.
Li gii
Ta s thành lp dãy s mi gm 5 s sau đây:
11
Sa=
2 1 2
S a a=+
3 1 2 3
S a a a= + +
4 1 2 3 4
S a a a a= + + +
5 1 2 3 4 5
S a a a a a= + + + +
- Nếu mt trong cách
( )
1, ... 5
i
Si=
chia hết cho 5 thì bài toán đã được chng minh.
- Nếu không có s nào chia hết cho 5 thì khi đem chia các số S
i
cho 5 s đưc 5 s dư có giá trị t 1 đến 4.
5 s dư mà chỉ có 4 giá tr (5 th, 4 lng). Theo nguyên tc Điriclê ít nhất phi có 2 s dư có cng giá
tr. Hiu ca chúng chia hết cho 5. Hiu này chính là tng các a
i
liên tiếp nhau hoc là a
i
nào đó.
Bài 16:
Trang 10
Vi 39 s t nhiên liên tiếp, hi rng ta có th m được mt s mà tng các ch s ca nó chia hết cho 11
hay không?
Li gii
T 20 s đầu tiên ca dãy bao gi ta cũng có thể m được 2 s mà ch s hàng đơn vị là 0, và trong hai s
đó ít nhất phi có mt s có ch s hàng chc khác 9. Gi s N là s đó, và ta gi S là tng các ch s ca
N.
Ta có dãy s mi
; 1; 2;... 9; 19N N N N N+ + + +
là 11 s vn nm trong 39 s cho trước
mà tng các ch s ca chúng là
; 1;SS+
2; ... ; 9;SS++
10S +
. Đó là 11 số t nhiên liên
tiếp, t phi có mt s chia hết cho 11.
Bài 17:
Chng minh rng trong 52 s t nhiên ty , chí ít cũng có một cp gm hai s sao cho hoc tng hoc
hiu ca chúng chia hết cho 100.
Li gii
Để làm xut hin s "th" và s "lồng ta làm như sau:
Trong tp hp các s dư trong phép chia cho 100 ta ly ra tng cp s sao cho tng các cặp đó bằng 100
và thành lp thành các nhóm sau:
(0 ; 0), (1 ; 99), (2 ; 98), (3 ; 97), (4 ; 96), (5 ; 95), (6 ; 94)... (49 ; 51), (50 ; 50).
Chú ý rng s có 50 cặp như vậy, ta thêm vào cp (0, 0) s có 51 cp (51 lng).
- Đem chia 52 số t nhiên cho 100 s có 52 s dư (52 thỏ).
- Có 52 s mà chỉ có 51 nhóm, theo nguyên tắc Điriclê ít nhất cũng phải2 s dư cng rơi vào một
nhóm.
ràng là cp s t nhiên ng vi cp s này chính là hai số t nhiên có tng hoc hiu chia hết cho
100. (đpcm)
Bài 18:
Chng minh rng trong 19 s t nhiên bất kì ta luôn luôn tìm được mt s mà tng các ch s ca nó chia
hết cho 10.
Li gii
Trước hết ta chng minh rng trong n s t nhiên liên tiếp bao gi cũng tn ti mt s chia hết cho n. (Các
bn t chứng minh điều này).
Vi 19 s t nhiên liên tiếp bt kì luôn luôn tn ti 10 s liên tiếp có ch s hàng chục như nhau, còn các
ch s hàng đơn vị có giá tr t 0 đến 9.
Vì thế tng các ch s ca mi s trong 10 s này cũng làm thành dãy số gm có 10 s t nhiên liên tiếp,
do đó tồn ti mt s chia hết cho 10 (đpcm).
Bài 19:
Trang 11
Một trường hc có 1000 hc sinh gm 23 lp. Chng minh rng phi có ít nht mt lp có t 44 hc sinh
tr lên
Li gii
Gi s 23 lp mi lp có không quá 43 hc sinh.
Khi đó s hc sinh là:
43.23 989=
hc sinh (ít hơn
1000 989 11=
hc sinh)
Theo nguyên lí Dirichlet phi có ít nht mt lp có t 44 hc sinh tr lên
Nhn xét: Các cháu hc sinh để , vi dng toán này, đề bài thường yêu cu chng minh có ít nht 1 lp,
(hoặc tương tự) có ít nht bao nhiêu hc sinh.
Như vậy, vi dng này điều quan trng là chng ta cn ch ra, đâu là th, đâu là chung. Vi bài s 1, đc
đề xong cái là nhìn thy ngay s hc sinh (như là s th) còn s lp chính là s chung.
Nhn xét thêm v cách gii, thc ra nói là áp dng nguyên l Dirichle, nhưng c cháu có th thy chng
ta đang đi chứng minh nguyên l này, bng vic gi s ngược lại (phương pháp phn chng).
Để hiu r hơn, chng ta đi tiếp tc bài 2.
Bài 20:
Mt lp có 50 hc sinh. Chng minh rng có ít nht 5 hc sinh có tháng sinh ging nhau
Phân tch:
Đc đề chng ta thy có hc sinh, đề bài yêu cu chng minh hc sinh có cng tháng sinh. Việc “cng
tháng sinh” ở đây th hiểu như “nhốt cng chung”. N vy, chung đây chính là tháng sinh, còn
hc sinh là“thỏ”.Hướng dẫn giải
Gisử có không quá 4 hc sinh có tháng sinh ging nhau
Một năm có 12 tháng, khi đó s hc sinh ca lp có không quá: 12.4=48 (hc sinh)
Theo nguyên lí Dirichlet phi có ít nht 5 hc sinh có tháng sinh ging nhau
Bài 21:
sáu loi hc bng khác nhau. Hi rng phi có ít nhất bao nhiêu sinh viên để chc chn rngít ra là
6 người cùng nhn hc bổng như nhau.
Phân tch:
Bài toán này, đề bài không yêu cu chng ta chng minh có ít nht bao nhiêu gì đấy trong mt gì đấy na.
Mà ngược lại, đề bài yêu cu chng ta tìm ít nht s hc sinh để tha mãn điu kin có ít nhất như các bài
trước.
Bây gi chng ta phân tích để nhn ra đâu là “thỏ”, đâu “chuồng” nhé. Nào hãy ch yêu cầu đề bài “ít
nhất 6 người cng nhn hc bổng như nhau”, như vậy, người đây chính là “thỏ” còn loi hc bng chính
là “chuồng”. Đ gii bài toán ngược này, chng ta cũng làm ơng tự, gi s không tha mãn đề bài, tc
mi loi hc bng ch có tối đa 5 người….
Li gii
Trang 12
Gi s mi loi hc bng ch có 5 người => s người là
5.6 30=
người.
Nếu ta lấy 31 người, khi đó theo nguyên l Dirichle, tn ti 1 loi hc bng mà có ít nhất 6 người nhn.
Nhn xt: Ta thấy 31 = 30 + 1, như vậy, ta ch vic tìm s ln nhất để không tha mãn đề bài (chính là
5×6 = 30) cng thêm 1 s thành s nh nht tha mãn đề bài.
Bài 22:
Trong 45 hc sinh làm bài kim tra, không có ai b điểm dưới 2, ch có 2 hc sinh được điểm 10. Chng
minh rng ít nht cũng tìm được 6 hc sinh có điểm kim tra bằng nhau (điểm kim tra là mt s t nhiên)
Phân tch:
Đề bài cho 45 hc sinh, (chính là s “thỏ”). Nhưng số chung thì chng ta chưa biết chính xác. Chng ta
cn cn thận hơn với các d kiện “không có ai b điểm dưới 2, ch có 2 hc sinh được điểm 10″. Như vậy
các điểm ch cóth t 2 cho đến 10. Nhưng chỉ có 2 người được 10 tc là còn 43 người còn li ch được
điểm t 2 cho đến 9. (có 8 s ơng ứng 8 “chuồng”)
Li gii
Có 43 hc sinh phân thành 8 loại điểm (t 2 đến 9)
Gi s trong 8 loại điểm đều là điểm ca không quá 5 hc sinh thì lp hc có:
5.8 40=
hc sinh, ít hơn 3 hc sinh so với 43.
Theo nguyên l Dirichlet tn ti 6 hc sinh có điểm kim tra bng nhau.
Bài 23:
Mt lp hc có 50 hc sinh, có duy nht mt hc sinh thiếu nhiu bài tp nht là thiếu 3 bài tp. Chng
minh rng tn ti 17 hc sinh thiếu 1 s bài tập như nhau (trường hp không thiếu bài tp coi như thiếu 0
bài)
Phân tch:
Bài này chng ta để d kiện: “có duy nht mt hc sinh thiếu nhiu bài tp nht là thiếu 3 bài tập”
Þ
các hc sinh còn li ch thiếu 0, 1, hoc 2 bài tp (tc là có 3 loi thiếu bài tp). Loi b hc sinh duy nht
thiếu 3 bài đi, còn li 50 1 = 49 bn.
Li gii
Ngoài bn hc sinh duy nht thiếu 3 bài ta còn 49 bn.
Gi s mi loi bài tp có 16 hc sinh.
S hc sinh không quá
16.3 48=
(thiếu 1 hc sinh).
Theo nguyên lí Dirichlet có ít nht 17 hc sinh thiếu mt s bài tập như nhau
Dng 3: S tương hỗ
Bài 1:
5 đấu th thi đấu c, mỗi người đấu mt trn vi mỗi đấu th khác. Chng minh rng trong sut thi
gian thi đấu, luôn tn tại hai đấu th có s trận đã đấu bng nhau.
Li gii
Trang 13
Gi 5 lng 0, 1, 2, 3, 4 th t chứa các đấu th đã đấu 0, 1, 2, 3, 4 trận. Cũng ch rằng hai lông 0 và 4
không th cùng chứa người. N vậy ch có 4 lồng, mà có 5 người, tn tại 2 người trong cùng mt lng
tc là tn tại hai đấu th s trận đấu bng nhau.
Bài 2:
Cho 5 người ty . CMR trong số đó có ít nhất 2 người số người quen như nhau (hiểu rằng A quen B
thì B quen A).
Phân tích: Chú trọng đến câu hỏi 2 người số người quen như nhau”
Từ đó hiểu rằng 5 người đóng vai trò là số thỏ. Tathể tạo ra các lồng n sau:
Li gii
Gi lồng 0 chứa những người có số người quen 0.
Gi lồng 1 chứa những người có số người quen 1.
Gi lồng 4 chứa những người có số người quen 4.
Như vậy ta có 5 lồng. Nếu lồng 0 có chứa ai đó thì lồng 4 phải trống. Ngược lại nếu lồng 4 có chứa ai đó
thì lồng 0 phải trống.
Vậy thực chất chỉ có 4 lồng nhốt 5 thỏ nên ít nhất 2 người ở cng một phòng tức là hai người đósố
người quen như nhau.
Bài 3:
10 đội bóng thi đấu với nhau mỗi đội phải đấu một trận với các đội khác. CMR vào bất cứ lc nào
cũng có hai đội đã đấu số trận như nhau (kể cả số trận đấu là 0).
Phân tích: Hiểu tương tự như bài toán trên.
Li gii
Gi A
0
là phòng chứa các độisố trận đấu là 0.
Gi A
1
là phòng chứa các độisố trận đấu là 1.
……………
Gi A
9
là phòng chứa các độisố trận đấu là 9.
Nếu phòng A
0
ít nhất 1 đội thì phòng A
9
không có đội nào và ngược lại phòng A
9
ít nhất 1 đội thì
phòng A
0
không có đội nào.
Vậy thực chất chỉ có 9 phòng được sử dụng mà lại có 9 đội nên có ít nhất 2 đội vào chung một phòng hay
có ít nhất 2 đội có cng số trận đấu như nhau.
Bài 4:
6 đội bóng thi đấu vi nhau (mỗi đội phải đu 1 trn với 5 đội khác). CMR vào bt c lc nào cũng
3 đội trong đó từng cặp đã đấu vi nhau hoặc chưa đấu vi nhau trn nào.
Li gii
Gisử 6 đội bóng đó là A, B, C, D, E, F. Xét đội A:
Trang 14
Theo nguyên l Điriclê ta suy ra: A phải đấu hoặc không đấu với ít nhất 3 đội khác.
Không mất nh tổng quát, giả sử A đã đấu với B, C, D.
+ Nếu B, C, D từng cặp chưa đấu với nhau thì bài toán được chứng minh.
+ Nếu B, C, D có 2 đội đã đấu với nhau, ví dụ B và C thì 3 đội A, B, C từng cặp đã đấu với nhau.
Như vậy bất cứ lc nào cũng có 3 đội trong đó từng cặp đã đấu với nhau hoặc chưa đấu với nhau trận nào.
Bài 5:
17 nhà toán hc trao đổi với nhau về 3 vấn đề. Mỗi người tra đổi với một người về 1 vấn đề. CMR
cũng có ít nhất 3 nhà toán hc trao đổi với nhau về cng một vấn đề (AB, B và C, C và A).
Phân tích: Tương tự như 17 điểm được nối với nhau bằng 3 màu à luôn tồn tại một tam giác với 3 cạnh
cùng màu tức là 3 nhà toán học trao đổi với nhau về cùng một vấn đề.
Li gii
Một nhà toán hc trao đổi với 16 nhà toán hc khác về 3 vấn đề Þ Theo nguyên l Điricle có ít nhất 6
người sẽ được một người trao đổi về cng một vấn đề, giả sử đó là vấn đề I.
6 người này lại trao đổi với nhau về 3 vấn đề:
+ TH1: Nếu có 2 người nào đó cng trao đổi về vấn đề I thì bài toán được chứng minh.
+ TH2: Nếu không2 người nào cng trao đổi về vấn đề 1 thì 6 người y chỉ trao đổi về 2 vấn đề II
III.
Một người trao đổi với 5 người n lại về 2 vấn đề II và III. Theo nguyên lĐiricle có ít nhất 3 người
cng được một người trao đổi về 1 vấn đề, giả sử đó là vấn đề II. Ba người này lại tiếp tục trao đổi với
nhau:
+ TH1: Nếu có 2 người nào đó cng trao đổi với nhau về vấn đề II thì bài toán được chứng minh.
+ TH2: Nếu không2 người nào cng trao đổi với nhau về vấn đề II thì c3 người này trao đổi với nhau
về vấn đề III Þ Bài toán cũng đã được chứng minh.
Vậy luônít nhất 3 nhà toán hc trao đổi với nhau về cng một vấn đề
Dng 4: S sp xếp
Bài 1:
Cho mt bng vuông 4 x 4. Trên 16 ô ca bảng, ta đặt 16 s t nhiên t 1 đến 16. Chng minh rng tn ti
hai ô k nhau (tc là hai ô có mt cnh chung ) sao cho hiu các s hai ô đó lớn hơn hoặc bng 3.
Li gii
Trang 15
Chuyn t mt ô bt kì sang ô k nó gi là một bước. Xét hai ô ghi
s 1 s 16 chuyn t ô ghi s 1 đến ô ghi s 16 ch cn không quá
6 bước chuyn (nhiu nhất là 3 bước theo hàng ngang, 3 bước theo
hàng dc). Tn ti một bước chuyn có hiu lớn hơn hoặc bng 3.
Tht vy gi s tt c các bước chuyển đều nh hơn hoặc bng 2 thì
t s 1, qua không quá 6 bước chuyển tăng thêm không quá 12,
không đạt được đến s 16.
Vy tn ti hai ô k nhau có hiu các s của hai ô đó lớn hơn hoặc
bng 3.
Bài 2:
Viết 16 s, mi s giá tr bt k 1, 2, 3, 4. Ghép thành tng cp
2 s được 8 cp s. Chng minh rng tn ti hai cp s mà tng các
s trong hai cặp đó bằng nhau.
Li gii
Tng hai s ca mi cp trong 8 cp s có giá tr nh nht là: 1 + 1 = 2, có giá tr ln nht là: 4 + 4 = 8.
Như vậy 8 tổng đó nhận 7 giá tri: (2, 3, 4, 5, 6, 7, 8). Theo nguyên lý Dirichlet, tn ti hai tng bng nhau,
tc là tn ti hai cp có tng bng nhau.
Dng 5: Bi toán hình hc
Nguyên th m rộng như sau: Nếum vật đặt vào n cái ngăn kéo m > k.n thì có ít nhất mt
ngăn kéo chứa ít nht k + 1 vt. Vi m rng này, ta còn có th gii quyết thêm nhiu bài toán khác.
Bài 1:
Trong tam giác đều có cnh bằng 4 (đơn vị độ dài, được hiểu đến cui bài viết) lấy 17 điểm. Chng minh
rằng trong 17 điểm đó có ít nhất hai điểm mà khong cách giữa chng không vượt quá 1.
Li gii
Chia tam giác đều cnh bằng 4 thành 16 tam giác đều có cnh bng 1 (hình 1).
Vì 17 > 16, theo nguyên lí Đi-rích-lê, tn ti ít nht một tam giác đều cnh bng 1 có
cha ít nhất 2 điểm trong s 17 điểm đã cho. Khoảng cách gia hai điểm đó luôn không
vượt quá 1 (đpcm).
Bài 2:
Trong mt hình vuông cnh bng 7, lấy 51 đim. Chng minh rằng có 3 điểm trong 51 điểm đã cho nằm
trong mt hình tròn có bán kính bng 1.
Li gii
Chia hình vuông cnh bng 7 thành 25 hình vuông bng nhau, cnh ca mi hình
vuông nh bng 5/7 (hình 2).
Trang 16
Vì 51 điểm đã cho thuộc 25 hình vuông nhỏ, mà 51 > 2.25 nên theo nguyên Đi-rích-lê, có ít nht mt
hình vuông nh cha ít nhất 3 điểm (3 = 2 + 1) trong s 51 điểm đã cho. Hình vuông cạnh bng bán
kính đường tròn ngoi tiếp là:
22
77
55
98
1
2 100
+
=
(đpcm)
Hình tròn này chính là hình tròn bán kính bng 1, chứa hình vuông ta đã chỉ ra trên.
Bài 3:
Trong mt phẳng cho 2003 điểm sao cho c 3 điểm bt kì có ít nhất 2 điểm cách nhau mt khong không
vượt quá 1. Chng minh rng: tn ti mt hình tròn bán kính bng 1 cha ít nhất 1002 điểm.
Li gii
Ly một điểm A bất kì trong 2003 điểm đã cho, vẽ đường tròn C
1
tâm A bán kính bng 1.
+ Nếu tt c các điểm đều nm trong hình tròn C1 thì hiển nhiên có đpcm.
+ Nếu tn ti một điểm B khong cách gia A và B lớn hơn 1 thì ta vẽ đưng tròn C
2
tâm B bán kính
bng 1.
Khi đó, xét một điểm C bt kì trong s 2001 điểm còn lại. Xét 3 điểm A, B, C, vì AB > 1 nên theo gi
thiết ta có AC ≤ 1 hoặc BC 1. Nói cách khác, điểm C phi thuc C
1
hoc C
2
.
=> 2001 điểm khác B và A phi nm trong C
1
hoc C
2
.
Theo nguyên lí Đi-rích-lê ta có mt hình tròn cha ít nhất 1001 điểm. Tính thêm tâm ca hình tròn này thì
hình tròn này chính là hình tròn bán kính bng 1 cha ít nhất 1002 điểm trong 2003 điểm đã cho.
Bài 4:
Cho hình bình hành ABCD, k 17 đường thng sao cho mỗi đường thng chia ABCD thành hai hình thang
có t s din tích bng 1/3 . Chng minh rằng, trong 17 đường thẳng đó có 5 đường thẳng đồng quy.
Li gii
Gi M, Q, N, P lần lượt là các trung điểm ca AB, BC, CD, DA (hình 3).
Vì ABCD là hình bình hành => MN // AD // BC ; PQ // AB // CD.
Gi d là mt trong 17 đường thẳng đã cho. Nếu d ct AB ti E ; CD ti F ; PQ ti
L thì LP, LQ lần lượt là đường trung bình ca các hình thang AEFD, EBCF.
Ta có: S(AEFD) / S(EBCF) = 1/3 hoc S(EBCF) / S(EBFC) = 1/3
=> LP / LQ = 1/3 hoc là LQ / LP = 1/3.
Trên PQ lấy hai điểm L
1
, L
2
thỏa mãn điu kin L
1
P / L
1
Q = L
2
Q / L
2
P = 1/3 khi đó L trng vi L
1
hoc L
trùng vi L
2
. Nghĩa là nếu d ct AB và CD thì d phi qua L
1
hoc L
2
.
Tương tự, trên MN lấy hai đim K
1
, K
2
thỏa mãn điều kin K
1
M / K
1
N = K
2
N / K
2
M = 1/3 khi đó nếu d
ct AD và BC thì d phi qua K
1
hoc K
2
.
Trang 17
Tóm li, mỗi đường thng trong s 17 đường thẳng đã cho phải đi qua một trong 4 điểm L
1
; L
2
; K
1
; K
2
.
Vì 17 > 4.4 nên theo nguyên Đi-rích-lê, trong 17 đường thẳng đó sẽ ít nhất 5 đường thng (5 = 4 + 1)
cng đi qua một trong 4 điểm L
1
; L
2
; K
1
; K
2
(5 đường thẳng đồng quy, đpcm).
Dng 6: S trùng lp
- Hc sinh thuộc nội dung nguyên l. Đc bài toán và phân biệt được yếu tnào đóng vai trò là “thỏ”, yếu
tố nào đóng vai trò là “lồng”. Hc sinh chỉ ra được số thỏ, số lồng.
- Cách phân biệt đơn giản nhất: Số thỏ luôn lớn hơn số lồng.
Bài 1:
Trong 45 hc sinh làm bài kiểm tra không ai bị điểm dưới 2, chỉ có 2 hc sinh được điểm 10. CMR ít
nhất cũng tìm được 6 hc sinh có điểm kiểm tra bằng nhau (điểm kiểm tra là một số tự nhiên từ 0 đến 10).
Phân tích: “thỏ” là 43 học sinh, “lồng” là các loại điểm từ 2 đến 9.
Li gii
45 2 = 43 (hc sinh) được 8 loại điểm từ 2 đến 9.
Do 43 : 8 = 5 (dư 3).
Theo Nguyên l Điricle có ít nhất 6 hc sinh có điểm kiểm tra bằng nhau.
Bài 2:
Một trường hc có 24 lớp gồm 900 hc sinh. Chứng minh rằng có một lớp với sĩ số 38 hc sinh trở lên.
Phân tích: Chia 900 học sinh vào 24 lớp có ý nghĩa tương tự như nhốt 900 con thỏ vào 24 cái lồng. T đó
có thể áp dụng ngay nội dung nguyên lý để giải bài toán:
Li gii
900 hc sinh được chia vào 24 lớp, mà 900: 24 = 37 (dư 12)
Theo nguyên l Điricle sẽ tồn tại một lớp có từ 37 + 1 = 38 (hc sinh) trở lên.
Bài 3:
Trong lớp hc có 30 hc sinh. Khi viết chính tả một em phạm 14 lỗi, các em khác phạm số lỗi ít hơn.
CMR ít nhất 3 hc sinh mắc số lỗi bằng nhau (kể cả những người mắc 0 lỗi).
Phân tích: Trong bài toán này “thỏ” là 29 học sinh (trừ đi 1 em mắc 14 lỗi), “lồng” là các loại lỗi (gồm
14 loại: 0 lỗi, 1 lỗi, 2 lỗi, , 13 lỗi).
Li gii
30 hc sinh trong đó 1 em phạm 14 lỗi, số còn lại là 29 em phạm các lỗi từ 0 đến 13 lỗi (14 loại lỗi).
Do 29: 14 = 2 (dư 1)
Theo Nguyên l Điricle có ít nhất 3 em mắc cng số lỗi như nhau.
Bài 4:
Trong một kỳ thi toán hc 6 thí sinh được vào chung khảo. Thể lệ của cuộc thi như sau: Mỗi thí sinh
phải giải 5 bài toán. Mỗi bài toán đng được tính 4 điểm. Mỗi bài toán sai hoặc không làm được đều bị trừ
Trang 18
2 điểm. Hãy chứng tỏ rằng trong 6 thí sinh đó có ít nhất 2 thí sinh bằng điểm nhau. Biết rằng điểm thấp
nhất là điểm 0.
Phân tích: số “thỏ” dường như là 6 học sinh, nhưng “lồng” là gì nhỉ? Ta phải đặc biệt chú ý đến nội
dung câu hỏi t nhất 2 thí sinh bằng điểm nhau” liên tưởng đến nội dung nguyên nó giống n 2
thỏ nhốt chung một lồng. Từ đó tìm ra yếu tố lồng đây là số điểm đạt được.
Giải
Vì mỗi thí sinh phải giải 5 bài toán. Mỗi bài toán đng được tính 4 điểm. Mỗi bài toán sai hoặc không làm
được đều bị trừ 2 điểm nên ta có 5 trường hợp sau:
Nếu đng 5 bài thì số điểm được là: 5. 4 = 20 (điểm).
Nếu đng 4 bài thì số điểm được là: 4. 4 - 2 = 14 (điểm).
Nếu đng 3 bài thì số điểm được là: 3. 4 4 = 8 (điểm).
Nếu đng 2 bài thì số điểm được là: 2. 4 6 = 2 (điểm).
Nếu đng 1 bài hoặc không đng bài nào thì đều được 0 điểm.
Như vậy có 6 thí sinh dự thi nhưng chỉ có 5 loại điểm nên theo nguyên l Điricle sẽ có ít nhất 2 thí sinh
bằng điểm nhau.
PHẦN III.BÀI TOÁN TRONG ĐỀ THI HSG6
Bài 1:
Trong mt phòng hp n người, bao gi cũng tìm được 2 ngưi có s người quen trong s nhng người
d hp là như nhau.
Phân tch:
Phòng hp có n người, có th coi là n “thỏ” rồi này. Bây gi chng ta xác định đâu “chuồng”. Hãy đc
k đề bài yêu cu gì, chng ta s nhìn ra “chuồng” ngay. “tìm được 2 người có s người quen trong s
những người d hp là như nhau” => số người quen ging nhau, hay chính là nht cng “chuồng”. Như
vy, s người quen chính là s “chuồng”.
Ta thấy 1 người có th quen với 0 người, 1 người, .hoặc nhiu nht là n-1 người trong cuc hp….
Li gii
Số người quen của mỗi người trong phòng hp nhận các giá trị từ 0 đến
–1n
. Rõ ràng trong phòng
không thể đồng thời có người có số người quen 0 (tức là không quen ai) có người có số người quen
–1n
(tức là quen tất cả). Vì vậy theo số lượng người quen, ta chỉ có thể phân n người ra thành
–1n
nhóm.
Vậy theo nguyên Dirichlet tồn tai một nhóm có ít nhất 2 người, tức là luôn tìm được ít nhất 2 người có
số người quen là nnhau.
Bài 2:
Trang 19
Trong một lưới ô vuông kích thước 5.5, người ta điền ngu nhiên vào các ô mt trong các giá tr 0,1 hoc
2, sau đó tính tổng tt c các ô theo hàng ; theo cột và theo hai đường chéo. Chng minh rng tn ti ít
nht hai tng có giá tr bng nhau.
Phân tch:
Hãy đc k đề bài yêu cu, chng ta s thấy “thỏ” và “chuồng”
“Tn ti ít nht 2 tng có giá tr bằng nhau”
Þ
th chính là tng (hàng ngang, dc, chéo), còn giá tr chính
là “chuồng”. Vấn đề ca chng ta là chng ta cần đim các giá tr có th ca tng. Ta thy mt tng 5 ô
s có giá tr nh nht là 0, ln nht là 10.
Li gii
Gi các tổng lần lượt S1,S2,..S12.
tất cả 12 tổng. Ta nhận thấy rằng các tổng này chỉ có thể nhận các giá trị là {0, 1, 2…., 9, 10}. tất
cả 11 giá trị khác nhau. Từ đó, theo nguyên l Dirichlet ta suy ra điều cần chứng minh.
Bài 3:
Gisử trong một nhóm 6 người mỗi cặp hai hoặc là bạn hoặc là th. Chứng tỏ rằng trong nhóm có ba
người là bạn lẫn nhau hoặc có ba người là kẻ th lẫn nhau.
Li gii
Gi A là một trong 6 người. Trong số 5 người của nhóm hoặc là có ít nhất ba người là bạn của A hoặc
ít nhất ba người là kẻ th của A, điều này suy ra từ nguyên lí Dirichlet, vì những người khác chỉ có thể là
bạn hoặc th của A.
Trong trường hợp đầu ta gi B,C,D là bạn của A. nếu trong ba người này có hai người là bạn thì h cng
với A lập thành một bộ ba người bạn lẫn nhau, ngược lại, tức là nếu trong ba người B,C,D khôngai là
bạn ai cả thì chứng tỏ h là bộ ba người th lẫn nhau.
Tương tự có thể chứng minh trong trường hợp có ít nhất ba người là kẻ th của A. (ĐPCM)
Bài 4:
5 đấu thủ thi đấu cờ, mỗi người đấu một trận với mỗi đấu thủ khác. Chứng minh rằng trong suốt thời
gian thi đấu, luôn tồn tại hai đấu thủ có số trận đã đấu bằng nhau.
Li gii
Ta có số trận đã đấu của mỗi người có thể là 0,1,2,3,4. Nhưng vì không thểcng lc một người đã đấu
4 trận và một người chưa đấu trận nào, nên có tối đa 4 loại số trận đã đấu.
Vận dụng nguyên l Dirichlet ta có ít nhất có 2 người có cng số trận đã đấu.
Bài 5:
Có 6 hc sinh làm mt bài thi gm 6 câu hi. Nếu tr lời đng được 2 điểm, tr li sai b tr 1 điểm. Nếu
s điểm b tr nhiều hơn số điểm đạt được thì tính b 0 điểm. Hi có th luôn có 2 hc sinh bằng đim
nhau được hay không???
Phân tch v gi gii:
Trang 20
Bài này đề bài li hi theo kiu có hay không, nhưng chng ta hãy bình tình. Nếu mt khi chng ta đã hiu
bn cht ca bài toán dng này thì s không gì làm chng ta s hay mt t tin được c.
“Hai hc sinh bằng điểm nhau”
Þ
Hc sinh chính là “thỏ”, điểm chính là “chuồng”.
Vấn đề bài toán tr thành đi tìm s điểm có th (s chung), t đó s gip chng ta tr lời được câu hi
của đề bài.
Đề thi gm 6 bài, xy ra các trường hp sau:
- Đng hết 6 câu => 12 điểm
- Đng 5 câu, sai 1 câu => 5×2 -1 = 9 điểm
- Đng 4 câu, sai 2 câu => 4×2 -2×1 = 6 điểm
- Đng 3 câu, sai 3 câu => 3×2 3×1 = 3 điểm
- Đng 2 câu, sai 4 câu => 2×2 4x 1 = 0 đim
- Đng dưới 2 câu => d thy s b 0 điểm.
Nhìn li ta thy ch có 0,3,6,9,12 điểm tc là ch có 5 loại điểm, trong khi có 6 hc sinh => có 2 hc sinh
cng điểm.
| 1/20

Preview text:

S6-CHUYÊN ĐỀ 8. NGUYÊN LÍ DIRICHLET
PHẦN I. TÓM TẮT LÝ THUYẾT
1. Nội dung nguyên lí
Nếu nhốt n.m + r (trong đó m, n, r Î ¥ * ) con thỏ vào n cái chuồng thì phải có ít nhất một chuồng
chứa không ít hơn m + 1 con thỏ. Chứng minh
Giả sử ngược lại mỗi chuồng chứa không quá m con thỏ thì tổng số thỏ nhốt trong n chuồng sẽ không quá .
m n con thỏ :Mâu thuẫn với giả thiết là số thỏ bằng m.n + r .Vậy phải có ít nhất một chuồng chứa
không ít hơn m + 1 con thỏ. 2. Nhận xét
Bản thân nguyên li Dirichlet khá đơn giản và dễ hiểu, tuy nhiên việc ứng dụng nguyên lí này lại không hề
đơn giản .Vấn đề ở đây là phát hiện ra “chất Dirichlet “ trong các bài toán , dạng toán của mình và sau đó
xác định trong đó đâu là chuồng và đâu là thỏ.Có những trường hợp chuồng và thỏ gần như đã có sẵn,
nhưng có những trường hợp chúng ta phải “xây chuồng , tạo thỏ”.
PHẦN II.CÁC DẠNG BÀI
Dạng 1: Toán chia hết
Khi chia số a cho số m ¹ 0 luôn có m khả năng về số dư là 0,1,….,m - 1 (“m chuồng “).Do vậy, khi
chia m + 1 số khác nhau a ,a , .....,a
cho m ta sẽ có m + 1 số dư (“m + 1 thỏ”) và do đó luôn 1 2 m + 1
có hai phép chia có cùng số dư.Giả sử hai số bị chia trong hai phép chia đó là a a (với i j
1 £ j < i £ m + 1 ). Ta có (a - a ) m M . i j Bài 1:
Chứng minh rằng có thể tìm được một số có dạng 19781978.....197800...0 chia hết cho 2012. Lời giải
Xét dãy số : 1978, 19781978, ....., 19781978...1978
14444442 4444443. Khi chia các số hạng của dãy này cho 2012 sẽ có 2013 so 1978
hai phép chia có cùng số dư. Giả sử hai số hạng của dãy trong hai phép chia đó là a = 19781978...1978 14444442 4444443 m so 1978 và b = 19781978...1978
14444442 4444443 ( với 1 £ n < m £ 2013) . n so 1978
Hiệu của a b chia hết cho 2012 hay a - b = 19781978....1978 { 00...0 2012 M 144444442 44444443 (đpcm) m - n so 1978 4n so 0 Trang 1
Nhận xét: Phương pháp để giải dạng toán này là tạo ra dãy số (theo cấu tạo số) từ yêu cầu của bài toán
(“tạo thỏ”) . Sau đó áp dụng nguyên lí Dirichlet cho các số hạng của dãy số mới (mỗi số hạng thay cho
một “thỏ”, 2012 là số “chuồng”). Bài 2:
Cho dãy m số tự nhiên bất kì a ,a , ...., a . Chứng minh rằng tồn tại một số hạng chia hết cho m hoặc 1 2 m
tổng của một số hạng liên tiếp trong dãy chia hết cho m (m Î ¥ *) . Lời giải
Xét dãy số b = a ,b = a + a , .......,b = a + a + .... + a 1 1 2 1 2 m 1 2 m
Khi chia các số hạng của dãy này cho m thì xảy ra một trong hai trường hợp sau :
• Có một phép chia hết , chẳng hạn : b m
M , thì ta có điều phải chứng minh : k
(a + a + .... + a ) m M 1 2 k
• Không có phép chia hết nào .Khi đó tồn tại hai phép chia có cùng số dư , chẳng hạn là b ,b i j
chia cho m ( vơi 1 £ j < i £ m )
 (b b ) m hay (a + a
+ ....+ a ) m , ta có điều phải chứng minh . i j j 1 + j +2 i
Nhận xét: Phương pháp “tạo thỏ “ trong ví dụ này là dựa vào phép toán cộng và yêu cầu về tính liên tiếp
của các số hạng trong dãy ban đầu của đề bài . Bài 3:
Cho bốn số tự nhiên phân biệt a > b > c > d . Chứng minh rằng: P = (a - )
b (a - c)(a - d)(b - c)(b - d)(c - d) 12 M Lời giải Chia bốn số phân biệt , a , b ,
c d cho 3 luôn có hai phép chia có cùng số dư
hiệu hai số bị chia đó chia hết cho 3 tồn tại hiệu hai số trong bốn số , a , b ,
c d chia hết cho 3. Do vậy P chia hết cho 3 (1) Trong bốn số , a , b ,
c d nếu có hai số có cùng số dư khi chia cho 4 thì P chia hết cho 4;trái lại , khi chia
bốn số đó cho 4 có đủ bốn trường hợp về số dư là 0,1,2,3 trong bốn số , a , b ,
c d có hai số chẵn , hai số
lẻ, giả sử a,c chẵn và ,
b d lẻ(a - c) 2 M và (b - d) 2 M
Do vậy P chia hết cho 4 (2)
Từ (1),(2) và (3,4)=1 suy ra P 3, M 4 hay P 12 M (đpcm) Bài 3:
Chứng minh rằng trong 19 số tự nhiên liên tiếp bất kì ta luôn tìm được một số có tổng các chữ số chia hết cho 10. Trang 2 Lời giải
Trong 19 số tự nhiên liên tiếp luôn tồn tại 10 số tự nhiên liên tiếp có chữ số hàng chục giống nhau , kí
hiệu chữ số hàng chục đó là a (các chữ số hàng trăm, hàng nghìn, ….(nếu có ) cũng giống nhau), còn các
chữ số hàng đơn vị là dãy 0;1;2;3;…;9.
Do đó tổng các chữ số của mỗi số cũng là một dãy 10 số tự nhiên liên tiếp, vì thế tồn tại số có tổng các chữ số chia hết cho 10. Bài 4:
Cho 12 số tự nhiên khác nhau có hai chữ số. Chứng minh rằng không tồn tại hai số có hiệu là một số có hai chữ số như nhau. Lời giải
Có 12 số tự nhiên khác nhau, mà chỉ có 11 số dư trong phép chia cho 11, do đó tồn tại hai số có cùng số
dư trong phép chia cho 11. Hiệu của chúng là một số chia hết cho 11, đó là số có hai chữ số như nhau. Bài 5:
Chứng minh rằng trong 11 số tự nhiên bất kì bao giờ cũng tồn tại ít nhất 2 số có hiệu chia hết cho 10. Lời giải
Với 11 số tự nhiên khi chia cho 10 ta được 11 số dư, mà một số tự nhiên bất kì khi chia cho 10 có 10 khả
năng dư là 0 ; 1 ; 2 ; 3 ; ... ; 9.
Vì có 11 số dư mà chỉ có 10 khả năng dư, theo nguyên lí Đi-rích-lê, tồn tại ít nhất 2 số khi chia cho 10 có
cùng số dư do đó hiệu của chúng chia hết cho 10 (đpcm). Bài 6:
Chứng minh rằng tồn tại số có dạng 19941994...199400...0 chia hết cho 1995. Lời giải
Ta có 19941994...199400...0 = 19941994...1994  100...0
Xét 1995 số có dạng: 1994 ; 19941994 ; ... ; .
+) Nếu một trong các số trên chia hết cho 1995 thì dễ dàng có điều phải chứng minh.
+) Nếu các số trên đều không chia hết cho 1995 thì khi chia từng số cho 1995 sẽ chỉ có 1994 khả năng dư là 1 ; 2 ; 3 ; ... ; 1994.
Vì có 1995 số dư mà chỉ có 1994 khả năng dư, theo nguyên lí Đi-rích-lê tồn tại ít nhất 2 số khi chia cho
1995 có cùng số dư, hiệu của chúng chia hết cho 1995.
Khi đó 1994...199400...0 chia hết cho 1995 (đpcm). Bài 7:
Chứng minh rằng tồn tại số tự nhiên k sao cho (1999^k - 1) chia hết cho104. Lời giải
Xét 104 số có dạng: 1999^1 ; 1999^2 ; ... ; 1999^104. Trang 3
Lấy tất cả các số trên chia cho 104 sẽ chỉ có 103 khả năng dư là 1 ; 2 ; 3 ; ...; 103 (chú ý: sẽ không có số
dư 0 vì 1999 và 104 là hai số nguyên tố cùng nhau nên 1999 mũ bao nhiêu cũng không chia hết cho 104)
Mà dãy số trên có 104 số nên sẽ có ít nhất hai số khi chia cho 104 có cùng số dư.
Gọi hai số có cùng số dư khi chia cho 104 là 1999^a và 1999^b (với a > b)
Ta có: 1999^a - 1999^b ⋮ 104 => 1999^b[1999^(a-b) – 1] ⋮ 104
Mà UCLN(1999^b, 104) là 1 (vì là hai số nguyên tố cùng nhau) nên 1999^(a-b) – 1 ⋮ 104
Đặt k = a – b, ta có 1999^k – 1 ⋮ 104 (đpcm) Bài 8:
Chứng minh rằng tồn tại một số chỉ viết bởi hai chữ số chia hết cho 2003. Lời giải
Xét 2003 số có dạng 1 ; 11 ; 111 ; ... ;
+) Nếu có một số chia hết cho 2003 thì ta được sô 11...1100..00 ⋮ 2003 (đpcm)
+) Nếu không có một số nào chia hêt cho 2003 thì sẽ có 2002 khả năng dư là 1 ; 2 ; 3 ; ...; 2002.
Mà dãy số trên có 2003 số hạng nên sẽ có ít nhất hai số khi chia cho 2003 có cùng số dư
Gọi hai số có cùng số dư khi chia cho 2003 là 11...11 và 111...111 (với n > m) m chu so 1 n chu so 1
Khi đó 111...111 - 11...11 = 11...110...00000 ⋮ 2003 (đpcm). n chu so 1 m chu so 1 n−m chu so 0
Dạng 2: Toán suy luận Bài 1:
Có 10 đội bóng thi đấu với nhau vòng tròn một lượt , mỗi đội phải đấu đúng một trận với mỗi đội khác
.Chứng minh rằng vào bất cứ lúc nào cũng có hai đội đã đấu số trận như nhau. Lời giải
Rõ ràng nếu trong 10 đội bóng có 1 đội chưa đấu một trận nào thì trong các đội còn lại không có đội nào
đã thi đấu 9 trận . Như vậy mỗi đội chỉ có số trận đấu hoặc từ 0 đến 8 hoặc từ 1 đến 9 .Vậy theo nguyên lí
Dirichlet phải có ít nhất hai đội có số trận đã đấu như nhau. Bài 2:
Trong 45 học sinh làm bài kiểm tra không có ai bị điểm dưới 2 và chỉ có 2 học sinh được điểm 10 .Chứng
minh rằng ít nhất cũng tìm được 6 học sinh có điểm kiểm tra bằng nhau ( điểm kiểm tra là một số tự nhiên từ 0 đến 10). Lời giải
Số học sinh có điểm kiểm tra từ 2 đến 9 là : 45 – 2 =43 Ta có : 43 = 8.5 + 3 Trang 4
Như vậy , khi phân chia 43 học sinh vào 8 loại điểm kiểm tra ( từ 2 đến 9 ) thì theo nguyên lí Dirichlet
luôn tồn tại ít nhất 5 + 1 = 6 học sinh có điểm kiểm tra giống nhau (đpcm) Bài 3:
Có 17 nhà Toán học viết thư cho nhau trao đổi về 3 vấn đề khoa học , mỗi người đều trao đổi với 16 người
còn lại và mỗi cặp 2 người chỉ trao đổi với nhau một vấn đề .Chứng minh rằng có ít nhất 3 nhà Toán học
trao đổi với nhau về cùng một vấn đề. Lời giải
Gọi A là một nhà Toán học nào đó trong 17 nhà Toán học thì A phải trao đổi với 16 người còn lại về 3
vấn đề khoa học ( kí hiệu là vấn đề I,II,III).
Vì 16 = 3.5 + 1 nên A phải trao đổi với ít nhất 5 + 1 = 6 nhà Toán học khác về cùng một vấn đề ( theo nguyên lí Dirichlet) .
Gọi 6 nhà Toán học cùng trao đổi với A về một vấn đề (chẳng hạn là vấn đề 1) là A , A , ....., A .Ta thấy 1 2 6
6 nhà Toán học này lại trao đổi với nhau về 3 vấn đề nên có hai khả năng xảy ra:
1) Nếu có 2 nhà Toán học nào đó cùng trao đổi với nhau về vấn đề I thì cùng với A sẽ có 3 nhà Toán học
cùng trao đổi về vấn đề I.
2) Nếu không có 2 nhà Toán học nào cùng trao đổi với nhau về vấn đề I , thì 6 nhà Toán học này chỉ trao
đổi với nhau về 2 vấn đề II và III.Theo nguyên lí Dirichlet , có ít nhất 3 nhà Toán học cùng trao đổi với
nhau về một vấn đề ( II hoặc III).
Vậy luôn có ít nhất 3 nhà Toán học trao đổi với nhau về cùng một vấn đề .
Nhận xét: Trong ví dụ trên ta đã phải phân chia bài toán thành hai lớp và sử dụng hai lần nguyên lí
Dirichlet : Lần thứ nhất với 16 thỏ và 3 chuồng ; lần thứ hai với 6 thỏ và 2 chuồng. Bài 4:
Chứng minh rằng tồn tại một số tự nhiên gồm toàn chữ số 1 chia hết cho 2013. Lời giải
Xét 2014 có dạng 1,11,111,…., {
11...1 . Theo nguyên lý Dirichlet thì tồn tại hai số có cùng số dư khi chia 2014 1
cho 2013. Giả sử hai số đó là a = { 11...1 , b = { 11...1 với n>k. n sè 1 k sè1 k
Khi đó a - b = { 11...1.10 2013 M . n - k sè 1
Vì (2007, 10k ) = 1 nên số c = { 11...1 chia hết cho 2013 n - k sè 1 Bài 5:
Cho 5 số tự nhiên phân biệt a > a > a > a > a . Xét tích 1 2 3 4 5 Trang 5
P = (a - a )(a - a )(a - a )(a - a )(a - a )(a - a )(a - a )(a - a )(a - a )(a - a ) 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
Chứng minh rằng P 228 M Lời giải Ta có 2 5 288 = 3 .2 1. Chứng minh 2 P 3 M
Xét 4 số a , a , a , a , : Ta thấy tồn tại hai số có cùng số dư khi chia cho 3, giả sử a a => 1 2 3 4 1 2 (a - a ) 3 M 1 2
Lại xét a ,a ,a ,a trong 4 số này lại tồn tại 2 số có cùng số dư khi chia cho 3, giả sử a a => 2 3 4 5 4 5 (a - a ) 3 M 4 5 Do vậy P 9 M (1) 2. Chứng minh 5 P 2 M
Trong 5 số đã cho có 3 số cùng tính chẵn lẻ.
Nếu có 3 số chẵn, 2 số lẻ, chẳng hạn là : a = 2k , a = 2k , a = 2k , a = 2k + 1 , a = 2k + 1 1 1 2 2 3 3 4 4 5 5
Khi đó: P = 16(k - k )(k - k )(k - k )(k - k ).M 1 2 1 3 2 3 4 5
Trong đó 3 số k , k , k có 2 số cùng tính chẵn lẻ, chẳng hạn k k , thì (k - k ) 2 M . Vậy P 32 M 1 2 3 1 2 1 2
Nếu có 3 số lẻ, 2 số chẵn thì chứng minh tương tự ta cũng có P 32 M
Vậy trong mọi trường hợp ta đều có P 32 M (2)
Từ (1), (2) và (9,32)=1 suy ra P 9, M 32 hay P 288 M (đpcm). Bài 6:
Chứng minh rằng trong n + 1 số bất kì thuộc tập hợp {1;2; 3;....;2n } luôn tìm được hai số mà số này là bội của số kia. Lời giải
Viết n+1 số lấy ra dưới dạng k k k 1 2 + 1
a = 2 b ,a = 2 b , ...., a = 2 n b
trong đó b ,b , ....,b là các số lẻ, 1 1 2 2 n + 1 n + 1 1 2 n + 1
Ta có: 1 £ b ,b , ....,b
£ 2n - 1. . Mặt khác trong khoảng từ 1 đến 2n-1 có đúng n số lẻ nên tồn tại hai 1 2 n + 1
số m, n sao cho b = b . Khi đó, trong hai số a a có một số là bội của số kia (đpcm) n m n m Bài 7:
Xét 100 số tự nhiên 0 < a ,a , ...., a
£ 100 và có tổng bằng 200 .Chứng minh rằng trong 100 số đó 1 2 100
luôn tồn tại một vài số có tổng bằng 100. Trang 6 Lời giải
1. Nếu a = a = ... = a
= 2 thì ta chọn 50 số bất kì đều có tổng bằng 100. 1 2 100
2. Nếu a ¹ a thì ta lập dãy sau 1 2
a ,a ,a + a ,a + a + a + ... + a + a + ... + a ( các số hạng này có giá trị từ 1 đến 199). 1 2 1 2 1 2 3 1 2 99
- Nếu tồn tại một số hang nào trong dãy chia hết cho 100 thì số hạng đó bằng 100
- Nếu không có số hạng nào chia hết cho 100 thì trong 100 số này khi chia cho 100 sẽ có hai số hạng có
cùng số dư . Hiệu của chúng cho ta tổng cần tìm. Bài 8:
Cho 69 số tự nhiên khác 0 phân biệt và không vượt quá 100 .Chứng minh rằng có thể chọnđược 4 số trong
69 số đó thỏa mãn tổng của ba số bằng số còn lại Lời giải
Giả sử 69 số đã cho là 1 £ a + a < a + a < ... < a + a
£ 100 . Khi đó a £ 32 . Xét hai dãy 1 3 1 4 1 69 1 sau:
1 < a + a < a + a < ... < a + a £ 132(1) 1 3 1 3 1 69
1 £ a - a < a - a < ... < a - a £ 132(2) 3 2 4 2 69 2
Từ (1) và (2) ta có 134 số hạng có giá trị từ 1 đến 132, suy ra có 2 số bằng nhau mỗi số thuộc một dãy,
chẳng hạn: a + a
= a - a (với 3 £ m < n £ 69) tức là ta tìm được 4 số a ;a ;a ;a với 1 m n 2 1 2 n m
a < a < a a + a + a = a (đpcm) 1 2 m 1 2 m n Bài 9:
Chứng minh rằng trong 39 số tự nhiên liên tiếp bất kì luôn có ít nhất một số có tổng cácchữ số chia hết cho 11. Lời giải
Giả sử 39 số tự nhiên liên tiếp đó là a < a < ... < a . 1 2 39
Trong 20 số hạng đầu tiên của dãy này sẽ có hai số tận cùng là 0 và có một số (trong hai số này) có chữ số
đứng trước số tận cùng khác 9. Gọi số này là N.
Xét các số N + 1, N + 2,..., N + 19 thuộc 39 số đã cho. Khi đó:
S (N + i) = S (N ) + i với i = 1, 2,..., 9 và S (N + 19) = S (N ) + 10 .
(kí hiệu S(a) là tổng các chữ số của a).
Trong 11 số tự nhiên liên tiếp S (N ), S (N ) + 1, ..., S (N ) + 9, S (N ) + 10 luôn có một số chia hết cho
11, chẳng hạn: S (N + m ) 11
M với m Î {1;2;...;9;1 } 9
Vậy N + m là số thỏa mãn. Trang 7 Bài 10:
Cho 15 số tự nhiên phân biệt, khác 0, không lớn hơn 28. Chứng minh rằng trong 15 số đó luôn tìm được ít
nhất một bộ 3 số mà số này bằng tổng của hai số còn lại hoặc một cặp 2 số mà số này gấp đôi số kia. Lời giải
Gọi 15 số tự nhiên sắp xếp theo thứ tự từ nhỏ đến lớn là : a ,a , ..., a . 1 2 15
Xét dãy số: b = a - a ,b = a - a , ...,b = a - a . Các số hạng của dãy số này có giá trị từ 1 đến 1 2 1 2 3 1 14 15 1
27 và đôi một khác nhau.
Þ Dãy số a ,a ,...,a ;b ,b ,...,b có 29 số hạng nhưng chỉ nhận 28 giá trị khác nhau (từ 1 đến 28). 1 2 15 1 2 14
Theo nguyên lí Dirichlet, tồn tại hai số bằng nhau, chẳng hạn: b = a (1 £ m £ 14, 1 £ n £ 15) m n Hay a
- a = a Û a = a + a . m + 1 1 n m + 1 1 n - Nếu n = 1 thì a = 2a m + 1 1
- Nếu n ¹ 1thì 3 số a , a ,a phân biệt và a = a + a . 1 n m + 1 m + 1 1 n
Vậy ta chỉ việc chọn 3 số a , a , a
hoặc 2 số a , a
sẽ thỏa mãn yêu cầu đề bài. 1 n m + 1 1 m + 1 Bài 11:
Chọn 5 người bất kì. Chứng minh rằng có ít nhất 2 người có cùng số người quen trong 5 người đó. Lời giải
Mỗi người trong số 5 người có khả năng về số người quen (từ 0 đến 4). Ta xét hai trường hợp sau:
1. Nếu có một người không quen ai trong số 4 người còn lại thì rõ ràng không có ai quen cả 4 người. Như
vậy, 5 người mà chỉ có 4 khả năng về số người quen (từ 0 đến 3) nên theo nguyên lí Dirichlet có ít nhất
hai người có cùng số người quen.
2. Nếu mỗi người đều có ít nhất một người quen. Khi đó 5 người mà chỉ có 4 khả năng về số người quen
(từ 1 đến 4), theo nguyên lí Dirichlet có ít nhất hai người có cùng số người quen Bài 12:
Có 6 đội bóng thi đấu với nhau vòng tròn một lượt, mỗi đội đấu đúng một trận với mỗi đội khác. Chứng
minh rằng vào bất cứ thời điểm nào cũng có ba đội trong đó từng cặp đã đấu với nhau hoặc chưa đấu với nhau trận nào. Lời giải
Giả sử 6 đội bóng đá là A, B, C, D, E, F. Xét đội A, Vì A phải đấu từ 0 đến 5 trận nên theo nguyên lí
Dirichlet ta suy ra. Hoặc A đã đấu hoặc A chưa đấu với ít nhất 3 đội khác. Không mất tính tổng quát, giả
sử A đã đấu với B, C, D
- Nếu B, C, D từng cặp chưa đấu với nhau thì bài toán được chứng minh.
- Nếu B, C, D có 2 đội đã đấu với nhau, ví dụ là C thì 3 đội A, B, C từng cặp đã đấu với nhau Trang 8
Như vậy bất cứ lúc nào cũng có 3 đội trong đó từng cặp đã đấu với nhau hoặc chưa đấu với nhau trận nào. Bài 13:
Một đồi thông có 800 000 cây thông. Trên mỗi cây thông có không quá 500 000 chiếc lá. Chứng minh
rằng ít nhất cũng có 2 cây thông có cùng số lá như nhau ở trên cây. Lời giải
Ta hãy tưởng tượng mỗi cây thông là một "thỏ", như vậy có 800.000 "thỏ" được nhốt vào không quá
500.000 "chiếc lồng". Lồng 1 ứng với cây thông có 1 chiếc lá trên cây, lồng 2 ứng với cây thông có 2
chiếc lá trên cây v.v... Số thỏ lớn hơn số lồng, theo nguyên tắc Điriclê ít nhất có 1 lồng nhốt không ít hơn
2 thỏ nghĩa là có ít nhất 2 cây thông có cùng số lá. Bài 14:
Một lớp học có 40 học sinh. Chứng minh rằng có ít nhất 4 học sinh có tháng sinh giống nhau Lời giải
Một năm có 12 tháng. Ta phân chia 40 học sinh vào 12 tháng đó. Nếu mỗi tháng có không quá 3 học sinh
được sinh ra thì số học sinh không quá: 3.12 = 36mà 36 < 40 : vô lý.
Vậy tồn tại một tháng có ít nhất 4 học sinh trùng tháng sinh ( trong bài này 40 thỏ là 40 học sinh, 12 lồng là 12 tên tháng). Bài 15:
Cho dãy số gồm 5 số tự nhiên bất kìa , a , a , a , a . Chứng minh rằng tồn tại một số chia hết cho 5 1 2 3 4 5
hoặc tổng của một số số liên tiếp trong dãy đã cho chia hết cho 5. Lời giải
Ta sẽ thành lập dãy số mới gồm 5 số sau đây: S = a 1 1
S = a + a 2 1 2
S = a + a + a 3 1 2 3
S = a + a + a + a 4 1 2 3 4
S = a + a + a + a + a 5 1 2 3 4 5
- Nếu một trong cách S (i = 1, ... )
5 chia hết cho 5 thì bài toán đã được chứng minh. i
- Nếu không có số nào chia hết cho 5 thì khi đem chia các số Si cho 5 sẽ được 5 số dư có giá trị từ 1 đến 4.
Có 5 số dư mà chỉ có 4 giá trị (5 thỏ, 4 lồng). Theo nguyên tắc Điriclê ít nhất phải có 2 số dư có cùng giá
trị. Hiệu của chúng chia hết cho 5. Hiệu này chính là tổng các ai liên tiếp nhau hoặc là ai nào đó. Bài 16: Trang 9
Với 39 số tự nhiên liên tiếp, hỏi rằng ta có thể tìm được một số mà tổng các chữ số của nó chia hết cho 11 hay không? Lời giải
Từ 20 số đầu tiên của dãy bao giờ ta cũng có thể tìm được 2 số mà chữ số hàng đơn vị là 0, và trong hai số
đó ít nhất phải có một số có chữ số hàng chục khác 9. Giả sử N là số đó, và ta gọi S là tổng các chữ số của N.
Ta có dãy số mới N ;N + 1;N + 2;... N + 9; N + 19là 11 số vẫn nằm trong 39 số cho trước
mà tổng các chữ số của chúng là S; S + 1; S + 2; ... ;S + 9; S + 10 . Đó là 11 số tự nhiên liên
tiếp, ắt phải có một số chia hết cho 11. Bài 17:
Chứng minh rằng trong 52 số tự nhiên tùy ý, chí ít cũng có một cặp gồm hai số sao cho hoặc tổng hoặc
hiệu của chúng chia hết cho 100. Lời giải
Để làm xuất hiện số "thỏ" và số "lồng ta làm như sau:
Trong tập hợp các số dư trong phép chia cho 100 ta lấy ra từng cặp số sao cho tổng các cặp đó bằng 100
và thành lập thành các nhóm sau:
(0 ; 0), (1 ; 99), (2 ; 98), (3 ; 97), (4 ; 96), (5 ; 95), (6 ; 94)... (49 ; 51), (50 ; 50).
Chú ý rằng sẽ có 50 cặp như vậy, ta thêm vào cặp (0, 0) sẽ có 51 cặp (51 lồng).
- Đem chia 52 số tự nhiên cho 100 sẽ có 52 số dư (52 thỏ).
- Có 52 số dư mà chỉ có 51 nhóm, theo nguyên tắc Điriclê ít nhất cũng phải có 2 số dư cùng rơi vào một nhóm.
Rõ ràng là cặp số tự nhiên ứng với cặp số dư này chính là hai số tự nhiên có tổng hoặc hiệu chia hết cho 100. (đpcm) Bài 18:
Chứng minh rằng trong 19 số tự nhiên bất kì ta luôn luôn tìm được một số mà tổng các chữ số của nó chia hết cho 10. Lời giải
Trước hết ta chứng minh rằng trong n số tự nhiên liên tiếp bao giờ cũng tồn tại một số chia hết cho n. (Các
bạn tự chứng minh điều này).
Với 19 số tự nhiên liên tiếp bất kì luôn luôn tồn tại 10 số liên tiếp có chữ số hàng chục như nhau, còn các
chữ số hàng đơn vị có giá trị từ 0 đến 9.
Vì thế tổng các chữ số của mỗi số trong 10 số này cũng làm thành dãy số gồm có 10 số tự nhiên liên tiếp,
do đó tồn tại một số chia hết cho 10 (đpcm). Bài 19: Trang 10
Một trường học có 1000 học sinh gồm 23 lớp. Chứng minh rằng phải có ít nhất một lớp có từ 44 học sinh trở lên Lời giải
Giả sử 23 lớp mỗi lớp có không quá 43 học sinh. Khi đó số học sinh là:
43.23 = 989 học sinh (ít hơn 1000 – 989 = 11 học sinh)
Theo nguyên lí Dirichlet phải có ít nhất một lớp có từ 44 học sinh trở lên
Nhận xét: Các cháu học sinh để ý, với dạng toán này, đề bài thường yêu cầu chứng minh có ít nhất 1 lớp,
(hoặc tương tự) có ít nhất bao nhiêu học sinh.
Như vậy, với dạng này điều quan trọng là chúng ta cần chỉ ra, đâu là thỏ, đâu là chuồng. Với bài số 1, đọc
đề xong cái là nhìn thấy ngay số học sinh (như là số thỏ) còn số lớp chính là số chuồng.
Nhận xét thêm về cách giải, thực ra nói là áp dụng nguyên lý Dirichle, nhưng các cháu có thể thấy chúng
ta đang đi chứng minh nguyên lý này, bằng việc giả sử ngược lại (phương pháp phản chứng).
Để hiểu rõ hơn, chúng ta đi tiếp tục bài 2. Bài 20:
Một lớp có 50 học sinh. Chứng minh rằng có ít nhất 5 học sinh có tháng sinh giống nhau Phân tích:
Đọc đề chúng ta thấy có học sinh, đề bài yêu cầu chứng minh học sinh có cùng tháng sinh. Việc “cùng
tháng sinh” ở đây có thể hiểu như “nhốt cùng chuồng”. Như vậy, chuồng ở đây chính là tháng sinh, còn
học sinh là“thỏ”.Hướng dẫn giải
Giả sử có không quá 4 học sinh có tháng sinh giống nhau
Một năm có 12 tháng, khi đó số học sinh của lớp có không quá: 12.4=48 (học sinh)
Theo nguyên lí Dirichlet phải có ít nhất 5 học sinh có tháng sinh giống nhau Bài 21:
Có sáu loại học bổng khác nhau. Hỏi rằng phải có ít nhất bao nhiêu sinh viên để chắc chắn rằng có ít ra là
6 người cùng nhận học bổng như nhau. Phân tích:
Bài toán này, đề bài không yêu cầu chúng ta chứng minh có ít nhất bao nhiêu gì đấy trong một gì đấy nữa.
Mà ngược lại, đề bài yêu cầu chúng ta tìm ít nhất số học sinh để thỏa mãn điều kiện có ít nhất như các bài trước.
Bây giờ chúng ta phân tích để nhận ra đâu là “thỏ”, đâu là “chuồng” nhé. Nào hãy chú ý yêu cầu đề bài “ít
nhất 6 người cùng nhận học bổng như nhau”, như vậy, người ở đây chính là “thỏ” còn loại học bổng chính
là “chuồng”. Để giải bài toán ngược này, chúng ta cũng làm tương tự, giả sử không thỏa mãn đề bài, tức
mỗi loại học bổng chỉ có tối đa 5 người…. Lời giải Trang 11
Giả sử mỗi loại học bổng chỉ có 5 người => số người là5.6 = 30 người.
Nếu ta lấy 31 người, khi đó theo nguyên lý Dirichle, tồn tại 1 loại học bổng mà có ít nhất 6 người nhận.
Nhận xét: Ta thấy 31 = 30 + 1, như vậy, ta chỉ việc tìm số lớn nhất để không thỏa mãn đề bài (chính là
5×6 = 30) cộng thêm 1 sẽ thành số nhỏ nhất thỏa mãn đề bài. Bài 22:
Trong 45 học sinh làm bài kiểm tra, không có ai bị điểm dưới 2, chỉ có 2 học sinh được điểm 10. Chứng
minh rằng ít nhất cũng tìm được 6 học sinh có điểm kiểm tra bằng nhau (điểm kiểm tra là một số tự nhiên) Phân tích:
Đề bài cho 45 học sinh, (chính là số “thỏ”). Nhưng số chuồng thì chúng ta chưa biết chính xác. Chúng ta
cần cẩn thận hơn với các dữ kiện “không có ai bị điểm dưới 2, chỉ có 2 học sinh được điểm 10″. Như vậy
các điểm chỉ cóthể từ 2 cho đến 10. Nhưng chỉ có 2 người được 10 tức là còn 43 người còn lại chỉ được
điểm từ 2 cho đến 9. (có 8 số – tương ứng 8 “chuồng”) Lời giải
Có 43 học sinh phân thành 8 loại điểm (từ 2 đến 9)
Giả sử trong 8 loại điểm đều là điểm của không quá 5 học sinh thì lớp học có:
5.8 = 40 học sinh, ít hơn 3 học sinh so với 43.
Theo nguyên lý Dirichlet tồn tại 6 học sinh có điểm kiểm tra bằng nhau. Bài 23:
Một lớp học có 50 học sinh, có duy nhất một học sinh thiếu nhiều bài tập nhất là thiếu 3 bài tập. Chứng
minh rằng tồn tại 17 học sinh thiếu 1 số bài tập như nhau (trường hợp không thiếu bài tập coi như thiếu 0 bài) Phân tích:
Bài này chúng ta để ý dữ kiện: “có duy nhất một học sinh thiếu nhiều bài tập nhất là thiếu 3 bài tập” Þ
các học sinh còn lại chỉ thiếu 0, 1, hoặc 2 bài tập (tức là có 3 loại thiếu bài tập). Loại bỏ học sinh duy nhất
thiếu 3 bài đi, còn lại 50 – 1 = 49 bạn. Lời giải
Ngoài bạn học sinh duy nhất thiếu 3 bài ta còn 49 bạn.
Giả sử mỗi loại bài tập có 16 học sinh.
Số học sinh không quá16.3 = 48 (thiếu 1 học sinh).
Theo nguyên lí Dirichlet có ít nhất 17 học sinh thiếu một số bài tập như nhau
Dạng 3: Sự tương hỗ Bài 1:
Có 5 đấu thủ thi đấu cờ, mỗi người đấu một trận với mỗi đấu thủ khác. Chứng minh rằng trong suốt thời
gian thi đấu, luôn tồn tại hai đấu thủ có số trận đã đấu bằng nhau. Lời giải Trang 12
Gọi 5 lồng 0, 1, 2, 3, 4 thứ tự chứa các đấu thủ đã đấu 0, 1, 2, 3, 4 trận. Cũng chú ý rằng hai lông 0 và 4
không thể cùng chứa người. Như vậy chỉ có 4 lồng, mà có 5 người, tồn tại 2 người trong cùng một lồng
tức là tồn tại hai đấu thủ có số trận đấu bằng nhau. Bài 2:
Cho 5 người tùy ý. CMR trong số đó có ít nhất 2 người có số người quen như nhau (hiểu rằng A quen B thì B quen A).
Phân tích: Chú trọng đến câu hỏi “2 người có số người quen như nhau”
Từ đó hiểu rằng 5 người đóng vai trò là số thỏ. Ta có thể tạo ra các lồng như sau: Lời giải
Gọi lồng 0 chứa những người có số người quen là 0.
Gọi lồng 1 chứa những người có số người quen là 1. …
Gọi lồng 4 chứa những người có số người quen là 4.
Như vậy ta có 5 lồng. Nếu lồng 0 có chứa ai đó thì lồng 4 phải trống. Ngược lại nếu lồng 4 có chứa ai đó thì lồng 0 phải trống.
Vậy thực chất chỉ có 4 lồng nhốt 5 thỏ nên có ít nhất 2 người ở cùng một phòng tức là hai người đó có số người quen như nhau. Bài 3:
Có 10 đội bóng thi đấu với nhau mỗi đội phải đấu một trận với các đội khác. CMR vào bất cứ lúc nào
cũng có hai đội đã đấu số trận như nhau (kể cả số trận đấu là 0).
Phân tích: Hiểu tương tự như bài toán trên. Lời giải
Gọi A0 là phòng chứa các đội có số trận đấu là 0.
Gọi A1 là phòng chứa các đội có số trận đấu là 1. ……………
Gọi A9 là phòng chứa các đội có số trận đấu là 9.
Nếu phòng A0 có ít nhất 1 đội thì phòng A9 không có đội nào và ngược lại phòng A9 có ít nhất 1 đội thì
phòng A0 không có đội nào.
Vậy thực chất chỉ có 9 phòng được sử dụng mà lại có 9 đội nên có ít nhất 2 đội vào chung một phòng hay
có ít nhất 2 đội có cùng số trận đấu như nhau. Bài 4:
Có 6 đội bóng thi đấu với nhau (mỗi đội phải đấu 1 trận với 5 đội khác). CMR vào bất cứ lúc nào cũng có
3 đội trong đó từng cặp đã đấu với nhau hoặc chưa đấu với nhau trận nào. Lời giải
Giả sử 6 đội bóng đó là A, B, C, D, E, F. Xét đội A: Trang 13
Theo nguyên lý Điriclê ta suy ra: A phải đấu hoặc không đấu với ít nhất 3 đội khác.
Không mất tính tổng quát, giả sử A đã đấu với B, C, D.
+ Nếu B, C, D từng cặp chưa đấu với nhau thì bài toán được chứng minh.
+ Nếu B, C, D có 2 đội đã đấu với nhau, ví dụ B và C thì 3 đội A, B, C từng cặp đã đấu với nhau.
Như vậy bất cứ lúc nào cũng có 3 đội trong đó từng cặp đã đấu với nhau hoặc chưa đấu với nhau trận nào. Bài 5:
Có 17 nhà toán học trao đổi với nhau về 3 vấn đề. Mỗi người tra đổi với một người về 1 vấn đề. CMR
cũng có ít nhất 3 nhà toán học trao đổi với nhau về cùng một vấn đề (A và B, B và C, C và A).
Phân tích: Tương tự như 17 điểm được nối với nhau bằng 3 màu à luôn tồn tại một tam giác với 3 cạnh
cùng màu tức là 3 nhà toán học trao đổi với nhau về cùng một vấn đề. Lời giải
Một nhà toán học trao đổi với 16 nhà toán học khác về 3 vấn đề Þ Theo nguyên lý Điricle có ít nhất 6
người sẽ được một người trao đổi về cùng một vấn đề, giả sử đó là vấn đề I.
6 người này lại trao đổi với nhau về 3 vấn đề:
+ TH1: Nếu có 2 người nào đó cùng trao đổi về vấn đề I thì bài toán được chứng minh.
+ TH2: Nếu không có 2 người nào cùng trao đổi về vấn đề 1 thì 6 người này chỉ trao đổi về 2 vấn đề II và III.
Một người trao đổi với 5 người còn lại về 2 vấn đề II và III. Theo nguyên lý Điricle có ít nhất 3 người
cùng được một người trao đổi về 1 vấn đề, giả sử đó là vấn đề II. Ba người này lại tiếp tục trao đổi với nhau:
+ TH1: Nếu có 2 người nào đó cùng trao đổi với nhau về vấn đề II thì bài toán được chứng minh.
+ TH2: Nếu không có 2 người nào cùng trao đổi với nhau về vấn đề II thì cả 3 người này trao đổi với nhau
về vấn đề III Þ Bài toán cũng đã được chứng minh.
Vậy luôn có ít nhất 3 nhà toán học trao đổi với nhau về cùng một vấn đề
Dạng 4: Sự sắp xếp Bài 1:
Cho một bảng vuông 4 x 4. Trên 16 ô của bảng, ta đặt 16 số tự nhiên từ 1 đến 16. Chứng minh rằng tồn tại
hai ô kề nhau (tức là hai ô có một cạnh chung ) sao cho hiệu các số ở hai ô đó lớn hơn hoặc bằng 3. Lời giải Trang 14
Chuyển từ một ô bất kì sang ô kề nó gọi là một bước. Xét hai ô ghi
số 1 và số 16 chuyển từ ô ghi số 1 đến ô ghi số 16 chỉ cần không quá
6 bước chuyển (nhiều nhất là 3 bước theo hàng ngang, 3 bước theo
hàng dọc). Tồn tại một bước chuyển có hiệu lớn hơn hoặc bằng 3.
Thật vậy giả sử tất cả các bước chuyển đều nhỏ hơn hoặc bằng 2 thì
từ số 1, qua không quá 6 bước chuyển tăng thêm không quá 12,
không đạt được đến số 16.
Vậy tồn tại hai ô kề nhau có hiệu các số của hai ô đó lớn hơn hoặc bằng 3. Bài 2:
Viết 16 số, mỗi số có giá trị bất kỳ là 1, 2, 3, 4. Ghép thành từng cặp
2 số được 8 cặp số. Chứng minh rằng tồn tại hai cặp số mà tồng các
số trong hai cặp đó bằng nhau. Lời giải
Tổng hai số của mỗi cặp trong 8 cặp số có giá trị nhỏ nhất là: 1 + 1 = 2, có giá trị lớn nhất là: 4 + 4 = 8.
Như vậy 8 tổng đó nhận 7 giá tri: (2, 3, 4, 5, 6, 7, 8). Theo nguyên lý Dirichlet, tồn tại hai tổng bằng nhau,
tức là tồn tại hai cặp có tổng bằng nhau.
Dạng 5: Bài toán hình học
Nguyên lí có thể mở rộng như sau: Nếu có m vật đặt vào n cái ngăn kéo và m > k.n thì có ít nhất một
ngăn kéo chứa ít nhất k + 1 vật. Với mở rộng này, ta còn có thể giải quyết thêm nhiều bài toán khác. Bài 1:
Trong tam giác đều có cạnh bằng 4 (đơn vị độ dài, được hiểu đến cuối bài viết) lấy 17 điểm. Chứng minh
rằng trong 17 điểm đó có ít nhất hai điểm mà khoảng cách giữa chúng không vượt quá 1. Lời giải
Chia tam giác đều có cạnh bằng 4 thành 16 tam giác đều có cạnh bằng 1 (hình 1).
Vì 17 > 16, theo nguyên lí Đi-rích-lê, tồn tại ít nhất một tam giác đều cạnh bằng 1 có
chứa ít nhất 2 điểm trong số 17 điểm đã cho. Khoảng cách giữa hai điểm đó luôn không vượt quá 1 (đpcm). Bài 2:
Trong một hình vuông cạnh bằng 7, lấy 51 điểm. Chứng minh rằng có 3 điểm trong 51 điểm đã cho nằm
trong một hình tròn có bán kính bằng 1. Lời giải
Chia hình vuông cạnh bằng 7 thành 25 hình vuông bằng nhau, cạnh của mỗi hình
vuông nhỏ bằng 5/7 (hình 2). Trang 15
Vì 51 điểm đã cho thuộc 25 hình vuông nhỏ, mà 51 > 2.25 nên theo nguyên lí Đi-rích-lê, có ít nhất một
hình vuông nhỏ chứa ít nhất 3 điểm (3 = 2 + 1) trong số 51 điểm đã cho. Hình vuông cạnh bằng có bán
kính đường tròn ngoại tiếp là: 2 2  7   7  +      5   5  98 = 1 (đpcm) 2 100
Hình tròn này chính là hình tròn bán kính bằng 1, chứa hình vuông ta đã chỉ ra ở trên. Bài 3:
Trong mặt phẳng cho 2003 điểm sao cho cứ 3 điểm bất kì có ít nhất 2 điểm cách nhau một khoảng không
vượt quá 1. Chứng minh rằng: tồn tại một hình tròn bán kính bằng 1 chứa ít nhất 1002 điểm. Lời giải
Lấy một điểm A bất kì trong 2003 điểm đã cho, vẽ đường tròn C1 tâm A bán kính bằng 1.
+ Nếu tất cả các điểm đều nằm trong hình tròn C1 thì hiển nhiên có đpcm.
+ Nếu tồn tại một điểm B mà khoảng cách giữa A và B lớn hơn 1 thì ta vẽ đường tròn C2 tâm B bán kính bằng 1.
Khi đó, xét một điểm C bất kì trong số 2001 điểm còn lại. Xét 3 điểm A, B, C, vì AB > 1 nên theo giả
thiết ta có AC ≤ 1 hoặc BC ≤ 1. Nói cách khác, điểm C phải thuộc C1 hoặc C2.
=> 2001 điểm khác B và A phải nằm trong C1 hoặc C2.
Theo nguyên lí Đi-rích-lê ta có một hình tròn chứa ít nhất 1001 điểm. Tính thêm tâm của hình tròn này thì
hình tròn này chính là hình tròn bán kính bằng 1 chứa ít nhất 1002 điểm trong 2003 điểm đã cho. Bài 4:
Cho hình bình hành ABCD, kẻ 17 đường thẳng sao cho mỗi đường thẳng chia ABCD thành hai hình thang
có tỉ số diện tích bằng 1/3 . Chứng minh rằng, trong 17 đường thẳng đó có 5 đường thẳng đồng quy. Lời giải
Gọi M, Q, N, P lần lượt là các trung điểm của AB, BC, CD, DA (hình 3).
Vì ABCD là hình bình hành => MN // AD // BC ; PQ // AB // CD.
Gọi d là một trong 17 đường thẳng đã cho. Nếu d cắt AB tại E ; CD tại F ; PQ tại
L thì LP, LQ lần lượt là đường trung bình của các hình thang AEFD, EBCF.
Ta có: S(AEFD) / S(EBCF) = 1/3 hoặc S(EBCF) / S(EBFC) = 1/3
=> LP / LQ = 1/3 hoặc là LQ / LP = 1/3.
Trên PQ lấy hai điểm L1, L2 thỏa mãn điều kiện L1P / L1Q = L2Q / L2P = 1/3 khi đó L trùng với L1 hoặc L
trùng với L2. Nghĩa là nếu d cắt AB và CD thì d phải qua L1 hoặc L2.
Tương tự, trên MN lấy hai điểm K1, K2 thỏa mãn điều kiện K1M / K1N = K2N / K2M = 1/3 khi đó nếu d
cắt AD và BC thì d phải qua K1 hoặc K2. Trang 16
Tóm lại, mỗi đường thẳng trong số 17 đường thẳng đã cho phải đi qua một trong 4 điểm L1 ; L2 ; K1 ; K2.
Vì 17 > 4.4 nên theo nguyên lí Đi-rích-lê, trong 17 đường thẳng đó sẽ có ít nhất 5 đường thẳng (5 = 4 + 1)
cùng đi qua một trong 4 điểm L1 ; L2 ; K1 ; K2 (5 đường thẳng đồng quy, đpcm).
Dạng 6: Sự trùng lặp
- Học sinh thuộc nội dung nguyên lý. Đọc bài toán và phân biệt được yếu tố nào đóng vai trò là “thỏ”, yếu
tố nào đóng vai trò là “lồng”. Học sinh chỉ ra được số thỏ, số lồng.
- Cách phân biệt đơn giản nhất: Số thỏ luôn lớn hơn số lồng. Bài 1:
Trong 45 học sinh làm bài kiểm tra không có ai bị điểm dưới 2, chỉ có 2 học sinh được điểm 10. CMR ít
nhất cũng tìm được 6 học sinh có điểm kiểm tra bằng nhau (điểm kiểm tra là một số tự nhiên từ 0 đến 10).
Phân tích: “thỏ” là 43 học sinh, “lồng” là các loại điểm từ 2 đến 9. Lời giải
Có 45 – 2 = 43 (học sinh) được 8 loại điểm từ 2 đến 9. Do 43 : 8 = 5 (dư 3).
Theo Nguyên lý Điricle có ít nhất 6 học sinh có điểm kiểm tra bằng nhau. Bài 2:
Một trường học có 24 lớp gồm 900 học sinh. Chứng minh rằng có một lớp với sĩ số 38 học sinh trở lên.
Phân tích: Chia 900 học sinh vào 24 lớp có ý nghĩa tương tự như nhốt 900 con thỏ vào 24 cái lồng. Từ đó
có thể áp dụng ngay nội dung nguyên lý để giải bài toán: Lời giải
Có 900 học sinh được chia vào 24 lớp, mà 900: 24 = 37 (dư 12)
Theo nguyên lý Điricle sẽ tồn tại một lớp có từ 37 + 1 = 38 (học sinh) trở lên. Bài 3:
Trong lớp học có 30 học sinh. Khi viết chính tả một em phạm 14 lỗi, các em khác phạm số lỗi ít hơn.
CMR có ít nhất 3 học sinh mắc số lỗi bằng nhau (kể cả những người mắc 0 lỗi).
Phân tích: Trong bài toán này “thỏ” là 29 học sinh (trừ đi 1 em mắc 14 lỗi), “lồng” là các loại lỗi (gồm
14 loại: 0 lỗi, 1 lỗi, 2 lỗi, …, 13 lỗi). Lời giải
Có 30 học sinh trong đó 1 em phạm 14 lỗi, số còn lại là 29 em phạm các lỗi từ 0 đến 13 lỗi (14 loại lỗi). Do 29: 14 = 2 (dư 1)
Theo Nguyên lý Điricle có ít nhất 3 em mắc cùng số lỗi như nhau. Bài 4:
Trong một kỳ thi toán học có 6 thí sinh được vào chung khảo. Thể lệ của cuộc thi như sau: Mỗi thí sinh
phải giải 5 bài toán. Mỗi bài toán đúng được tính 4 điểm. Mỗi bài toán sai hoặc không làm được đều bị trừ Trang 17
2 điểm. Hãy chứng tỏ rằng trong 6 thí sinh đó có ít nhất 2 thí sinh bằng điểm nhau. Biết rằng điểm thấp nhất là điểm 0.
Phân tích: số “thỏ” dường như là 6 học sinh, nhưng “lồng” là gì nhỉ? Ta phải đặc biệt chú ý đến nội
dung câu hỏi ít nhất 2 thí sinh bằng điểm nhau” liên tưởng đến nội dung nguyên lý nó giống như 2
thỏ nhốt chung một lồng. Từ đó tìm ra yếu tố lồng ở đây là số điểm đạt được. Giải
Vì mỗi thí sinh phải giải 5 bài toán. Mỗi bài toán đúng được tính 4 điểm. Mỗi bài toán sai hoặc không làm
được đều bị trừ 2 điểm nên ta có 5 trường hợp sau:
Nếu đúng 5 bài thì số điểm được là: 5. 4 = 20 (điểm).
Nếu đúng 4 bài thì số điểm được là: 4. 4 - 2 = 14 (điểm).
Nếu đúng 3 bài thì số điểm được là: 3. 4 – 4 = 8 (điểm).
Nếu đúng 2 bài thì số điểm được là: 2. 4 – 6 = 2 (điểm).
Nếu đúng 1 bài hoặc không đúng bài nào thì đều được 0 điểm.
Như vậy có 6 thí sinh dự thi nhưng chỉ có 5 loại điểm nên theo nguyên lý Điricle sẽ có ít nhất 2 thí sinh bằng điểm nhau.
PHẦN III.BÀI TOÁN TRONG ĐỀ THI HSG6 Bài 1:
Trong một phòng họp có n người, bao giờ cũng tìm được 2 người có số người quen trong số những người dự họp là như nhau. Phân tích:
Phòng họp có n người, có thể coi là n “thỏ” rồi này. Bây giờ chúng ta xác định đâu là “chuồng”. Hãy đọc
kỹ đề bài yêu cầu gì, chúng ta sẽ nhìn ra “chuồng” ngay. “tìm được 2 người có số người quen trong số
những người dự họp là như nhau” => số người quen giống nhau, hay chính là nhốt cùng “chuồng”. Như
vậy, số người quen chính là số “chuồng”.
Ta thấy 1 người có thể quen với 0 người, 1 người, ….hoặc nhiều nhất là n-1 người trong cuộc họp…. Lời giải
Số người quen của mỗi người trong phòng họp nhận các giá trị từ 0 đến n – 1. Rõ ràng trong phòng
không thể đồng thời có người có số người quen là 0 (tức là không quen ai) và có người có số người quen
n – 1(tức là quen tất cả). Vì vậy theo số lượng người quen, ta chỉ có thể phân n người ra thành n – 1 nhóm.
Vậy theo nguyên lí Dirichlet tồn tai một nhóm có ít nhất 2 người, tức là luôn tìm được ít nhất 2 người có
số người quen là như nhau. Bài 2: Trang 18
Trong một lưới ô vuông kích thước 5.5, người ta điền ngẫu nhiên vào các ô một trong các giá trị 0,1 hoặc
2, sau đó tính tổng tất cả các ô theo hàng ; theo cột và theo hai đường chéo. Chứng minh rằng tồn tại ít
nhất hai tổng có giá trị bằng nhau. Phân tích:
Hãy đọc kỹ đề bài yêu cầu, chúng ta sẽ thấy “thỏ” và “chuồng”
“Tồn tại ít nhất 2 tổng có giá trị bằng nhau” Þ thỏ chính là tổng (hàng ngang, dọc, chéo), còn giá trị chính
là “chuồng”. Vấn đề của chúng ta là chúng ta cần đi tìm các giá trị có thể của tổng. Ta thấy một tổng 5 ô
sẽ có giá trị nhỏ nhất là 0, lớn nhất là 10. Lời giải
Gọi các tổng lần lượt là S1,S2,..S12.
Có tất cả 12 tổng. Ta nhận thấy rằng các tổng này chỉ có thể nhận các giá trị là {0, 1, 2…., 9, 10}. Có tất
cả 11 giá trị khác nhau. Từ đó, theo nguyên lý Dirichlet ta suy ra điều cần chứng minh. Bài 3:
Giả sử trong một nhóm 6 người mỗi cặp hai hoặc là bạn hoặc là thù. Chứng tỏ rằng trong nhóm có ba
người là bạn lẫn nhau hoặc có ba người là kẻ thù lẫn nhau. Lời giải
Gọi A là một trong 6 người. Trong số 5 người của nhóm hoặc là có ít nhất ba người là bạn của A hoặc có
ít nhất ba người là kẻ thù của A, điều này suy ra từ nguyên lí Dirichlet, vì những người khác chỉ có thể là bạn hoặc thù của A.
Trong trường hợp đầu ta gọi B,C,D là bạn của A. nếu trong ba người này có hai người là bạn thì họ cùng
với A lập thành một bộ ba người bạn lẫn nhau, ngược lại, tức là nếu trong ba người B,C,D không có ai là
bạn ai cả thì chứng tỏ họ là bộ ba người thù lẫn nhau.
Tương tự có thể chứng minh trong trường hợp có ít nhất ba người là kẻ thù của A. (ĐPCM) Bài 4:
Có 5 đấu thủ thi đấu cờ, mỗi người đấu một trận với mỗi đấu thủ khác. Chứng minh rằng trong suốt thời
gian thi đấu, luôn tồn tại hai đấu thủ có số trận đã đấu bằng nhau. Lời giải
Ta có số trận đã đấu của mỗi người có thể là 0,1,2,3,4. Nhưng vì không thể có cùng lúc một người đã đấu
4 trận và một người chưa đấu trận nào, nên có tối đa 4 loại số trận đã đấu.
Vận dụng nguyên lý Dirichlet ta có ít nhất có 2 người có cùng số trận đã đấu. Bài 5:
Có 6 học sinh làm một bài thi gồm 6 câu hỏi. Nếu trả lời đúng được 2 điểm, trả lời sai bị trừ 1 điểm. Nếu
số điểm bị trừ nhiều hơn số điểm đạt được thì tính bị 0 điểm. Hỏi có thể luôn có 2 học sinh bằng điểm nhau được hay không???
Phân tích và gợi ý giải: Trang 19
Bài này đề bài lại hỏi theo kiểu có hay không, nhưng chúng ta hãy bình tình. Nếu một khi chúng ta đã hiểu
bản chất của bài toán dạng này thì sẽ không gì làm chúng ta sợ hay mất tự tin được cả.
“Hai học sinh bằng điểm nhau”Þ Học sinh chính là “thỏ”, điểm chính là “chuồng”.
Vấn đề bài toán trở thành đi tìm số điểm có thể (số chuồng), từ đó sẽ giúp chúng ta trả lời được câu hỏi của đề bài.
Đề thi gồm 6 bài, xảy ra các trường hợp sau:
- Đúng hết 6 câu => 12 điểm
- Đúng 5 câu, sai 1 câu => 5×2 -1 = 9 điểm
- Đúng 4 câu, sai 2 câu => 4×2 -2×1 = 6 điểm
- Đúng 3 câu, sai 3 câu => 3×2 – 3×1 = 3 điểm
- Đúng 2 câu, sai 4 câu => 2×2 – 4x 1 = 0 điểm
- Đúng dưới 2 câu => dễ thấy sẽ bị 0 điểm.
Nhìn lại ta thấy chỉ có 0,3,6,9,12 điểm tức là chỉ có 5 loại điểm, trong khi có 6 học sinh => có 2 học sinh cùng điểm. Trang 20