Nguyên lý chuồng bồ câu | Bài giảng môn Toán rời rạc

TOÁN RỜI RẠC PHÉP ĐẾM
NGUYÊN LÝ CHUỒNG BỒ CÂU 1 NỘI DUNG 1.Giới thiệu 2.Các định lí 3.Ứng dụng 4.Ví dụ & bài tập 5.Kết luận 2
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm
Giới Thiệu Nguyên L ý
Nguyên lý chuồng bồ câu được dùng rất nhiều trong thực tế:
“Trong một lớp có 40 học sinh thì luôn có ít nhất
4 người bằng điểm nhau” (thang điểm 10 và điểm là số nguyên)
“Nhốt 5 con thỏ trong 4 cái chuồng thì có một cái
chuồng có ít nhất 2 con thỏ” 3
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm
Giới Thiệu Nguyên L ý
Nguyên lí chuồng bồ câu được cho được Johann
Dirichlet phát biểu lần đầu tiên vào năm 1834 dưới tên “Schubfachprinzip” 4
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm
Vài Nét Về Dirichlet
Dirichlet tên đầy đủ là Johann Peter Gustav Lejeune Dirichlet (1805-1859)
Ông sinh ra tại Düren (Đức) và học tại đại học Bonn và
từng công tác đại học Berlin. Ông được xem là người
đầu tiên đưa ra định nghĩa hiện đại của hàm số: 5
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm
Vài nét về Dirichlet
Các định lý mang tên Định lý Dirichlet:
Định lý Dirichlet về cấp số cộng
Định lý Dirichlet về xấp xỉ diophantine
Định lý Dirichlet về phần tử đơn vị 6
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm
Vài nét về Dirichlet
Johann Peter Gustav Lejeune Dirichlet (1805-1859) 7
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm
Nguyên lý chuồng bồ câu Định Lý 1:
“Nếu xếp m đối tượng vào n cái hộp và m > n
thì có ít nhất một cái hộp chứa từ 2 đối tượng trở lên” 8
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm
Nguyên lý chuồng bồ câu Ví dụ:
Có 10 con bồ câu nhưng lại chỉ có 9 ô thì có ít
nhất một ô có 2 con bồ câu 9
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm
Nguyên lý chuồng bồ câu Định Lý 2:
“Nếu xếp N đối tượng vào k cái hộp thì tồn tại
ít nhất một cái hộp chứa N/k đối tượng.”
N/k là số nguyên nhỏ nhất lớn hơn hoặc bằng N/k. 10
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm
Nguyên lý chuồng bồ câu Ví dụ:
- Trong lớp có 43 sinh viên nên có ít nhất 4 sinh viên sinh cùng một tháng.
( 4 là số nguyên nhỏ nhất lớn hơn hoặc bằng 43/12)
- Nếu lấy 20 trái cam chia cho 9 người thì có một
người được từ 3 trái trở lên 11
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm
Nguyên lý chuồng bồ câu Định Lý 3:
“Một dãy số có n2+1 số thực khác nhau thì bao
gồm trong nó ít nhất một dãy số có n+1 số mà dãy
đó tăng dần hoặc giảm dần.” 12
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm
Nguyên lý chuồng bồ câu Ví dụ:
Dãy số số sau có 10 số khác nhau : 10, 17, 8, 4, 12, 15, 18, 9, 7, 1
Nên dãy trên có ít nhất một dãy có 4 số mà dãy đó
tăng dần hoặc giảm dần.
10, 12, 15, 18 là dãy tăng dần… 13
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm Ứng Dụng
Nguyên lý chuồng bồ câu được vận dụng rất nhiều trong thực tế.
Nhờ 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 vật cụ thể. Ví dụ:
Trong toán học: chứng minh sự tồn tại của một số chia hết 2011
mà các chữ số đều bằng 1 14
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm Ứng Dụng Trong thực tế:
- Trong 64 người thi ít nhất có 2 người sinh ra ở cùng 1 tỉnh.
- Nếu bạn bắn rơi n con bồ câu với m lần bắn
(m < n) thì có ít nhất một lần bạn bắn rơi hơn một con bồ câu.
- Được sử dụng trong một số trò ảo thuật… 15
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm Một số Ví Dụ  1)
Chứng minh rằng nếu có 101 người có chiều cao khác
nhau đang xếp thành một hàng thì luôn tìm được 11
người trong hàng xếp theo mà 11 người này đang xếp
theo chiều cao tăng dần hoặc giảm dần.  16
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm Một số Ví Dụ Bài giải 
Xem chiều cao của 101 người là một dãy 101 số khác nhau. Ta có: 101 = 102 + 1
Theo định lý 3 ta có trong dãy 101 số trên có một dãy 11
số (10 + 1) mà dãy đó tăng dần hoặc giảm dần (đpcm)  17
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm Một số Ví Dụ
2) Chứng minh rằng trong số 12 số tự nhiên bất kỳ có thể chọn 
hai số có hiệu chia hết cho 11. Bài giải:
Khi chia 12 số bất kỳcho11tasẽcómỗisốcó
một số dư trong 11 số dư: 0, 1, 2,…, 10. Do đó theo
nguyên lý Dirichlet phải tồn tại ít nhất hai số có cùng
số dư. Hiệu của hai số đó sẽ chia hết cho 11. 18
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm Một số Ví Dụ
3) 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 . 19
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm Một số Ví Dụ Bà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 => có tối đa 4 loại số trận đã đấu.
Vận dụng nguyên lý chuồng bồ câu ta có ít nhất có 2
người có cùng số trận đã đấu. 20
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm Một số Ví Dụ
4) CMR tồn tại một số tự nhiên gồm toàn
chữ số 1 chia hết cho 2007. Bài giải:
Xét 2008 số gồm toàn chữ số 1. Theo nguyên lý
chuồng bồ câu sẽ tồn tại 2 số khi chia cho 2007 cùng số dư. 21
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm Một số Ví Dụ Giả sử số a = 11…1(có m chữ số 1) b = 11…1(có n chữ số 1) (m > n)
a – b = 11…1 .10n (có m - n chữ số 1)
Vì a và b có cùng số dư khi chia cho 2007 nên a –b chia hết cho 2007
mà 10n không chia hết cho 2007
nên 11…1(có m - n chữ số 1) chia hết cho 2007(đpcm) 22
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm Bài Tập
1 .CMR: tồn tại một số tự nhiên: 0(25x - 1) chia hết cho 17
2. Chứng minh trong n người (n≥2) thì luôn có ít
nhất 2 người có số người quen (trong số n người) giống nhau . 23
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm Bài Tập
3. Cho một hình vuông và 13 đường thẳng, mỗi
đường thẳng đều chia hình vuông thành hai tứ giác
có tỉ số diện tích 2:3. CMR trong số 13 đường
thẳng đó, có ít nhất 4 đường thẳng cùng đi qua một điểm. 24
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm
Hướng Dẫn Bài Tập Câu 1:
Sử dụng phương pháp phản chứng.
(giả sử không có số x nào thỏa yêu cầu => không có
2 số x sao cho (25x-1) khi chia 17 có cùng số dư (ở
đây sử dụng phương pháp chứng minh gián tiếp) từ
đó suy ra 25x chia hết cho 17 (vô lý)). 25
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm
Hướng Dẫn Bài Tập Câu 2:
Có thể tham khảo ví dụ 3 Câu 3:
Chỉ ra 4 điểm mà các đường thẳng đi qua nó sẽ
chia hình vuông thành 2 tứ giác có tỉ số diện tích là 2:3 26
Toán rời rạc: 2011 - 2012 Chương 5: Phép đếm