Toán ✅ (ĐÃ XÁC MINH)

Một số nguyên lý cơ bản và ứng dụng – Tài liệu text

Một số nguyên lý cơ bản và ứng dụng

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (528.14 KB, 70 trang )

Header Page 1 of 161.

TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
*********

PHAN THỊ TUYẾT CHINH

MỘT SỐ NGUYÊN LÝ CƠ BẢN
VÀ ỨNG DỤNG

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Đại số

HÀ NỘI – 2016

Footer Page 1 of 161.

Header Page 2 of 161.

TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
*********

PHAN THỊ TUYẾT CHINH

MỘT SỐ NGUYÊN LÝ CƠ BẢN
VÀ ỨNG DỤNG

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC

Chuyên ngành: Đại số

Người hướng dẫn khoa học

TS. Nguyễn Thị Kiều Nga

HÀ NỘI – 2016

Footer Page 2 of 161.

Header Page 3 of 161.

Mục lục

Mở đầu

1

1 Nguyên lý Dirichlet và ứng dụng trong toán sơ cấp

3

1.1

Nguyên lý Dirichlet. .. .. .. .. .. .. .. .. .. . .

3

1.1.1

Nguyên lý Dirichlet mở rộng. .. .. .. .. .. .

4

1.1.2

Nguyên lý Dirichlet dưới dạng tập hợp hữu hạn .

4

1.1.3

Nguyên lý Dirichlet dưới dạng tập hợp hữu hạn
mở rộng. .. .. .. .. .. .. .. .. .. .. . .

4

1.1.4

Nguyên lý Dirichlet trong hình học. .. .. .. .

5

1.1.5

Vận dụng nguyên lý Dirichlet trong giải toán sơ cấp

5

1.1.6

Một số ví dụ về nguyên lý Dirichlet. .. .. .. .

6

1.2

Ứng dụng nguyên lý Dirichlet vào số học. .. .. .. . .

7

1.3

Ứng dụng nguyên lý Dirichlet vào hình học. .. .. .. .

14

1.4

Ứng dụng nguyên lý Dirichlet vào giải các bài toán khác

24

1.5

Bài tập áp dụng. .. .. .. .. .. .. .. .. .. .. . .

27

2 Nguyên lý cực hạn và ứng dụng trong toán sơ cấp

29

2.1

Nguyên lý cực hạn. .. .. .. .. .. .. .. .. .. . .

29

2.2

Ứng dụng nguyên lý cực hạn vào số học

.. .. .. .. .

30

2.3

Ứng dụng nguyên lý cực hạn vào hình học. .. .. .. .

36

2.4

Ứng dụng nguyên lý cực hạn vào giải các bài toán khác .

42

2.5

Bài tập áp dụng. .. .. .. .. .. .. .. .. .. .. . .

46

i

Footer Page 3 of 161.

Header Page 4 of 161.
MỤC LỤC

MỤC LỤC

3 Nguyên lý xuống thang và ứng dụng trong toán sơ cấp

47

3.1

Nguyên lý xuống thang. .. .. .. .. .. .. .. .. . .

47

3.2

Ứng dụng nguyên lý xuống thang vào số học. .. .. . .

48

3.3

Ứng dụng nguyên lý xuống thang vào hình học. .. .. .

56

3.4

Ứng dụng nguyên lý xuống thang vào các bài toán khác .

59

3.5

Bài tập áp dụng. .. .. .. .. .. .. .. .. .. .. . .

62

Tài liệu tham khảo

64

ii

Footer Page 4 of 161.

Header Page 5 of 161.

Lời cảm ơn
Em xin bày tỏ lòng biết ơn sâu sắc đến TS. Nguyễn Thị Kiều Nga, người
đã tận tình hướng dẫn để em có thể hoàn thành khóa luận này.
Em cũng xin bày tỏ lòng biết ơn chân thành tới các thầy cô giáo trong
khoa Toán, các thầy cô trong tổ Đại số và thư viện trường Đại học Sư
phạm Hà Nội 2 đã giúp đỡ em trong suốt quá trình học tập tại trường.
Hà Nội, tháng 5 năm 2016
Sinh viên

Phan Thị Tuyết Chinh

Footer Page 5 of 161.

Header Page 6 of 161.

Lời cam đoan
Em xin cam đoan, dưới sự hướng dẫn của TS. Nguyễn Thị Kiều Nga,
khóa luận chuyên ngành Đại số với đề tài:”Một số nguyên lý cơ bản
và ứng dụng” được hoàn thành bởi sự nhận thức và tìm hiểu của bản
thân.
Trong quá trình nghiên cứu và thực hiện khóa luận, em có tham khảo
tài liệu của một số tác giả với sự biết ơn chân thành.
Hà Nội, tháng 5 năm 2016
Sinh viên

Phan Thị Tuyết Chinh

Footer Page 6 of 161.

Header Page 7 of 161.

Mở đầu
1. Lí do chọn đề tài
Trong nhà trường, môn toán giữ một vị trí hết sức quan trọng. Nó
giúp học sinh học tốt các môn học khác, là công cụ của nhiều ngành
khoa học và là công cụ để hoạt động trong đời sống thực tế. Đặc biệt
Toán sơ cấp không chỉ gần gũi với các em học sinh mà còn có tác dụng
trong việc khai thác và phát triển năng lực trí tuệ chung, rèn luyện các
thao tác và phẩm chất tư duy của chúng.
Có rất nhiều phương pháp khác nhau để giải quyết các bài toán sơ
cấp, trong đó người ta có thể sử dụng một công cụ hữu ích là các nguyên
lý cơ bản. Đây là cách đưa các bài toán đã cho về các bài toán đơn giản
hơn, sử dụng linh hoạt các nguyên lý này sẽ là một lợi thế lớn giúp các
em học sinh phát triển niềm đam mê với toán học và năng lực tư duy
của bản thân.
Vì các lý do trên, cùng với sự hướng dẫn của cô Nguyễn Thị Kiều
Nga tôi đã chọn đề tài: “Một số nguyên lý cơ bản và ứng dụng”.
Khóa luận gồm ba chương:
Chương 1: Nguyên lý Dirichlet và ứng dụng trong toán sơ cấp.
Chương 2: Nguyên lý cực hạn và ứng dụng trong toán sơ cấp.
Chương 3: Nguyên lý xuống thang và ứng dụng trong toán sơ cấp.
2. Mục đích nghiên cứu
Sử dụng các nguyên lý cơ bản để giải các bài toán sơ cấp.

Footer Page 7 of 161.

1

Header Page 8 of 161.

3. Đối tượng nghiên cứu
– Nguyên lý cơ bản.
– Các bài toán sơ cấp được ứng dụng các nguyên lý cơ bản.
4. Phương pháp nghiên cứu
Tham khảo tài liệu, phân tích, so sánh và hệ thống hóa và tổng hợp.

Footer Page 8 of 161.

2

Header Page 9 of 161.

Chương 1
Nguyên lý Dirichlet và ứng dụng
trong toán sơ cấp
1.1

Nguyên lý Dirichlet

Nhà toán học nổi tiếng người Đức Peter Gustav Lejeune Dirichlet (1805−
1859) là người đầu tiên phát biểu quy tắc chia phân tử vào các lớp. Quy
tắc này được gọi là “Nguyên lý Dirichlet” hay còn gọi là “Nguyên lý
Lồng và Thỏ” hoặc “Nguyên lý ngăn kéo”. Nguyên lý này được phát
biểu đơn giản là: nếu đem nhốt n + 1 con thỏ vào n chiếc lồng thì luôn
có một cái lồng chứa ít nhất 2 con thỏ.

Chứng minh. Ta chứng minh bằng phản chứng. Giả sử n + 1 con thỏ
nhốt vào n chiếc lồng mà không lồng nào chứa 2 con thỏ trở lên, tức mỗi
lồng chứa không quá 1 con thỏ. Như vậy, n chiếc lồng chứa không quá
n con thỏ. Mâu thuẫn với giả thiết có n + 1 con thỏ. Suy ra giả sử sai.
Vậy ta có điều phải chứng minh.
Sau đây là một số dạng phát biểu khác của Nguyên lý Dirichlet:

Footer Page 9 of 161.

3

Header Page 10 of 161.

1.1.1

Nguyên lý Dirichlet mở rộng

Nếu nhốt n con thỏ vào k cái lồng (k ≤ n) thì luôn có một cái lồng chứa
n
ít nhất
con thỏ, trong đó x là số nguyên nhỏ nhất lớn hơn hoặc
k
bằng x.
Chứng minh. Ta xét hai trường hợp sau:
.
Trường hợp 1. Nếu n .. k, tức n = k.a với a ∈ Z thì ta giả sử mỗi
n
= a con thỏ, nghĩa là mỗi lồng chỉ có ít
lồng thỏ không có đến

k
hơn hoặc bằng a − 1 con. Từ đó suy ra tổng số con thỏ không vượt quá
k.(a − 1) = k.a − k = n − k < n con thỏ (mâu thuẫn với giả thiết có n
con thỏ). Do đó điều giả sử là sai.
Trường hợp 2. Nếu n không chia hết cho k, tức n = ka + r với 1 ≤ r ≤
n
k − 1, (a, r ∈ Z) thì ta giả sử mỗi lồng thỏ không có đến
= a+1
k
con thỏ, nghĩa là mỗi lồng có ít hơn hoặc bằng a con. Khi đó, k lồng chỉ
có k.a = n − r < n con (mâu thuẫn với giả thiết có n con thỏ).Do đó
điều giả sử là sai.
Vậy ta có điều phải chứng minh.
1.1.2

