TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2 KHOA TOÁN
===£OBŨIGS===
TRẦN THỊ THU HẰNG
MỘT SỐ NGUYÊN LÍ cơ BẢN
KHÓA LUÂN TỐT NGHIÊP ĐAI HOC • • • • Chuyên ngành: Đại
số
Người hướng dẫn khoa học ThS. DƯƠNG THI
LUYẾN
HÀ NỘI - 2014
MỤC LỤC
Sau một thời gian nghiên cứu cùng với sự giúp đỡ của các thầy cô giáo và
các bạn sinh viên, khóa luận của tôi đã được hoàn thành. Tôi xin bày tỏ lòng
biết ơn sâu sắc tới cô giáo THẠC SĨ

Dương THỊ LUYẾN

- người đã trực tiếp
hướng dẫn, chỉ bảo tận tình giúp đỡ tôi hoàn thành khóa luận này.
Tôi cũng xin gửi lời cảm ơn tới tất cả các thầy cô giáo trong tổ Đại số,
khoa Toán và thư viện trường Đại Học Sư Phạm Hà Nội 2 đã tạo điều kiện giúp
đỡ tôi hoàn thành khóa luận.
Tôi xin chân thành cảm ơn!
Hà Nội, tháng 5 năm 2014 Sinh viên
Trần Thị Thu Hằng
Tôi xin cam đoan rằng khóa luận này là kết quả nghiên cứu tìm tòi của
riêng tôi và hoàn thành trên cơ sở những kiến thức đã học và tham khảo các tài
liệu. Kết quả nghiên cứu này không hoàn toàn trùng với bất cứ công trình
nghiên cứu nào từng được công bố.
Hà Nội, tháng 5 năm 2014 Sinh viên
Trần Thị Thu Hằng
LỜI CẢM ƠN

G.lejeune-Dirich tên đầy đủ là Johnn Peter Gustar Lejeune Dirichlet, sinh
ra tại Duren (Đức) vào ngày 13 tháng 2 năm 1805.
Nguyên lí Dirichlet được phát biểu đầu tiên vào năm 1834, đưa ra một
nguyên tắc về phân chia phần tử các lớp.
1.1. Nguyên lí Dirỉchlet
Nguyên lí Dirichlet còn gọi là “nguyên lí chuồng bồ câu” hoặc “nguyên lí
ngăn kéo” hoặc “nguyên lí nhốt thỏ vào lồng”. Nội dung của nguyên lí này
đơn giản và dễ hiểu nhưng lại có tác dụng rất lớn trong giải toán. Nhiều khi có
những bài toán, người ta đã dùng rất nhiều phương pháp toán học để giải mà
vẫn chưa đi đến kết quả, nhưng nhờ nguyên lí Dirichlet mà bài toán trở nên dễ
dàng giải quyết.
1.1.1. Nguyên lí Dirichlet được phát biểu dưới dạng bài toán sau
đây
Nếu đem nhốt m- con thỏ vào n- chiếc lồng, với m > n thì ít nhất
cũng có một lồng nhốt không ít hơn hai con thỏ.
Hoặc là, nếu đem xếp m- đồ vật vào n- ô ngăn kéo, với m > n, thì ít nhất
cũng phải có một ô ngăn kéo chứa không ít hơn hai đồ vật.
1.1.2. Nguyên líDỉrỉchlet mở rộng
Nếu nhốt n- con thỏ vào m > 2 cái chuồng thì tồn tại một chuồng có
ít nhất [
n+m
- ] con thỏ, ở đây kí hiệu [a] để chỉ phần nguyên của số a.
Nguyên lí Dirichlet tưởng chừng đơn giản như vậy nhưng nó là một công
cụ rất hiệu quả dùng để chứng minh nhiều kết quả sâu sắc của Toán học. Nó
đặc biệt có nhiều áp dụng trong nhiều lĩnh vực khác nhau của Toán học.
Nguyên lí này trong nhiều trường hợp người ta dễ dàng chứng minh được sự
tồn tại mà không đưa ra được phương pháp tìm được vật cụ thể, nhưng trong
thực tế ta chỉ cần chỉ ra sự tồn tại là đủ.
Nguyên lí Dirichlet thực chất là một định lí về tập hữu hạn. Người ta chỉ
có thể phát biểu chính xác nguyên lí này dưới dạng sau.

