#1
Nguyễn Hoàng Nam
-
- Thành viên
-
- 334 Bài viết
Độc thân...
- Giới tính:Nam
- Đến từ:Hà Nội
- Sở thích:Kiếng cận và tất cả những gì liên quan đến kiếng cận ^^!
Đã gửi 11-09-2010 - 21:42
Chào mừng VMF vừa mới trở lại
Mình xin post một chuyên đề về nguyên tắc Đi-rích-lê, hay còn gọi là nguyên tắc nhốt thỏ vào lồng. Bài viết có sử dụng nguồn từ khá nhiều sách, các bạn đọc tạp chí Toán học tuổi trẻ để biết thêm
Nguyên tắc Đi-rích-lê được phát biểu dưới dạng bài toán như sau:
Nếu đem m thỏ vào n lồng với m>n thì ít nhất cũng có một lồng nhốt không ít hơn 2 thỏ. Tương
tự, nếu đem m đồ vật vào n ô ngăn kéo, với m>n, thì ít nhất cũng phải có 1 ô ngăn kéo chứa không ít hơn 2 đồ vật
Phần chứng minh bài toán, các bạn chắc gần như ai cũng biết, mình chỉ xin nêu một vài bài toán vận dụng cơ bản.
Ví dụ 1:
Trong một lớp chuyên toán có 40 học sinh. Trong một kỳ kiểm tra chất lượng môn toán chỉ có một em đạt điểm tối đa là 10, và một em đạt điểm 4, các em khác đạt từ điểm 5 trở lên. Chứng minh rằng trong lớp ít nhất cũng có 8 em có điểm
số như nhau, biết rằng điểm số các em đều là các số nguyên.
Lời giải:
Theo giả thiết của bài toán thì chỉ có một em đạt điểm 10 và một em đạt điểm 4, do đó sẽ có $40-2=38$ em đạt điểm 5 đến điểm 9. Coi mỗi học sinh là một "thỏ", mỗi loại điểm là 1 "lồng", như vậy ta sẽ có các lồng sau:
"Lồng 5": nhốt những ai đạt điểm 5
"Lồng 6": nhốt những ai đạt điểm 6
"Lồng 7": nhốt những ai đạt điểm 7
"Lồng 8": nhốt những ai đạt điểm 8
"Lồng 9": nhốt những ai đạt điểm 9
Với 5
lồng nhốt 38 thỏ, vậy có ít nhất một lồng nhốt không ít hơn 8 thỏ, bài toán được chứng minh.
Ví dụ 2:
Cho 10 số tự nhiên bất kỳ: $a_1, a_2, a_3...,a_9,a_10$
Chứng minh rằng thế nào cũng có một số hoặc tổng một số số liên tiếp nhau trong dãy 10 số đã cho chia hết cho 10.
Lời giải:
Để làm xuất hiện khái niệm "thỏ", "lồng", ta thành lập dãy số mới sau đây:
Đặt
$B_1=a_1$
$B_2=a_1+a_2$
$B_3=a_1+a_2+a_3$
$B_4=a_1+a_2+a_3+a_4$
...
$B_10=a_1+...+a_10$
Ta thấy rằng:
- Nếu tồn tài một $B_i$ nào đó [i=1,2,3,...,10] chia hết cho 10 thì bài toán đã được chứng minh.
- Nếu không tồn tại một $B_1$ nào đó chia hết cho 10 thì ta chỉ việc đem tất cả $B_i$ chia cho 10, lúc đó được 10 số dư từ 1-9, trong khi đó các số tự nhiên từ 1-9 chỉ có 9 số [như vậy tương đương với việc nhốt 10 chủ thỏ vào 9 lồng], theo nguyên tắc Đi-rích-lê, tồn tại 1 lồng
nhốt không ít hơn 2 chú thỏ, tương đương với việc tồn tại hai số có cùng số dư, như vậy có hiệu chia hết cho 10, bài toán được chứng minh
Còn tiếp.....
#2
Nguyễn Hoàng Nam
-
- Thành viên
-
- 334 Bài viết
Độc thân...
- Giới tính:Nam
- Đến từ:Hà Nội
- Sở thích:Kiếng cận và tất cả những gì liên quan đến kiếng cận ^^!
Đã gửi 09-10-2010 - 16:40
Các ví dụ:
A.Các bài toán số học:
1. Toán suy luận:
Ví dụ 1: 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.
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 10 độ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ý Đirichlê phải có ít nhất 2 đội có số trận đấu như nhau.
Ví dụ 2: 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.
GIẢI: Giả sử 6 đội bóng đó là A,B,C,D,E,F. Xét đội A.
Theo nguyên lý Đirichlê 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.
Ví dụ
3: CMR trong n người bất kì, tồn tại hai người có số người quen như nhau [kể cả trường hợp quen 0 người]
GIẢI: Tương tự ví dụ 1, ta xét n nhóm...
Ví dụ 4: 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]
GIẢI: Có 43 học sinh phân chia vào 8 loại điểm [từ 2 đến 9]. Giả sử mỗi loại 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ó không quá 5.8=40 học sinh, ít hơn 43 học sinh. Vậy tồn tại 6 học sinh có điểm kiểm tra bằng nhau.
2.Sự chia hết:
Trong các phép tính trên số nguyên thì phép chia là rất đặc biệt.Phép chia có hàng loạt các tính chất mà các phép còn lại không có. Ví dụ các phép toán cộng , trừ , 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à trong toán học xây dựng hẳn 1 lý thuyết về phép vchia . Những ví dụ sau có liên quan mật thiết giữa phép
chia và nguyên lý Dirchlet
Ví dụ 1: CMR tồn tại một số tự nhiên gồm toàn chữ số 1 chia hết cho 2007.
GIẢI: Xét 2008 số có dạng $1,11,...,11...11$. Theo nguyên tắc Đirichlê thì tồn tại hai số có cùng số dư khi chia cho 2007. Giả sử hai số đó là:
$A={11...1}_{n} và B={11...1}_{k}$ với k