Nguyên lý Dirichlet dưới dạng tập hợp hữu hạn

Cho A và B là hai tập hợp không rỗng có số phần tử hữu hạn mà số
phần tử của A lớn hơn số phần tử của B. Nếu với một quy tắc nào đó
mà mỗi phần tử của A tương ứng với một phần tử của B thì tồn tại ít
nhất 2 phần tử khác nhau của A cùng tương ứng với một phần tử của
B.
1.1.3

Nguyên lý Dirichlet dưới dạng tập hợp hữu hạn mở rộng

Cho hai tập hợp hữu hạn A và B, gọi |A| và |B| lần lượt là số phần tử
của A và B. Giả sử có một số tự nhiên k nào đó mà |A| > k. |B| và có
một quy tắc tương ứng mỗi phần tử của A với một phần tử của B. Khi

Footer Page 10 of 161.

4

Header Page 11 of 161.

đó tồn tại ít nhất k + 1 phần tử khác nhau của A cùng tương ứng với
một phần tử của B.
1.1.4

Nguyên lý Dirichlet trong hình học

Nguyên lý Dirichlet cho diện tích: Cho A là một hình phẳng, A1, A2, …, An
là các hình phẳng sao cho Ai ⊆ A và SA < n
i=1 SAi

, với SX là diện

tích của hình X. Khi đó tồn tại 2 hình phẳng Ai, Aj (1 ≤ i < j ≤ n) mà
chúng có điểm trong chung. Ta nói điểm M là điểm trong của tập X
nếu có đường tròn tâm M bán kính đủ nhỏ sao cho nó nằm hoàn toàn
trong X.
Nguyên lý Dirichlet cho độ dài và thể tích các vật được phát biểu tương
tự.
1.1.5

Vận dụng nguyên lý Dirichlet trong giải toán sơ cấp

Cơ sở lý luận: Để vận dụng nguyên lý Dirichlet ta thấy rằng việc nhận
ra “lồng” và “thỏ” là điểm mấu chốt. Vì vậy khi giải các bài toán sơ
cấp, ta cần xem xét kỹ đối tượng nào là “lồng”, đối tượng nào là “thỏ”
hay đôi khi ta phải tạo ra “lồng” và “thỏ” để đưa bài toán đã cho về bài
toán đơn giản hơn.

Footer Page 11 of 161.

5

Header Page 12 of 161.

1.1.6

Một số ví dụ về nguyên lý Dirichlet

Ví dụ 1.1.1. Ở nước ta, cứ 64 người thì chắc chắn có ít nhất 2 người ở
cùng một tỉnh thành.
Giải
Ta đã biết nước ta có 63 tỉnh thành khác nhau nên theo nguyên lý
64
Dirichlet có ít nhất
= 2 người ở cùng một tỉnh thành.
63
Ví dụ 1.1.2. Trong số 200 người có ít nhất 17 người sinh cùng một
tháng.
Giải
Ta đã biết một năm có 12 tháng khác nhau nên theo nguyên lý Dirichlet

200
= 17 người sinh cùng một tháng.
có ít nhất
12
Ví dụ 1.1.3. Trong 54 học sinh làm bài kiểm tra môn Toán không có ai
được dưới điểm 3, nhưng chỉ có 2 em, được điểm 10. Chứng minh rằng
có ít nhất 8 học sinh có điểm bằng nhau.
Giải
Ta phân ra 7 loại điểm từ 3 đến 9. Như vậy theo nguyên lý Dirichlet,
trong số 52 học sinh (không tính 2 học sinh được điểm 10) có ít nhất
52
= 8 học sinh có số điểm bằng nhau.
7
Ví dụ 1.1.4. Trong trường phổ thông có 4 mức xếp loại học tập: giỏi,
khá, trung bình, yếu. Hỏi để 1 lớp của trường đó chắc chắn có 10 học
sinh xếp cùng loại học tập thì số học sinh của lớp đó ít nhất bằng bao
nhiêu?
Giải
Số học sinh ít nhất để đảm bảo chắc chắn có 10 học sinh xếp cùng loại
n
học tập là số nguyên nhỏ nhất n sao cho:
= 10. Suy ra n = 37.
4

Footer Page 12 of 161.

6

Header Page 13 of 161.

1.2

Ứng dụng nguyên lý Dirichlet vào số học

Việc tìm lời giải cho các bài toán số học thường gặp rất nhiều khó khăn.
Tuy nhiên nguyên lý Dirichlet là một công cụ hiệu quả và sắc bén được
sử dụng để giải quyết các bài toán số học, mà lời giải được trình bày đơn
giản và dễ hiểu. Sau đây là một số bài toán số học ứng dụng nguyên lý
Dirichlet.

Bài tập 1.1. Chứng minh rằng từ 52 số nguyên bất kỳ luôn có thể chọn
ra được 2 số mà tổng hoặc hiệu của chúng chia hết cho 100.
Giải
Tất cả các số dư trong phép chia cho 100 là 100 số khác nhau từ 0 đến
99. Ta chia thành các nhóm như sau:
{0}, {1, 99}, {2, 98}, …, {49, 51}, {50} .
Vì có tất cả 51 nhóm khác nhau mà có 52 số nên theo nguyên lý Dirichlet
phải có 2 số mà các số dư khi chia cho 100 rơi vào một nhóm. Dễ thấy
hai số đó là hai số cần tìm vì nếu số dư của chúng bằng nhau thì hiệu
của chúng chia hết cho 100, ngược lại nếu số dư của chúng khác nhau
thì tổng của chúng chia hết cho 100.
Bài tập 1.2. Cho dãy số 10, 102, 103, …, 1020. Chứng minh tồn tại một
số chia cho 19 dư 1.
Giải
Tất cả số dư trong phép chia cho 19 là 19 số từ 0 dến 18. Mà theo
giả thiết ta có dãy 10, 102, 103, …, 1020 gồm 20 số. Vậy theo nguyên lý
Dirichlet trong dãy trên tồn tại 2 số khi chia cho 19 có cùng số dư. Giả
.
sử 2 số đó là 10n, 10m (1 ≤ n < m ≤ 20). Suy ra 10m − 10n .. 19 hay
Footer Page 13 of 161.

7

Header Page 14 of 161.

.
.
10n (10m−n − 1) .. 19. Mặt khác (10n, 19) = 1 suy ra 10m−n − 1 .. 19 hay
số 10m−n ≡ 1(mod 19). Lại có (1 ≤ n < m ≤ 20) suy ra 10m−n nằm
trong dãy 20 số đã cho.
Vậy trong dãy số đã cho tồn tại 1 số chia cho 19 dư 1.
Nhận xét: bài toán trên có thể phát biểu dưới dạng: tồn tại số tự
.
nhiên k sao cho: 10k − 1 .. 19.
Bài tập 1.3. Người ta viết 5 số tự nhiên a1, a2, a3, a4, a5 thành một hàng.
Chứng minh rằng hoặc một trong các số tự nhiên đó chia hết cho 5 hoặc
một tổng một số số tự nhiên chia hết cho 5.
Giải
Xét 5 tổng sau:
S1 = a1
S 2 = a1 + a2
S3 = a1 + a2 + a3
S 4 = a1 + a2 + a3 + a4
S5 = a1 + a2 + a3 + a4 + a5 .
Trường hợp 1. Nếu một trong các tổng trên chia hết cho 5 thì bài toán
đã được chứng minh xong.
Trường hợp 2. Nếu không có tổng nào chia hết cho 5 thì mỗi tổng đó

chia cho 5 được các số dư là 1 trong 4 số: 1, 2, 3, 4. Như vậy, theo nguyên
lý Dirichlet tồn tại 2 tổng chia cho 5 có cùng số dư. Giả sử hai tổng đó
là Sm, Sn với 1 ≤ n < m ≤ 5. Khi đó hiệu của chúng chia cho 5 tức:
.
Sm − Sn = an+1 + an+2 + … + am .. 5 và an+1 + an+2 + … + am là tổng các
số tự nhiên kề nhau.
Vậy tổng một số các số tự nhiên kề nhau chia hết cho 5.
Nhận xét: bài toán trên có thể được tổng quát lên như sau: xếp n
số tự nhiên tùy ý thành một hàng thì hoặc có 1 số chia hết cho n hoặc
tổng của một số số tự nhiên chia hết cho n.

Footer Page 14 of 161.

8

Header Page 15 of 161.

Bài tập 1.4. Chứng minh rằng tồn tại một bội của 13 gồm toàn chữ số
2.
Giải
Xét dãy gồm 14 số: 2, 22, 222, …, 222222…22. Mỗi số chia cho 13 có số
14 chữ số 2

dư là một trong các số từ 0 đến 12. Vậy theo nguyên lý Dirichlet, trong
dãy 14 số trên tồn tại 2 số chia cho 13 có cùng số dư. Giả sử 2 số đó
là: 222222…22, 222222…22 với 1 ≤ n < m ≤ 14. Suy ra hiệu của chúng
m chữ số 2

n chữ số 2