1 = [—- + 11 = 1 + 1 con thỏ, thì số thỏ trong mỗi chuồng
m m m
đều nhỏ hơn hoặc bằng [^—4 con. Từ đó suy ra tổng số con thỏ không
m
vượt quá m.[—-] > n-1 con. Điều này vô lí vì có n-con thỏ. Vậy giả thiết
m
phản chứng là sai.
=> Điều phải chứng minh.
1.3. Cơ sở Toán hoc
■
Nguyên lí Dirichlet đơn giản như vậy, nhưng nó là một công cụ hết sức có
hiệu quả dùng để chứng mình nhiều kết quả hết sức sâu sắc của toán học.
Nguyên lí Dirichlet cũng được áp dụng cho các bài toán của hình học, điều đó
được thể hiện qua hệ thống bài tập sau
Để sử dụng nguyên lý Dirichlet ta phải làm xuất hiện tình huống nhốt
“thỏ” vào “chuồng” và thoả mãn các điều kiện :
+ Số ‘thỏ” phải nhiều hơn số “chuồng”
+ “Thỏ” phải được nhốt hết vào các “chuồng”, nhưng không bắt buộc
chuồng nào cũng phải có thỏ.
Thường phương pháp Dirichlet được áp dụng kèm theo phương pháp
phản chứng. Ngoài ra nó còn có thể áp dụng với các phép biến hình.
1.4. Bài tập áp dụng
1.4.1. Áp dụng nguyên líDirichlet vào suy luận logic
BÀI 1.

Trong một lớp có 30 học sinh. Chứng minh rằng trong số học sinh
ta sẽ tìm thấy 2 học sinh có tên bắt đầu bằng một chữ cái giống nhau.
Giải
Bảng chữ cái Tiếng Việt gồm 29 chữ cái, trong lúc đó số học sinh lớn hơn
(30 học sinh).

1999 tức ai nhận 2000 giá ưị i = 1, ,2001.
Vậy phải tồn tại ak = a
m
, k, m = 1, , 2001. Nếu mỗi người đều quen ít
nhất 1 người khác trong nhóm thì ta có: 1< aị < 2000, i = 1, , 2000. Do đó
cũng tồn tại a
k
= a
m
.
7
Vậy trong 2001 người bất kì luôn có ít nhất 2 người có số người quen
bằng nhau (số người quen chỉ tính trong số 2001 người này).
BÀI

3. Giả sử có 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à thù
lẫn nhau.
Giải
Gọi A là một trong 6 người. Trong số 5 người của nhóm hoặc có ít nhất 3
người là bạn của A hoặc có ít nhất 3 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 là 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 3 người này
có 2 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.
=> Điều phải chứng minh.
BÀI 4.

bằng nhau (kể cả những người mắc 0 lỗi).
BÀI 2.

Cho 5 người tùy ý. Chứng minh rằng trong số đó có ít nhất 2
người có số người quen như nhau trong số 5 người đã chọn (hiểu rằng A và B
quen nhau thì B quen A)
BÀI

3. Trong một giải bóng đá có 10 đội tham gia, bất cứ hai đội nào
trong số đó cũng phải đấu với nhau một trận. Chứng minh rằng tại bất cứ thời
điểm nào cũng có hai đội đã đấu được cùng số trận.
1.4.2. Áp dụng nguyên líDirichlet vào bài toán chia hết
Trong các phép tính trên số nguyên thì phép chia hết rất đặc biệt. Phép
chia có hàng loạt các tính chất mà phép toán còn lại không có. Chẳng hạn, các
phép toán cộng, ưừ, nhân đều thực hiện với số 0, còn phép chia thì không thể.
Vì những lí do đặc biệt đó mà ưong Toán học xây dựng hẳn một lí thuyết về
phép chia. Những bài toán sau có liên quan mật thiết giữa phép chia và nguyên
lí Dirichlet.
BÀI 1.

Cho 7 số tự nhiên bất kì. Chứng minh rằng bao giờ cũng có thể
chọn ra hai số mà hiệu của chúng chia hết cho 6.
Giải
9
Ta biết rằng nếu 2 số tự nhiên chia hết cho cùng một số dư thì hiệu của
chúng chia hết cho số đó. Vậy để chứng minh bài toán ta phải chứng minh
trong 7 số đó có ít nhất 2 số chia cho 6 có cùng số dư chỉ có thể là một trong 6
số: 0, 1,2, 3, 4, 5.
Lấy 7 số tự nhiên chia cho 6 thu được 7 số dư thuộc 6 số khác nhau. Vậy
theo nguyên lí Dirichlet thì ít nhất cũng có 2 số chia hết cho 6 có cùng số dư.

- 1) : 19 hay 10
mn
chia cho 19 dư 1.
Rõ ràng 10
m n
là một số của dãy đã cho (vì 1 < n < m <20).
Nhân xét. Qua bài toán này ta thấy tồn tại một số tự nhiên k > 1 để
cho
(10
k
- 1) i 19.
BÀI

3. Chứng minh rằng tồn tại một số là bội số của 19 và tổng các chữ
số của số đó bằng 19.
Giải
Ta phải chứng minh tồn tại một số chia hết cho 19 và tổng các chữ số của
số đó bằng 19. Theo trên ta đã chứng minh được rằng (10
k
- 1) : 19. Ta có
10
2k
- 1= 10
2k
- 10
k
+10
k
- 1 = 10
fe

19k
- 1 ! 19.
Vậy 10
k
- 1 + 10
2k
- 1 + 10
3k
- 1 + + 10
19k
- 1 : 19 Hay (10
k
+
10
2k
+ 10
3k
+ + 10
19k
)- 19 i 19
1
Hay 1000 0 + 1000 0 + - + 1000 0 : 19
k chữ

số 0 2kchữsÔ0

19 chữ số 0
Tổng ở vế trái của 19 số hạng và tổng các chữ số của nó đúng bằng
Vậy tồn tại một số là bội của 19 có tổng các chữ số bằng 19.
BÀI 4.

Vậy tồn tại một bội của 13 gồm toàn chữ số 2.
Nhân xét Bài toán trên tương đương với bài toán “Chứng minh rằng tồn tại
một số tự nhiên gồm toàn chữ số 2 và chia hết cho 13”
Bài toán vẫn đúng nếu thay số 2 bằng bất kì số nào.
BÀI

5. Cho 10 số nguyên dương U1, ,U10. Chứng minh rằng tồn tại các
số Ci € {—1,0,1}, i =1,10, không đồng thời bằng 0 sao cho
số Eí®! CịUị : 1023.
Giải
Xét tất cả các số có dạng Aj = 5^°! BỊUỊ
trong đó bi e {0,1}, i = l, 10, j = 1,1024.
Rõ ràng có tất cả 2
10
= 1024 số Aj, j = 1,1024. Như vậy khi chia 1024 số
Aj này cho 1023 thì theo nguyên lí Dirichlet có ít nhất 2 số A
k
, A
h
, к Ф

h sao
cho A
k
= A
h
(mod 1023). Giả sử A
k
, A
h

€ {0,1}, bhi e {0,1} nên
Ci € {-1,0 1}.
Mặt khác, do A
k
Ф

A
h
nên Cj không thể tồn tại đồng thời bằng 0,
Vi = 1,10. Như thế ta đã chứng minh được sự tồn tại của 10 số
Cị € {—1,0,1} không đồng thời bằng 0 sao cho
Eí®! qUi i 1023.
=> Điều phải chứng minh.
Bài tập đề nghị
Bài 1. Cho dãy số 10, 10
2
, 10
3
, ,10
2
°. Chứng minh rằng tồn tại một số
chia hết cho 19 dư 1.
Bài 2. Nam là một vận động viên chơi cờ. Để luyện tập mỗi ngày anh
chơi cờ ít nhất một ván. Để khỏi mệt mỗi tuần anh chơi không quá 12 ván.
Chứng minh rằng tồn tại một số ngày liên tiếp trong đó anh chơi đúng 20 ván.
Bài 3. Chứng minh rằng trong 27 số nguyên tùy ý nhỏ hơn 1000 có thể
chọn ra được 2 số có ước chung lớn nhất khác 1
1.4.3. Áp dụng nguyên líDỉrỉchlet vào hình học tổ hợp
Phàn này, tôi xin trình bày phương pháp sử dụng nguyên lí Dirichlet để
giải các bài toán hình học tổ hợp.

1
H « • K
1 < w
ầ
J
Nhân xét: Các đường thẳng đã cho không thể đi qua trung điểm các cạnh
hình vuông ABCD bởi vì ngược lại thì hình vuông sẽ bị phân thành
1
1
2 phần tam giác và ngũ giác.
Giả sử một đường thẳng ưong số đó cắt cạnh BC tại M và cắt cạnh AD tại
N. Các hình thang ABMN và CDNM có chiều cao bằng nhau nên từ giả thiết
suy ra MN chia đoạn thẳng nối trung điểm p, Q của AB và CD theo tỉ lệ 2:3.
Dễ thấy chỉ có 4 điểm chia 2 đường trung bình của hình vuông ABCD
theo tỉ lệ 2:3 là I, J, K, H, có 9 đường thẳng đi qua 4 điểm này, theo nguyên lí
Dirichlet, phải có ít nhất 3 đường thẳng cùng đi qua 1 điểm.
Bài 3. Trong một tờ giấy hình vuông bằng giấy có cạnh bằng 12 cm có 31
lỗ kim châm. Chứng minh rằng ta vẫn có thể cắt từ tờ giấy này ra một hình
tròn có bán kính 1 cm mà không chứa một lỗ kim châm nào.
Giải
Lấy mỗi lỗ kim là tâm dựng một hình tròn bán kính lcm. Tổng diện tích
của 31 hình tròn này sẽ là 31 7T

nhỏ hơn diện tích của hình vuông cạnh 10 cm.
Do đó phải có một điểm M trong hình vuông cạnh 10 cm (là hình vuông thu
được từ hình vuông cạnh 12 cm đã cho bằng cách thu hẹp các chiều lcm) và
không nằm trong 31 hình tròn bán kính được dựng như đã trình bày ở trên. Lấy
điểm M làm tâm ta cắt một hình tròn bán kính lcm, thì hình tròn này nằm hoàn
toàn trong hình vuông đã cho có cạnh dài 12 cm và không chứa một lỗ kim
châm nào cả.

một hình tròn có bán kính r cm mà không chứa một lỗ kim châm nào.
1
1
BÀI 4.

Trên mặt phẳng cho 25 điểm. Biết rằng 3 điểm bất kì ữong số đó
luôn tồn tại 2 điểm cách nhau nhỏ hơn 1. Chứng minh rằng tồn tại hình tròn
bán kính 1 chứa không ít hơn 13 điểm đã cho.
Giải
Lấy A là một trong 25 điểm đã cho. Xét hình tròn Oi (A; 1) tâm A, bán
kính 1. Chỉ có 2 trường hợp sau xảy ra:
THI. Nếu các điểm đã cho nằm ưong (Oi) thì kết luận của bài toán hiển
nhiên đúng.
TH2. Tồn tại điểm в -Ф-

А (В thuộc trong số 25 điểm đã cho) sao cho В
Ể (Oi) nên AB > 1. Xét hình tròn O2 (B;l) tâm B, bán kính 1. Lấy с là điểm bất
kì ữong số 25 điểm đã cho sao cho с ^ А, о в. Theo giả thiết (và dựa vào AB >
1) nên min{CVl, CB

} < 1. Vì thế с € (Ol) hoặc с e (0
2
). Điều khẳng định này
chứng tỏ rằng các hình tròn (Oi) và (O2) chứa tất cả 25 điểm đã cho. Vì thế
theo nguyên lí Dirichlet, có ít nhất một ưong hai hình ưòn nói trên chứa không
ít hơn 13 điểm đã cho.
=> Điều phải chứng minh.
Chú V Bài toán trên có dạng tổng quát như sau Cho 2n + 1 điểm ưên mặt
phẳng (n > 3). Biết rằng trong 3 điểm bất kì trong 2n + 1 điểm luôn tồn tại 2
điểm cách nhau nhỏ hơn 1. Khi đó tồn tại hình tròn bán kính 1 chứa không ít

cạnh A
n+
1 A
n+
2, , A
2n
Ai (n cạnh).
Như vậy còn n - 1 đường thẳng chỉ có thể cắt nhiều nhất n - 1 cạnh trong n
cạnh trên nên tồn tại 1 cạnh không có điểm trong chung với các đường thẳng
kẻ được.
Bài tập đề nghị
Bài 1. Cho tam giác đều ABC có 3 cạnh bằng 1. Đánh dấu 5 điểm phân
biệt bất kì trong tam giác ABC. Chứng minh rằng tồn tại ít nhất 2 điểm trong
số đó mà khoảng cách giữa chúng nhỏ hơn 0.5
BÀI

2. Bên trong hình vuông có cạnh bằng 1, lấy bất kì 51 điểm phân
biệt. Chứng minh rằng phải tồn tại ít nhất là điểm trong 51 điểm này nằm
trong một hình tròn có bán kính bằng
Bài 3. Bên trong hình tròn (O, R) có diện tích bằng 8, người ta lấy 17
điểm phân biệt bất kì. Chứng minh rằng bao giờ cũng tìm được ít nhất là 3
điểm tạo thành tam giác có diện tích bé hơn 1.
Chương 2 NGUYÊN LÍ cực HẠN
2.1. Nguyên lí cực hạn
Song song với việc sử dụng nguyên lí khác như nguyên lí Dirichlet hay
quy nạp toán học để tìm lời giải cho các bài toán khá hóc búa, nguyên lí cực
hạn cũng được xem là một phương pháp rất hay, được yận dụng một cách linh
hoạt trong việc khảo sát một tập hợp hữu hạn hay vô hạn phần tử mà trong nó
tồn tại giá trị lớn nhất hoặc giá ưị nhỏ nhất.
Nguyên lí cực hạn được phát biểu đơn giản như sau:

d
= m. Tìm GTLN - GTNN của
biểu thức s = Xi
2
+ x
2
2
+ +x
d
2
.
Giải
Gọi G là tập tất cả các giá trị của của s. Ta có G Ф

0 và hữu hạn nên theo
nguyên lí cực hạn thì luôn tồn tại N là số nhỏ nhất của G và L là số lớn nhất
của G.
1
1
Giả sử (a
b
a
2
, ,a
d
) nhận giá trị L. Ta sẽ chứng minh rằng các số a
b
a
2
, , a

2
< < ad và m = dn + к (0 < к < d). Do đặc điểm của
dãy ai < a
2
< < a
d
nên ai = a
2
= = a
d
_
k
,
^d-k+1 = ũd-k+2 — . . a d = n + 1.
Vậy GTNN của N = (d - k).n
2
+ k(n + l)
2
.
Giả sử (bi, b
2
, ,b
d
) làm cho s nhận GTLN. Ta sẽ chứng minh bi
=
b
2
= = b
d
_i = 1, b

d
= m và làm cho các giá ưị của s lớn hơn L (mâu
thuẫn).
Vậy GTLN L = (d - 1) + (m - d +1)
2
.
Tồng quát: Cho m và d là các số nguyên dương với m > d > 2. Giả sử
Xi, ,x
d
là các biến nguyên dương sao cho
Xi + + x
d
= m. Tìm GTLN và GTNN của biểu thức
s = Xi
k
+ + x
d
\
Bài 2. Cho m> d là một số nguyên dương. Giả sử x
b
,x
d
là các biến
nguyên dương sao cho: XiX
2
Xd = m. Tìm GTLN của
s =
Xl
3
+ X2

+ c
3
= ai
3
.a
2
3
> a + ai
3
+ a
2
3
. Như vậy ta tìm
được các số nguyên dương b, c, a
3
, , a
d
thỏa mãn b.c.a
3
a
d
= m làm cho giá trị
của s lớn hơn Ư (mâu thuẫn).
Vậy ai = m, a
2
= = a
d
= 1 và u = m
3
+ (d - 1).

d
_i = 1, a
d
= m - d +1.
Thật vậy, giả sử ad < m +1 -d, khi đó phải tồn tại ai > 1, i Ф

d. Đặt b
d
= a
d
+ 1 ; bi = ai - 1 thì ai + + ai-1 + bi + a
i+
i + + bd = m và
i.bi + d.bd = i(ai - 1) + d(a
d
+ 1) = i.ai + d.a
d
+d -1 > i.aị + d.a
d
. Như vậy
ta tìm được các số nguyên dương
ai, ,ai_i, bi, b
d
thỏa mãn
ai + + ai_i + bi + ai+i+ + b
d
= m và làm cho giá trị của s lớn hơn N
(mâu thuẫn).
Vậy ai = a
2

+ + bi_i +Ci + bi+1 + +b
d
= m và làm cho giá trị của s nhỏ hơn
N (mâu thuẫn).
Vậy bl = m + 1 - d,
b
2
= b
3
= = b
d
= 1,
„ . (đ-i)(đ+2)
N = (m +1 -d) + —
Bài 4. Cho ai, a
2
, ,a
d
, a, bi, b
2
, ,b
d
là các hằng số thực dương, còn Xi,
x
2
, , x
d
là các biến không âm sao cho Xk=i a
fc
= a. Tìm GTLN và GTNN của
k

y đ
a
k^k

x
k

y đ
a
k

x
k


k
<
a
i
a
d
Vậy s đạt GTLN bằng khi Xi = x
2
= .= x
d
_i = 0; x
d
= — và s đạt
GTNN bằng khi x
2
= .= x
d
_i = x
d
; Xi = - .
a
i a.1
Bài 5. Cho các số nguyên dương a
b
a
2
, a
3
, a
4

= X1X2 + 0.5xi - 0.25 - 0.5x
2
= X1X
2
+ 0.5(xi - x
2
) - 0.25
= X1X
2
+ 0.5x - 0.25 (Do Xi - x
2
= X > 0.5)
Giả sử Xi < X2 < <x
5
mà do ai + +a
5
= 99. Ta suy ra
ai = a
2
= 19.5 và a
3
= a
4
= a
5
= 20.
Vậy GTLN của N = 19.5
2
. 20
3

+ a
4
+ a
5
= 99.
Tìm GTLN của p = aia
2
a
3
a4a5.
2.2.2. Thiết lập thứ tự trên các yếu tố bình đẳng
Sự thiết lập thứ tự trên các yếu tố bình đẳng đã làm giảm đi rất nhiều
trường hợp xét trong bài toán. Đó chính là tính ưu việt của phương pháp này.
Ta xét một vài YÍ dụ cụ thể để hiểu rõ hơn về phương pháp này.
1
2
Bài 1. Tìm các số nguyên dương X , y sao cho (3x
+ 1) : y và (3y + 1) : X.
Giải
Do vai trò bình đẳng của X , y nên ta có thể giả sử X > y. Khi đó xảy ra
các trường hợp:
(a) Neu X = y thì (Зх + 1) : X => 1 : X, điều này trái với giả thiết X > 1.
(b) Neu X > у thì tồn tại số nguyên p sao cho Зу + X = px. Mặt khác, ta có
Зх > Зу => Зх > Зу + 1 = px. Dấu bằng không xảy ra vì Зу + 1 không chia
hết cho 3, nên ta chỉ có 3x > px. Vậy p = 1 hoặc p = 2.
- Nếu p = 1 thì Зу + 1 = x(3(3y + 1) + 1) : y, do đó 4 : y.
Suy ra у = 2 hoặc у = 4. Tương ứng X = 7 hoặc X = 13.
- Nếu p = 2 thì 2x = 3y + l(9y + 5) : y, do đó 5 : y.
Suy ra у = 5 và X = 8.
Bài 2. Tìm tất cả các số nguyên a, b, с sao cho