.
.
222222…22.10 .. 13. Mà (10n, 13) = 1 nên 222222…22 .. 13. Mặt khác,
n

m – n chữ số 2

m – n chữ số 2

do 1 ≤ n < m ≤ 14 nên 222222...22 nằm trong dãy 14 số đang xét.
m – n chữ số 2

Vậy tồn tại một bội của 13 gồm toàn chữ số 2.
Bài tập 1.5. Biết 3 số a, a + k, a + 2k đều là các số nguyên tố lớn hơn
.
3. Chứng minh rằng k .. 6.
Giải
Ta thấy:
+) Vì a, a + k, a + 2k là các số nguyên tố lớn hơn 3 nên suy ra chúng là
các số lẻ.
.
+) Vì a và a + k đều là số lẻ nên k phải là số chẵn hay k .. 2. (1)
+) Vì a, a + k, a + 2k đều không chia hết cho 3 nên theo nguyên lý
Dirichlet khi chi cho 3 có ít nhất 2 số có cùng số dư. Ta xét các trường
hợp sau:
Trường hợp 1. Nếu a ≡ a + k(mod 3) thì (a + k) − a ≡ 0(mod 3) hay
.
k ≡ 0(mod 3) tức là k .. 3.
Trường hợp 2. Nếu a + 2k ≡ a + k(mod 3) thì (a + 2k) − (a + k) ≡

.
0(mod 3) suy ra k ≡ 0(mod 3) hay k .. 3.
Trường hợp 3. Nếu a + 2k ≡ a(mod 3) thì (a + 2k) − a ≡ 0(mod 3)
hay 2k ≡ 0(mod 3). Mà (2,3)= 1 nên suy ra k ≡ 0(mod 3). Vậy trong

Footer Page 15 of 161.

9

Header Page 16 of 161.

mọi trường hợp ta đều có k ≡ 0(mod 3) (2).
.
Kết hợp (1) và (2) suy ra: k .. 6.
Bài tập 1.6. Cho 10 số nguyên dương a1, a2, …, a10. Chứng minh tồn
tại các số ci ∈ {−1, 0, 1}, i ∈ 1, 10, không đồng thời bằng 0 sao cho
10
i=1 ci .ai

chia hết cho 1023.
Giải
10
i=1 bji .ai, bji

Xét tất cả các số có dạng Aj =

∈ {0, 1}, i ∈ 1, 10,

j ∈ 1, 1024. Ta thấy có tất cả 210 = 1024 số Aj, j ∈ 1, 1024 như vậy.

Theo nguyên lý Dirichlet, khi chia 1024 số trên cho 1023 thì ít nhất có 2
số có cùng số dư. Giả sử 2 số đó là: Am =

10
i=1 bmi .ai

với bmi ∈ {0, 1} và bni ∈ {0, 1}, m = n. Khi đó
.
Am −An = ( 10 bmi .ai − 10 bni .ai ) .. 1023 hay
i=1

i=1

10
i=1 bni .ai

và An =

10
i=1 (bmi −bni ).ai

..
. 1023.

Đặt ci = bmi − bni. Do bmi ∈ {0, 1} và bni ∈ {0, 1} nên ci ∈ {−1, 0, 1}.
Mặt khác, do m = n nên Am = An. Suy ra ci không đồng thời bằng 0.
Vậy ta có điều phải chứng minh.
Bài tập 1.7. Chứng minh có vô số số chia hết cho 2312

1993

mà trong biểu

diễn thập phân của số đó không có các chữ số 0, 1, 2, 3.
Giải
Gọi a là số tự nhiên mà trong biểu diễn thập phân của nó không chứa
các chữ số 0, 1, 2, 3. Rõ ràng các số a như vậy là vô hạn. Xét dãy số sau
đây:
a, aa, aaa, …, aaa…a .
23121993 +1 số a

Đem chia 2312

1993

1993

+ 1 số khác nhau trong dãy trên cho 2312

. Theo

nguyên lý Dirichlet sẽ tồn tại ít nhất 2 số trong dãy có cùng số dư khi
1993

chia cho 2312

. Giả sử 2 số đó là aaa…a, aaa…a (n > m). Khi đó:
n chữ số a m chữ số a

Footer Page 16 of 161.

10

Header Page 17 of 161.

aaa…a − aaa…a = aaa…a00…0 .
n chữ số a

m chữ số a
1993

Vì (10,23) = 1 nên (10k, 2312

n – m chữ số a, m số 0

1993
.
) = 1 nên aaa…a .. 2312. (*)

n – m số a

Mặt khác, do có vô số số a như trên nên từ (*) suy ra tồn tại vô số chia
hết cho 2312

1993

mà trong biểu diễn thập phân của chúng không có các

chữ số 0, 1, 2, 3.

Bài tập 1.8. Cho 5 số nguyên phân biệt tùy ý: a1, a2, a3, a4, a5. Xét tích
P = (a1 − a2 )(a1 − a3 )(a1 − a4 )(a1 − a5 )(a2 − a3 )(a2 − a4 )(a2 − a5 )(a3 −
.
a4 )(a3 − a5 )(a4 − a5 ). Chứng minh rằng: P .. 288.
Giải
.
Ta thấy 288 = 25 .32 mà (2,3) = 1 nên để chứng minh P .. 288 ta sẽ đi
chứng minh P đồng thời chia hết cho 25 và 32. Theo nguyên lý Dirichlet
thì trong n + 1 số nguyên tùy ý luôn tồn tại 2 số có hiệu chia hết cho
n (tức 2 số đó chia cho n có cùng số dư). Vậy trong 4 số a1, a2, a3, a4
có 2 số có hiệu chia hết cho 3, không làm giảm tính tổng quát giả sử:
.
a1 − a2 .. 3. Bây giờ xét tiếp 4 số a2, a3, a4, a5, lập luận như trên ta được
hiệu của 2 số chia hết cho 3, mà hiệu này khác a1 − a2 (vì a1 không thuộc
dãy đang xét). Như thế trong tích P đã cho có 2 hiệu khác nhau cùng
.
chia hết cho 3 suy ra P .. 32 (1). Lại theo nguyên lý Dirichlet thì trong 5
5
số đã cho có ít nhất
= 3 có cùng tính chẵn, lẻ nên ta xét 2 trường
2
hợp sau:
Trường hợp 1. Nếu có ít nhất 4 số cùng tính chẵn lẻ thì từ 4 số này có
thể lập nên 6 hiệu khác nhau cùng chia hết cho 2, do đó tích của chúng
.
sẽ chia hết cho 26. Hiển nhiên nó chia hết cho 25 hay P .. 25 .
Trường hợp 2. Nếu có đúng 3 số cùng tính chẵn lẻ. Không làm giảm
tính tổng quát ta giả sử 3 số đó là a1, a2, a3. Khi đó còn lại 2 số là
a4, a5 cũng có tính chẵn lẻ giống nhau nhưng khác tính chẵn lẻ của 3 số
a1, a2, a3. Suy ra 4 hiệu sau chia hết cho 2:

Footer Page 17 of 161.

11

Header Page 18 of 161.

a1 − a2 ; a1 − a3 ; a2 − a3 ; a4 − a5 .
Mặt khác, trong 5 số đã cho có ít nhất có 2 số có hiệu chia hết cho 4.
Vì thế trong 4 số a1 − a2 ; a1 − a3 ; a2 − a3 ; a4 − a5 có ít nhất 1 chia hết
.
.
cho 4. Do đó: (a1 − a2 )(a1 − a3 )(a2 − a3 )(a4 − a5 ) .. 25 hay P .. 25. (2)
.
Kết hợp (1) và (2) suy ra: P .. 288.
Bài tập 1.9. Xét tập M gồm 2016 số nguyên dương phân biệt sao cho
không có số nào trong chúng có ước nguyên tố lớn hơn 23. Chứng minh
rằng M chứa 1 tập hợp con gồm 4 phần tử mà tích của 4 phần tử này
là lũy thừa bậc 4 của 1 số nguyên.
Giải
Ta thấy chỉ có 9 số nguyên tố không lớn hơn 23 là: p1 = 2, p2 = 3, p3 =
5, p4 = 7, p5 = 11, p6 = 13, p7 = 17, p8 = 19, p9 = 23.
Gọi k là 1 phần tử bất kỳ của tập M .
Khi đó, k có biểu diễn như sau: k = pk11 .pk22 …pk99 (*) trong đó ki, i = 1, 9
là các số nguyên không âm. Với mỗi phần tử k của tập hợp M ta gán
với một dãy (x1, x2, …, x9 ) trong đó:

0 nếu số mũ k của p trong (*) là chẵn
i

i
xi =
1 nếu số mũ k của p trong (*) là lẻ.
i
i
Tập hợp dãy (x1, x2, …, x9 ) như vậy gồm 29 phần tử. Ta thấy: 29 + 1 =
513 < 2016. Trong mọi tập hợp con chứa không ít hơn 29 + 1 phần tử
của M luôn chứa ít nhất 2 số nguyên phân biệt a1, b1 cố cùng bộ sắp
xếp gồm số 0 và 1 giống nhau. Giả sử bộ sắp xếp đó là: x1, x2, …, x9 và
2 số a1, b1 có biểu diễn:
k

k

k

a1 = pk11 .pk22 …pk99 và b1 = p11 .p22 …p99 .
Khi đó suy ra: ki, ki có cùng tính chẵn lẻ, ∀i = 1, 9. Do đó:
k +k1

a1 .b1 = p11

Footer Page 18 of 161.

k +k2

.p22

12

k +k9

…p99

= c2 .

Header Page 19 of 161.

(Vì mỗi số tự nhiên là số chính phương khi và chỉ khi tất cả số mũ trong
biểu diễn tiêu chuẩn đều chẵn).
Nói cách khác, ta lấy đi một cặp (a1, b1 ) như thế từ tập M thì tập M
còn lại 2016 − 2 = 2014 > 29 + 1 = 513 số.
Tiếp tục áp dụng nguyên lý Dirichlet và lấy đi những cặp số như trên
cho đến khi còn lại 29 + 1 phần tử trong M .
Mà để ý rằng: 2016 > 3.(29 + 1) = 3.513 = 1539 nên ta có thể lấy đi
29 + 1 cặp (ai, bi ). Đến đây số phần tử còn lại trong M là:
2016 − 2.(29 + 1) = 990 > 513 = 29 + 1.
Xét 29 +1 cặp được lấy đi. Ứng với mỗi cặp (ai, bi ) ta có c2i = ai .bi, i = 1, 9.

Suy ra: ci = ai .bi. Mặt khác, các số ai, bi chỉ chứa các số nguyên tố pi ,
i = 1, 9 nên ci cũng như vậy. Bằng cách lập luận như trên trong 29 + 1 số
ci ta luôn tìm được ít nhất 2 số nguyên ci, cj phân biệt có cùng bộ sắp
xếp 0 và 1 giống nhau. Do đó tồn tại số nguyên d thỏa mãn: d2 = ci .cj
suy ra d4 = c2i .c2j = ai .bi .aj .bj. Vậy ta có điều phải chứng minh.
Bài tập 1.10. Chứng minh trong 12 số nguyên tố phân biệt luôn luôn
chọn ra được 6 số a1, a2, a3, a4, a5, a6 sao cho
.
(a1 − a2 )(a3 − a4 )(a5 + a6 ) .. 1800.
Giải

Vì 3 số nguyên tố đầu tiên là 2, 3, 5 nên trong 12 số nguyên tố phân
biệt đã cho luôn có 9 số lớn hơn 5. Do đó,
+) Chín số nguyên tố lớn hơn 5 khi chia cho 3 luôn dư 2 hoặc 1. Theo
9
nguyên lý Dirichlet phải tồn tại ít nhất
= 5 số chia hết cho 3 có
2
cùng số dư. Năm số này lại không chia hết cho 5 nên theo nguyên lý
5
Dirichlet trong 5 số ấy có ít nhất
= 2 số chia cho 5 có cùng số dư (vì
4
khi chia cho 5 có 4 số dư là 1, 2, 3, 4). Không làm giảm tính tổng quát

Footer Page 19 of 161.

13

Header Page 20 of 161.

ta giả sử hai số đó là a1, a2, khi đó a1 ≡ a2 (mod 5) và a1 ≡ a2 (mod 3).
.
Từ đây suy ra: a1 − a2 .. 15 (1).
Mặt khác, do a1, a2 là các số nguyên tố lơn hơn 5 nên a1, a2 đều là các
.
số lẻ hay a1 − a2 .. 2 (2). Lại có: (2, 15) = 1 nên từ (1) và (2) suy ra:
.
a1 − a2 .. 30.
7

=4
+) Trong 7 số còn lại, theo nguyên lý Dirichlet tồn tại ít nhât
2
số khi chia cho 3 có cùng số dư. Đem 4 số này chia cho 5 xảy ra 2 trường
hợp sau:
Trường hợp 1. Giả sử có 2 số a3, a4 thỏa mãn: a3 ≡ a4 (mod 5) thì
.
.
tương tự cách lập luận trên ta suy ra được: a3 − a4 .. 5, a3 − a4 .. 3 và
.
.
a3 − a4 .. 2 suy ra a3 − a4 .. 30 (do (5,2,1) = 1). Lấy 2 số a5, a6 bất kỳ
trong 9 số khác các số a1, a2, a3, a4 đã chọn. Ta thấy a5, a6 đều là các số
.
.
lẻ nên a5 + a6 .. 2. Từ đây suy ra: (a1 − a2 )(a3 − a4 )(a5 + a6 ) .. 1800.
Trường hợp 2. Nếu 4 số này chia cho 5 có 4 số dư khác nhau là 1,
2, 3, 4. Không làm giảm tính tổng quát, ta giả sử: a5 ≡ 1(mod 5) và
.
a6 ≡ 4(mod 5) suy ra a5 + a6 ≡ 5(mod 5) hay a5 + a6 .. 5. (3) (Tương tự
ta chứng minh cho trường hợp a5 ≡ 2(mod 5) và a6 ≡ 3(mod 5)). Với 2
số còn lại ta gọi là a3, a4. Theo cách chọn 4 số ở trên ta có 2 số khi chia
.
cho 3 thì có cùng số dư (theo nguyên lý Dirichlet). Khi đó: a3 − a4 .. 3
(4). Mà a3, a4, a5, a6 là các số nguyên tố lớn hơn 5 nên a3, a4, a5, a6 đều
.
.
là số lẻ. Suy ra: a5 + a6 .. 2 (5) và a3 − a4 .. 2 (6). Kết hợp (3) và (5) suy
.
.

ra: a5 + a6 .. 10 ( do (2,5) = 1). Kết hợp (4) và (6) suy ra: a3 − a4 .. 6 (
.
do (2,3) = 1). Vậy: (a1 − a2 )(a3 − a4 )(a5 + a6 ) .. 30.10.6 = 1800.
Tóm lại ta có luôn có điều phải chứng minh.

1.3

Ứng dụng nguyên lý Dirichlet vào hình học

Trong mục này, ta sử dụng nguyên lý Dirichlet vào giải các bài toán
hình học. Thường phương pháp Dirichlet được áp dụng kết hợp kèm
theo phương pháp phản chứng hay các phép biến hình.

Footer Page 20 of 161.

14

Header Page 21 of 161.

Bài tập 1.11. Trong hình vuông cạnh 1, đặt 51 điểm phân biệt bất kỳ.
Chứng minh rằng có ít nhất 3 trong số 51 điểm đó nằm trong một đường
1
tròn bán kính .
7
Giải
Ta chia hình vuông đã cho thành 25 hình vuông con bằng nhau có cạnh
1
bằng. Theo nguyên lý Dirichlet tồn tại ít nhất một hình vuông con C
5

51
= 3 điểm trong số 51 điểm ban đầu. Đường tròn (C)
chứa ít nhất
25
1
1
ngoại tiếp hình vuông con C có bán kính √ < .
5 2 7
1
Vậy 3 điểm nói trên nằm trong một đường tròn bán kính .
7
Nhận xét: Ta có thể tổng quát bài toán trên như sau: Trong hình
vuông có cạnh bằng a đặt m điểm phân biệt bất kỳ. Chứng minh có ít
nhất n điểm trong m điểm đã cho nằm trong một đường tròn bán kính
a2
(trong đó [a] là phần nguyên của a).
m
2.
n−1
Bài tập 1.12. Cho S là một tập hợp gồm 9 điểm khác nhau có các tọa
độ nguyên trong không gian. Chứng minh rằng có ít nhất một trung điểm
của đường nối các cặp điểm đã cho có tọa độ nguyên.
Giải
Gọi tọa độ 2 điểm bất kỳ trong không gian là A(a, b, c) và B(d, e, f ). Khi
a+d b+e c+f
đó trung điểm O của đoạn AB là: O(
,
,
).
2

2
2
Các tọa độ của điểm O nguyên nếu và chỉ nếu a và d, b và e, c và f cùng
tính chẵn lẻ. Mà có 23 = 8 bộ ba chẵn lẻ khác nhau là:
(c, c, c); (l, l, l); (c, c, l); (c, l, l); (c, l, c); (l, c, c); (l, c, l); (l, l, c).
Nên theo nguyên lý Dirichlet có ít nhất 2 trong 9 điểm có cùng bộ ba
chẵn lẻ như nhau. Vậy có ít nhất một cặp điểm mà trung điểm giữa

Footer Page 21 of 161.

15

Header Page 22 of 161.

chúng có tọa độ nguyên.
Nhận xét: ta có thể tổng quát bài toán trên trong không gian như
sau: Trong không gian, cho tập hợp gồm
 m điểmkhác nhau có các tọa độ
m
1+

8 
nguyên. Chứng minh rằng có ít nhất 
 trung điểm của đường
2
nối các cặp điểm đã cho có tọa độ nguyên.
Bài tập 1.13. Trong mặt phẳng cho 25 điểm. Biết rằng trong 3 điểm
bất kỳ của 25 điểm 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 đường tròn bán kính 1 chứa không ít hơn 13 điểm đã

cho.
Giải

Lấy A là 1 trong số 25 điểm đã cho. Xét đường tròn Ω1 (A, 1), chỉ có 2
khả năng sau xảy ra:
Trường hợp 1. Nếu tất cả các điểm đã cho nằm trong Ω1 thì ta có điều
phải chứng minh.
Trường hợp 2. Ngược lại, tồn tại điểm B, (A = B), B là 1 trong số 25
điểm đã cho và thỏa mãn B ∈
/ Ω1. Do đó AB > 1.
Xét đường tròn Ω2 (B, 1), lấy C là điểm bất kỳ trong số 23 điểm còn lại.
Theo giả thiết trong 3 điểm bất kỳ thì trong đó luôn tồn tại 2 điểm có
khoảng cách nhỏ hơn 1 mà AB > 1 nên min{CA, CB} < 1. Từ đây suy
ra C ∈ Ω1 hoặc C ∈ Ω2. Như vậy chứng tỏ rằng các đường tròn Ω1 và Ω2

Footer Page 22 of 161.

16

Header Page 23 of 161.

chứa tất cả 25 điểm đã cho. Vì thế theo nguyên lý Dirichlet có ít nhất 1
25
= 13 điểm đã cho.
trong 2 đường tròn nói trên chứa không ít hơn
2
Nhận xét: ta có thể tổng quát bài toán trên như sau: Cho 2n + 1
điểm trên mặt phẳng (n ≥ 3). Biết trong 3 điểm bất kỳ trong đó 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 đường

tròn bán kính 1 chứa không ít hơn n + 1 điểm.
Bài tập 1.14. Một khu rừng thông hình vuông, mỗi chiều dài 1000m.
Trong khu rừng có 4500 cây thông, cây to nhất đường kính 0,5m.Chứng
minh rằng trong khu rừng có ít nhất 60 mảnh đất, diện tích mỗi mảnh
200m2 không có một cây thông nào.
Giải

Ta thấy: 1000m = 48.20m + 47.0.6m + 2.5,9m và : 1000m = 95.10m +
94.0,52m + 2.0,56m.
Ta chia một cạnh hình vuông thành 48 đoạn dài 20m, khoảng cách
giữa 2 đoạn là 0,6m, ở 2 đầu là 2 đoạn 5,9m. Còn ạnh còn lại của hình
vuông chia thành 95 đoạn dài 10m, khoảng cách giữa 2 đoạn là 0,52m
và 2 đầu là 2 đoạn dài 0,56m. Như vậy, ta có tất cả 45.95 = 4560 mảnh
có diện tích 200m2 .
Mà theo giả thiết, chỉ có 4500 cây thông, mỗi cây có đường kính 0,5m
(0,5 < 0,56 < 0,6) nên mỗi cây thông bất kỳ không thể nằm trên 2 mảnh
cùng lúc.
Vì thế còn ít nhất 60 mảnh (diện tích 200m2 ) không có cây thông nào.

Footer Page 23 of 161.

17

Header Page 24 of 161.

Bài tập 1.15. Cho 9 đường thẳng cùng có tính chất là mỗi đường thẳng
2
chia hình vuông thành 2 tứ giác có tỉ số diện tích là. Chứng minh rằng
3

có ít nhất 3 đường thẳng trong số đó cùng đi qua 1 điểm.
Giải

Các đường thẳng đã cho không thể cắt 2 cạnh kề nhau của một hình
vuông, bởi nếu thế chúng chia hình vuông thành 1 tam giác và 1 ngũ
giác (mâu thuẫn với giả thiết). Do đó 9 đường thẳng đã cho sẽ cắt 2
cạnh đối của hình vuông và không đi qua 2 đỉnh nào của hình vuông.
Giả sử 2 đường thẳng bất kỳ cắt 2 cạnh AD, BC tại M, N.
Gọi E, F, P, Q lần lượt là trung điểm của AB, CD, BC, AD.
Gọi J1, J2, J3, J4 nằm trên EF, PQ và thỏa mãn:
F J2
P J3
QJ4
2
EJ1
=
=
=
= .
F J1
EJ2
QJ3
P J4
3
Khi đó ta có
SABM N
SCDN M

1
AB.(BM + AN )

EJ1
2
2
=
=
= .
1
J1 F
3
CD.(M C + N D)
2

Từ cách lập luận trên suy ra mỗi đường thẳng có tính chất thỏa mãn
yêu cầu đề bài phải đi qua 1 trong 4 điểm J1, J2, J3, J4 nói trên. Vậy theo
9
nguyên lý Dirichlet, trong 9 đường thẳng đã cho tồn tại ít nhất
=3
4
đường thẳng đi qua 1 trong 4 điểm J1, J2, J3, J4 .

Footer Page 24 of 161.

18

Header Page 25 of 161.

Bài tập 1.16. Trên mặt phẳng, cho 9 điểm được nối với nhau đôi một
bới các đoạn màu xanh hoặc màu đỏ sao cho trong 3 điểm bất kỳ bao giờ
cũng tìm đk 2 điểm nối với nhau bởi màu đỏ. Chứng minh rằng trong số

các điểm đã cho luôn tìm được 4 điểm mà các đoạn thẳng nối chúng đều
có màu đỏ.
Giải
Gọi 9 điểm đã cho là:A, B, C, D, E, F, G, H, I. Xét 2 trường hợp:
Trường hợp 1. Tìm được 1 điểm là đầu mút của ít nhất 4 đoạn nối
màu xanh, giả sử đó là điểm A và các đoạn màu xanh là AB, AC, AE.
Theo giả thiết, trong số 3 đoạn nối 3 điểm bất kỳ luôn có 1 đoạn màu
đỏ nên các đoạn BC, BD, CD, CE, DE có màu đỏ. Vậy B, C, D, E là 4
điểm cần tìm.
Trường hợp 2. Mỗi điểm đều là đầu mút của nhiều nhất 3 đoạn màu
xanh. Khi đó không thể xảy ra trường hợp cả 9 điểm đều là đầu mút
của 3 đoạn màu xanh (vì khi đó sẽ có 9.3 :2 = 13,5 đoạn thẳng). Do
đó phải tìm được 1 điểm là mút của 2 đoạn màu xanh, giả sử điểm đó
là điểm I. Khi đó I là đầu mút của ít nhất 6 đoạn màu đỏ, giả sử là
IA, IB, IC, ID, IE, IF. Theo kết quả bài tập trước có ít nhất 3 trong
số 6 điểm A, B, C, D, E, F tạo thành một tam giác cùng màu. Không
làm giảm tính tổng quát giả sử tam giác đó là ABC. Mặt khác, theo giả
thiết 3 đoạn nối 3 điểm bất kỳ luôn có 1 đoạn màu đỏ nên ABC là tam
giác đỏ.
Vậy A, B, C, I là 4 điểm cần tìm.
Bài tập 1.17. Cho mỗi điểm trên mặt phẳng được tô bằng 2 màu xanh,
đỏ. Chứng minh rằng tồn tại một tam giác mà ba đỉnh và trọng tâm cùng
màu.
Giải
Lấy 5 điểm tùy ý sao cho không có 3 điểm nào thẳng hàng trên mặt
phẳng. Vì chỉ dùng 2 màu xanh, đỏ nên theo nguyên lý Dirichlet phải

Footer Page 25 of 161.

19

Chuyên ngành: Đại sốNgười hướng dẫn khoa họcTS. Nguyễn Thị Kiều NgaHÀ NỘI – 2016Footer Page 2 of 161.Header Page 3 of 161.Mục lụcMở đầu1 Nguyên lý Dirichlet và ứng dụng trong toán sơ cấp1.1Nguyên lý Dirichlet. .. .. .. .. .. .. .. .. .. . .1.1.1Nguyên lý Dirichlet mở rộng. .. .. .. .. .. .1.1.2Nguyên lý Dirichlet dưới dạng tập hợp hữu hạn .1.1.3Nguyên lý Dirichlet dưới dạng tập hợp hữu hạnmở rộng. .. .. .. .. .. .. .. .. .. .. . .1.1.4Nguyên lý Dirichlet trong hình học. .. .. .. .1.1.5Vận dụng nguyên lý Dirichlet trong giải toán sơ cấp1.1.6Một số ví dụ về nguyên lý Dirichlet. .. .. .. .1.2Ứng dụng nguyên lý Dirichlet vào số học. .. .. .. . .1.3Ứng dụng nguyên lý Dirichlet vào hình học. .. .. .. .141.4Ứng dụng nguyên lý Dirichlet vào giải các bài toán khác241.5Bài tập áp dụng. .. .. .. .. .. .. .. .. .. .. . .272 Nguyên lý cực hạn và ứng dụng trong toán sơ cấp292.1Nguyên lý cực hạn. .. .. .. .. .. .. .. .. .. . .292.2Ứng dụng nguyên lý cực hạn vào số học.. .. .. .. .302.3Ứng dụng nguyên lý cực hạn vào hình học. .. .. .. .362.4Ứng dụng nguyên lý cực hạn vào giải các bài toán khác .422.5Bài tập áp dụng. .. .. .. .. .. .. .. .. .. .. . .46Footer Page 3 of 161.Header Page 4 of 161.MỤC LỤCMỤC LỤC3 Nguyên lý xuống thang và ứng dụng trong toán sơ cấp473.1Nguyên lý xuống thang. .. .. .. .. .. .. .. .. . .473.2Ứng dụng nguyên lý xuống thang vào số học. .. .. . .483.3Ứng dụng nguyên lý xuống thang vào hình học. .. .. .563.4Ứng dụng nguyên lý xuống thang vào các bài toán khác .593.5Bài tập áp dụng. .. .. .. .. .. .. .. .. .. .. . .62Tài liệu tham khảo64iiFooter Page 4 of 161.Header Page 5 of 161.Lời cảm ơnEm xin bày tỏ lòng biết ơn sâu sắc đến TS. Nguyễn Thị Kiều Nga, ngườiđã tận tình hướng dẫn để em có thể hoàn thành khóa luận này.Em cũng xin bày tỏ lòng biết ơn chân thành tới các thầy cô giáo trongkhoa Toán, các thầy cô trong tổ Đại số và thư viện trường Đại học Sưphạm Hà Nội 2 đã giúp đỡ em trong suốt quá trình học tập tại trường.Hà Nội, tháng 5 năm 2016Sinh viênPhan Thị Tuyết ChinhFooter Page 5 of 161.Header Page 6 of 161.Lời cam đoanEm xin cam đoan, dưới sự hướng dẫn của TS. Nguyễn Thị Kiều Nga,khóa luận chuyên ngành Đại số với đề tài:”Một số nguyên lý cơ bảnvà ứng dụng” được hoàn thành bởi sự nhận thức và tìm hiểu của bảnthân.Trong quá trình nghiên cứu và thực hiện khóa luận, em có tham khảotài liệu của một số tác giả với sự biết ơn chân thành.Hà Nội, tháng 5 năm 2016Sinh viênPhan Thị Tuyết ChinhFooter Page 6 of 161.Header Page 7 of 161.Mở đầu1. Lí do chọn đề tàiTrong nhà trường, môn toán giữ một vị trí hết sức quan trọng. Nógiúp học sinh học tốt các môn học khác, là công cụ của nhiều ngànhkhoa học và là công cụ để hoạt động trong đời sống thực tế. Đặc biệtToán sơ cấp không chỉ gần gũi với các em học sinh mà còn có tác dụngtrong việc khai thác và phát triển năng lực trí tuệ chung, rèn luyện cácthao tác và phẩm chất tư duy của chúng.Có rất nhiều phương pháp khác nhau để giải quyết các bài toán sơcấp, trong đó người ta có thể sử dụng một công cụ hữu ích là các nguyênlý cơ bản. Đây là cách đưa các bài toán đã cho về các bài toán đơn giảnhơn, sử dụng linh hoạt các nguyên lý này sẽ là một lợi thế lớn giúp cácem học sinh phát triển niềm đam mê với toán học và năng lực tư duycủa bản thân.Vì các lý do trên, cùng với sự hướng dẫn của cô Nguyễn Thị KiềuNga tôi đã chọn đề tài: “Một số nguyên lý cơ bản và ứng dụng”.Khóa luận gồm ba chương:Chương 1: Nguyên lý Dirichlet và ứng dụng trong toán sơ cấp.Chương 2: Nguyên lý cực hạn và ứng dụng trong toán sơ cấp.Chương 3: Nguyên lý xuống thang và ứng dụng trong toán sơ cấp.2. Mục đích nghiên cứuSử dụng các nguyên lý cơ bản để giải các bài toán sơ cấp.Footer Page 7 of 161.Header Page 8 of 161.3. Đối tượng nghiên cứu- Nguyên lý cơ bản.- Các bài toán sơ cấp được ứng dụng các nguyên lý cơ bản.4. Phương pháp nghiên cứuTham khảo tài liệu, phân tích, so sánh và hệ thống hóa và tổng hợp.Footer Page 8 of 161.Header Page 9 of 161.Chương 1Nguyên lý Dirichlet và ứng dụngtrong toán sơ cấp1.1Nguyên lý DirichletNhà toán học nổi tiếng người Đức Peter Gustav Lejeune Dirichlet (1805−1859) là người đầu tiên phát biểu quy tắc chia phân tử vào các lớp. Quytắc này được gọi là “Nguyên lý Dirichlet” hay còn gọi là “Nguyên lýLồng và Thỏ” hoặc “Nguyên lý ngăn kéo”. Nguyên lý này được phátbiểu đơn giản là: nếu đem nhốt n + 1 con thỏ vào n chiếc lồng thì luôncó một cái lồng chứa ít nhất 2 con thỏ.Chứng minh. Ta chứng minh bằng phản chứng. Giả sử n + 1 con thỏnhốt vào n chiếc lồng mà không lồng nào chứa 2 con thỏ trở lên, tức mỗilồng chứa không quá 1 con thỏ. Như vậy, n chiếc lồng chứa không quán con thỏ. Mâu thuẫn với giả thiết có n + 1 con thỏ. Suy ra giả sử sai.Vậy ta có điều phải chứng minh.Sau đây là một số dạng phát biểu khác của Nguyên lý Dirichlet:Footer Page 9 of 161.Header Page 10 of 161.1.1.1Nguyên lý Dirichlet mở rộngNếu nhốt n con thỏ vào k cái lồng (k ≤ n) thì luôn có một cái lồng chứaít nhấtcon thỏ, trong đó x là số nguyên nhỏ nhất lớn hơn hoặcbằng x.Chứng minh. Ta xét hai trường hợp sau:Trường hợp 1. Nếu n .. k, tức n = k.a với a ∈ Z thì ta giả sử mỗi= a con thỏ, nghĩa là mỗi lồng chỉ có ítlồng thỏ không có đếnhơn hoặc bằng a − 1 con. Từ đó suy ra tổng số con thỏ không vượt quák.(a − 1) = k.a − k = n − k < n con thỏ (mâu thuẫn với giả thiết có ncon thỏ). Do đó điều giả sử là sai.Trường hợp 2. Nếu n không chia hết cho k, tức n = ka + r với 1 ≤ r ≤k − 1, (a, r ∈ Z) thì ta giả sử mỗi lồng thỏ không có đến= a+1con thỏ, nghĩa là mỗi lồng có ít hơn hoặc bằng a con. Khi đó, k lồng chỉcó k.a = n − r < n con (mâu thuẫn với giả thiết có n con thỏ).Do đóđiều giả sử là sai.Vậy ta có điều phải chứng minh.1.1.2Nguyên lý Dirichlet dưới dạng tập hợp hữu hạnCho A và B là hai tập hợp không rỗng có số phần tử hữu hạn mà sốphần tử của A lớn hơn số phần tử của B. Nếu với một quy tắc nào đómà mỗi phần tử của A tương ứng với một phần tử của B thì tồn tại ítnhất 2 phần tử khác nhau của A cùng tương ứng với một phần tử củaB.1.1.3Nguyên lý Dirichlet dưới dạng tập hợp hữu hạn mở rộngCho hai tập hợp hữu hạn A và B, gọi |A| và |B| lần lượt là số phần tửcủa A và B. Giả sử có một số tự nhiên k nào đó mà |A| > k. |B| và cómột quy tắc tương ứng mỗi phần tử của A với một phần tử của B. KhiFooter Page 10 of 161.Header Page 11 of 161.đó tồn tại ít nhất k + 1 phần tử khác nhau của A cùng tương ứng vớimột phần tử của B.1.1.4Nguyên lý Dirichlet trong hình họcNguyên lý Dirichlet cho diện tích: Cho A là một hình phẳng, A1, A2, …, Anlà các hình phẳng sao cho Ai ⊆ A và SA m). Khi đó:n chữ số a m chữ số aFooter Page 16 of 161.10Header Page 17 of 161.aaa…a − aaa…a = aaa…a00…0 .n chữ số am chữ số a1993Vì (10,23) = 1 nên (10k, 2312n – m chữ số a, m số 01993) = 1 nên aaa…a .. 2312. (*)n – m số aMặt khác, do có vô số số a như trên nên từ (*) suy ra tồn tại vô số chiahết cho 23121993mà trong biểu diễn thập phân của chúng không có cácchữ số 0, 1, 2, 3.Bài tập 1.8. Cho 5 số nguyên phân biệt tùy ý: a1, a2, a3, a4, a5. Xét tíchP = (a1 − a2 )(a1 − a3 )(a1 − a4 )(a1 − a5 )(a2 − a3 )(a2 − a4 )(a2 − a5 )(a3 −a4 )(a3 − a5 )(a4 − a5 ). Chứng minh rằng: P .. 288.GiảiTa thấy 288 = 25 .32 mà (2,3) = 1 nên để chứng minh P .. 288 ta sẽ đichứng minh P đồng thời chia hết cho 25 và 32. Theo nguyên lý Dirichletthì trong n + 1 số nguyên tùy ý luôn tồn tại 2 số có hiệu chia hết chon (tức 2 số đó chia cho n có cùng số dư). Vậy trong 4 số a1, a2, a3, a4có 2 số có hiệu chia hết cho 3, không làm giảm tính tổng quát giả sử:a1 − a2 .. 3. Bây giờ xét tiếp 4 số a2, a3, a4, a5, lập luận như trên ta đượchiệu của 2 số chia hết cho 3, mà hiệu này khác a1 − a2 (vì a1 không thuộcdãy đang xét). Như thế trong tích P đã cho có 2 hiệu khác nhau cùngchia hết cho 3 suy ra P .. 32 (1). Lại theo nguyên lý Dirichlet thì trong 5số đã cho có ít nhất= 3 có cùng tính chẵn, lẻ nên ta xét 2 trườnghợp sau:Trường hợp 1. Nếu có ít nhất 4 số cùng tính chẵn lẻ thì từ 4 số này cóthể lập nên 6 hiệu khác nhau cùng chia hết cho 2, do đó tích của chúngsẽ chia hết cho 26. Hiển nhiên nó chia hết cho 25 hay P .. 25 .Trường hợp 2. Nếu có đúng 3 số cùng tính chẵn lẻ. Không làm giảmtính tổng quát ta giả sử 3 số đó là a1, a2, a3. Khi đó còn lại 2 số làa4, a5 cũng có tính chẵn lẻ giống nhau nhưng khác tính chẵn lẻ của 3 sốa1, a2, a3. Suy ra 4 hiệu sau chia hết cho 2:Footer Page 17 of 161.11Header Page 18 of 161.a1 − a2 ; a1 − a3 ; a2 − a3 ; a4 − a5 .Mặt khác, trong 5 số đã cho có ít nhất có 2 số có hiệu chia hết cho 4.Vì thế trong 4 số a1 − a2 ; a1 − a3 ; a2 − a3 ; a4 − a5 có ít nhất 1 chia hếtcho 4. Do đó: (a1 − a2 )(a1 − a3 )(a2 − a3 )(a4 − a5 ) .. 25 hay P .. 25. (2)Kết hợp (1) và (2) suy ra: P .. 288.Bài tập 1.9. Xét tập M gồm 2016 số nguyên dương phân biệt sao chokhông có số nào trong chúng có ước nguyên tố lớn hơn 23. Chứng minhrằng M chứa 1 tập hợp con gồm 4 phần tử mà tích của 4 phần tử nàylà lũy thừa bậc 4 của 1 số nguyên.GiảiTa thấy chỉ có 9 số nguyên tố không lớn hơn 23 là: p1 = 2, p2 = 3, p3 =5, p4 = 7, p5 = 11, p6 = 13, p7 = 17, p8 = 19, p9 = 23.Gọi k là 1 phần tử bất kỳ của tập M .Khi đó, k có biểu diễn như sau: k = pk11 .pk22 …pk99 (*) trong đó ki, i = 1, 9là các số nguyên không âm. Với mỗi phần tử k của tập hợp M ta gánvới một dãy (x1, x2, …, x9 ) trong đó:0 nếu số mũ k của p trong (*) là chẵnxi =1 nếu số mũ k của p trong (*) là lẻ.Tập hợp dãy (x1, x2, …, x9 ) như vậy gồm 29 phần tử. Ta thấy: 29 + 1 =513 < 2016. Trong mọi tập hợp con chứa không ít hơn 29 + 1 phần tửcủa M luôn chứa ít nhất 2 số nguyên phân biệt a1, b1 cố cùng bộ sắpxếp gồm số 0 và 1 giống nhau. Giả sử bộ sắp xếp đó là: x1, x2, ..., x9 và2 số a1, b1 có biểu diễn:a1 = pk11 .pk22 ...pk99 và b1 = p11 .p22 ...p99 .Khi đó suy ra: ki, ki có cùng tính chẵn lẻ, ∀i = 1, 9. Do đó:k +k1a1 .b1 = p11Footer Page 18 of 161.k +k2.p2212k +k9...p99= c2 .Header Page 19 of 161.(Vì mỗi số tự nhiên là số chính phương khi và chỉ khi tất cả số mũ trongbiểu diễn tiêu chuẩn đều chẵn).Nói cách khác, ta lấy đi một cặp (a1, b1 ) như thế từ tập M thì tập Mcòn lại 2016 − 2 = 2014 > 29 + 1 = 513 số.Tiếp tục áp dụng nguyên lý Dirichlet và lấy đi những cặp số như trêncho đến khi còn lại 29 + 1 phần tử trong M .Mà để ý rằng: 2016 > 3.(29 + 1) = 3.513 = 1539 nên ta có thể lấy đi29 + 1 cặp (ai, bi ). Đến đây số phần tử còn lại trong M là:2016 − 2.(29 + 1) = 990 > 513 = 29 + 1.Xét 29 +1 cặp được lấy đi. Ứng với mỗi cặp (ai, bi ) ta có c2i = ai .bi, i = 1, 9.Suy ra: ci = ai .bi. Mặt khác, các số ai, bi chỉ chứa các số nguyên tố pi ,i = 1, 9 nên ci cũng như vậy. Bằng cách lập luận như trên trong 29 + 1 sốci ta luôn tìm được ít nhất 2 số nguyên ci, cj phân biệt có cùng bộ sắpxếp 0 và 1 giống nhau. Do đó tồn tại số nguyên d thỏa mãn: d2 = ci .cjsuy ra d4 = c2i .c2j = ai .bi .aj .bj. Vậy ta có điều phải chứng minh.Bài tập 1.10. Chứng minh trong 12 số nguyên tố phân biệt luôn luônchọn ra được 6 số a1, a2, a3, a4, a5, a6 sao cho(a1 − a2 )(a3 − a4 )(a5 + a6 ) .. 1800.GiảiVì 3 số nguyên tố đầu tiên là 2, 3, 5 nên trong 12 số nguyên tố phânbiệt đã cho luôn có 9 số lớn hơn 5. Do đó,+) Chín số nguyên tố lớn hơn 5 khi chia cho 3 luôn dư 2 hoặc 1. Theonguyên lý Dirichlet phải tồn tại ít nhất= 5 số chia hết cho 3 cócùng số dư. Năm số này lại không chia hết cho 5 nên theo nguyên lýDirichlet trong 5 số ấy có ít nhất= 2 số chia cho 5 có cùng số dư (vìkhi chia cho 5 có 4 số dư là 1, 2, 3, 4). Không làm giảm tính tổng quátFooter Page 19 of 161.13Header Page 20 of 161.ta giả sử hai số đó là a1, a2, khi đó a1 ≡ a2 (mod 5) và a1 ≡ a2 (mod 3).Từ đây suy ra: a1 − a2 .. 15 (1).Mặt khác, do a1, a2 là các số nguyên tố lơn hơn 5 nên a1, a2 đều là cácsố lẻ hay a1 − a2 .. 2 (2). Lại có: (2, 15) = 1 nên từ (1) và (2) suy ra:a1 − a2 .. 30.=4+) Trong 7 số còn lại, theo nguyên lý Dirichlet tồn tại ít nhâtsố khi chia cho 3 có cùng số dư. Đem 4 số này chia cho 5 xảy ra 2 trườnghợp sau:Trường hợp 1. Giả sử có 2 số a3, a4 thỏa mãn: a3 ≡ a4 (mod 5) thìtương tự cách lập luận trên ta suy ra được: a3 − a4 .. 5, a3 − a4 .. 3 vàa3 − a4 .. 2 suy ra a3 − a4 .. 30 (do (5,2,1) = 1). Lấy 2 số a5, a6 bất kỳtrong 9 số khác các số a1, a2, a3, a4 đã chọn. Ta thấy a5, a6 đều là các sốlẻ nên a5 + a6 .. 2. Từ đây suy ra: (a1 − a2 )(a3 − a4 )(a5 + a6 ) .. 1800.Trường hợp 2. Nếu 4 số này chia cho 5 có 4 số dư khác nhau là 1,2, 3, 4. Không làm giảm tính tổng quát, ta giả sử: a5 ≡ 1(mod 5) vàa6 ≡ 4(mod 5) suy ra a5 + a6 ≡ 5(mod 5) hay a5 + a6 .. 5. (3) (Tương tựta chứng minh cho trường hợp a5 ≡ 2(mod 5) và a6 ≡ 3(mod 5)). Với 2số còn lại ta gọi là a3, a4. Theo cách chọn 4 số ở trên ta có 2 số khi chiacho 3 thì có cùng số dư (theo nguyên lý Dirichlet). Khi đó: a3 − a4 .. 3(4). Mà a3, a4, a5, a6 là các số nguyên tố lớn hơn 5 nên a3, a4, a5, a6 đềulà số lẻ. Suy ra: a5 + a6 .. 2 (5) và a3 − a4 .. 2 (6). Kết hợp (3) và (5) suyra: a5 + a6 .. 10 ( do (2,5) = 1). Kết hợp (4) và (6) suy ra: a3 − a4 .. 6 (do (2,3) = 1). Vậy: (a1 − a2 )(a3 − a4 )(a5 + a6 ) .. 30.10.6 = 1800.Tóm lại ta có luôn có điều phải chứng minh.1.3Ứng dụng nguyên lý Dirichlet vào hình họcTrong mục này, ta sử dụng nguyên lý Dirichlet vào giải các bài toánhình học. Thường phương pháp Dirichlet được áp dụng kết hợp kèmtheo phương pháp phản chứng hay các phép biến hình.Footer Page 20 of 161.14Header Page 21 of 161.Bài tập 1.11. Trong hình vuông cạnh 1, đặt 51 điểm phân biệt bất kỳ.Chứng minh rằng có ít nhất 3 trong số 51 điểm đó nằm trong một đườngtròn bán kính .GiảiTa chia hình vuông đã cho thành 25 hình vuông con bằng nhau có cạnhbằng. Theo nguyên lý Dirichlet tồn tại ít nhất một hình vuông con C51= 3 điểm trong số 51 điểm ban đầu. Đường tròn (C)chứa ít nhất25ngoại tiếp hình vuông con C có bán kính √ < .5 2 7Vậy 3 điểm nói trên nằm trong một đường tròn bán kính .Nhận xét: Ta có thể tổng quát bài toán trên như sau: Trong hìnhvuông có cạnh bằng a đặt m điểm phân biệt bất kỳ. Chứng minh có ítnhất n điểm trong m điểm đã cho nằm trong một đường tròn bán kínha2(trong đó [a] là phần nguyên của a).2.n−1Bài tập 1.12. Cho S là một tập hợp gồm 9 điểm khác nhau có các tọađộ nguyên trong không gian. Chứng minh rằng có ít nhất một trung điểmcủa đường nối các cặp điểm đã cho có tọa độ nguyên.GiảiGọi tọa độ 2 điểm bất kỳ trong không gian là A(a, b, c) và B(d, e, f ). Khia+d b+e c+fđó trung điểm O của đoạn AB là: O().Các tọa độ của điểm O nguyên nếu và chỉ nếu a và d, b và e, c và f cùngtính chẵn lẻ. Mà có 23 = 8 bộ ba chẵn lẻ khác nhau là:(c, c, c); (l, l, l); (c, c, l); (c, l, l); (c, l, c); (l, c, c); (l, c, l); (l, l, c).Nên theo nguyên lý Dirichlet có ít nhất 2 trong 9 điểm có cùng bộ bachẵn lẻ như nhau. Vậy có ít nhất một cặp điểm mà trung điểm giữaFooter Page 21 of 161.15Header Page 22 of 161.chúng có tọa độ nguyên.Nhận xét: ta có thể tổng quát bài toán trên trong không gian nhưsau: Trong không gian, cho tập hợp gồm m điểmkhác nhau có các tọa độ1+8 nguyên. Chứng minh rằng có ít nhất  trung điểm của đườngnối các cặp điểm đã cho có tọa độ nguyên.Bài tập 1.13. Trong mặt phẳng cho 25 điểm. Biết rằng trong 3 điểmbất kỳ của 25 điểm luôn tồn tại 2 điểm cách nhau nhỏ hơn 1. Chứngminh rằng tồn tại đường tròn bán kính 1 chứa không ít hơn 13 điểm đãcho.GiảiLấy A là 1 trong số 25 điểm đã cho. Xét đường tròn Ω1 (A, 1), chỉ có 2khả năng sau xảy ra:Trường hợp 1. Nếu tất cả các điểm đã cho nằm trong Ω1 thì ta có điềuphải chứng minh.Trường hợp 2. Ngược lại, tồn tại điểm B, (A = B), B là 1 trong số 25điểm đã cho và thỏa mãn B ∈/ Ω1. Do đó AB > 1.Xét đường tròn Ω2 (B, 1), lấy C là điểm bất kỳ trong số 23 điểm còn lại.Theo giả thiết trong 3 điểm bất kỳ thì trong đó luôn tồn tại 2 điểm cókhoảng cách nhỏ hơn 1 mà AB > 1 nên min{CA, CB} < 1. Từ đây suyra C ∈ Ω1 hoặc C ∈ Ω2. Như vậy chứng tỏ rằng các đường tròn Ω1 và Ω2Footer Page 22 of 161.16Header Page 23 of 161.chứa tất cả 25 điểm đã cho. Vì thế theo nguyên lý Dirichlet có ít nhất 125= 13 điểm đã cho.trong 2 đường tròn nói trên chứa không ít hơnNhận xét: ta có thể tổng quát bài toán trên như sau: Cho 2n + 1điểm trên mặt phẳng (n ≥ 3). Biết trong 3 điểm bất kỳ trong đó luôntồn tại 2 điểm cách nhau nhỏ hơn 1. Chứng minh rằng tồn tại đườngtròn bán kính 1 chứa không ít hơn n + 1 điểm.Bài tập 1.14. Một khu rừng thông hình vuông, mỗi chiều dài 1000m.Trong khu rừng có 4500 cây thông, cây to nhất đường kính 0,5m.Chứngminh rằng trong khu rừng có ít nhất 60 mảnh đất, diện tích mỗi mảnh200m2 không có một cây thông nào.GiảiTa thấy: 1000m = 48.20m + 47.0.6m + 2.5,9m và : 1000m = 95.10m +94.0,52m + 2.0,56m.Ta chia một cạnh hình vuông thành 48 đoạn dài 20m, khoảng cáchgiữa 2 đoạn là 0,6m, ở 2 đầu là 2 đoạn 5,9m. Còn ạnh còn lại của hìnhvuông chia thành 95 đoạn dài 10m, khoảng cách giữa 2 đoạn là 0,52mvà 2 đầu là 2 đoạn dài 0,56m. Như vậy, ta có tất cả 45.95 = 4560 mảnhcó diện tích 200m2 .Mà theo giả thiết, chỉ có 4500 cây thông, mỗi cây có đường kính 0,5m(0,5 < 0,56 < 0,6) nên mỗi cây thông bất kỳ không thể nằm trên 2 mảnhcùng lúc.Vì thế còn ít nhất 60 mảnh (diện tích 200m2 ) không có cây thông nào.Footer Page 23 of 161.17Header Page 24 of 161.Bài tập 1.15. Cho 9 đường thẳng cùng có tính chất là mỗi đường thẳngchia hình vuông thành 2 tứ giác có tỉ số diện tích là. Chứng minh rằngcó ít nhất 3 đường thẳng trong số đó cùng đi qua 1 điểm.GiảiCác đường thẳng đã cho không thể cắt 2 cạnh kề nhau của một hìnhvuông, bởi nếu thế chúng chia hình vuông thành 1 tam giác và 1 ngũgiác (mâu thuẫn với giả thiết). Do đó 9 đường thẳng đã cho sẽ cắt 2cạnh đối của hình vuông và không đi qua 2 đỉnh nào của hình vuông.Giả sử 2 đường thẳng bất kỳ cắt 2 cạnh AD, BC tại M, N.Gọi E, F, P, Q lần lượt là trung điểm của AB, CD, BC, AD.Gọi J1, J2, J3, J4 nằm trên EF, PQ và thỏa mãn:F J2P J3QJ4EJ1= .F J1EJ2QJ3P J4Khi đó ta cóSABM NSCDN MAB.(BM + AN )EJ1= .J1 FCD.(M C + N D)Từ cách lập luận trên suy ra mỗi đường thẳng có tính chất thỏa mãnyêu cầu đề bài phải đi qua 1 trong 4 điểm J1, J2, J3, J4 nói trên. Vậy theonguyên lý Dirichlet, trong 9 đường thẳng đã cho tồn tại ít nhất=3đường thẳng đi qua 1 trong 4 điểm J1, J2, J3, J4 .Footer Page 24 of 161.18Header Page 25 of 161.Bài tập 1.16. Trên mặt phẳng, cho 9 điểm được nối với nhau đôi mộtbới các đoạn màu xanh hoặc màu đỏ sao cho trong 3 điểm bất kỳ bao giờcũng tìm đk 2 điểm nối với nhau bởi màu đỏ. Chứng minh rằng trong sốcác điểm đã cho luôn tìm được 4 điểm mà các đoạn thẳng nối chúng đềucó màu đỏ.GiảiGọi 9 điểm đã cho là:A, B, C, D, E, F, G, H, I. Xét 2 trường hợp:Trường hợp 1. Tìm được 1 điểm là đầu mút của ít nhất 4 đoạn nốimàu xanh, giả sử đó là điểm A và các đoạn màu xanh là AB, AC, AE.Theo giả thiết, trong số 3 đoạn nối 3 điểm bất kỳ luôn có 1 đoạn màuđỏ nên các đoạn BC, BD, CD, CE, DE có màu đỏ. Vậy B, C, D, E là 4điểm cần tìm.Trường hợp 2. Mỗi điểm đều là đầu mút của nhiều nhất 3 đoạn màuxanh. Khi đó không thể xảy ra trường hợp cả 9 điểm đều là đầu mútcủa 3 đoạn màu xanh (vì khi đó sẽ có 9.3 :2 = 13,5 đoạn thẳng). Dođó phải tìm được 1 điểm là mút của 2 đoạn màu xanh, giả sử điểm đólà điểm I. Khi đó I là đầu mút của ít nhất 6 đoạn màu đỏ, giả sử làIA, IB, IC, ID, IE, IF. Theo kết quả bài tập trước có ít nhất 3 trongsố 6 điểm A, B, C, D, E, F tạo thành một tam giác cùng màu. Khônglàm giảm tính tổng quát giả sử tam giác đó là ABC. Mặt khác, theo giảthiết 3 đoạn nối 3 điểm bất kỳ luôn có 1 đoạn màu đỏ nên ABC là tamgiác đỏ.Vậy A, B, C, I là 4 điểm cần tìm.Bài tập 1.17. Cho mỗi điểm trên mặt phẳng được tô bằng 2 màu xanh,đỏ. Chứng minh rằng tồn tại một tam giác mà ba đỉnh và trọng tâm cùngmàu.GiảiLấy 5 điểm tùy ý sao cho không có 3 điểm nào thẳng hàng trên mặtphẳng. Vì chỉ dùng 2 màu xanh, đỏ nên theo nguyên lý Dirichlet phảiFooter Page 25 of 161.19

VIETLIKE.VN

CEO: Công ty TNHH Công Nghệ Truyền Thông Ez Media.

Trả lời

Email của bạn sẽ không được hiển thị công khai.

Back to top button