Bài giảng nguyên lí Dirlchlet và các bài Toán

Chia sẻ: A A | Ngày: | Loại File: DOC | Số trang:10

Thêm vào BST

Báo xấu

53
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng nguyên lí Dirlchlet và các bài Toán trình bày giới thiệu về nguyên lý Dirlchlet cùng với cách giải các bài toán theo cấu trúc giáo án qua từng tiết học,... Mời các bạn cùng tham khảo

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng nguyên lí Dirlchlet và các bài Toán

Chuyên đề 9: NGUYÊN LÍ DIRICHLET VÀ CÁC BÀI TOÁN Tiết 1 GIỚI THIỆU NGUYÊN LÍ DIRICHLET A.Nguyên lí Dirichlet Nguyên tắc này mang tên nhà toán học người Đức Peter Gustav Dirichlet (1851 1931) còn gọi là “nguyên tắc lồng chim câu, nguyên tắc thỏ và lồng…”được phát biểu hết sức đơn giản như sau: Nếu nhốt n + 1 con thỏ vào n cái lồng (n N*) thì thế nào cũng có một lồng chứa ít nhất 2 thỏ. Nếu nhốt n con thỏ vào k cái lồng ( với n, k N* , n lớn hơn và không chia hết �n� cho k) thì thế nào cũng có một cái lồng chứa ít nhất � �+1 con thỏ. k� � B.Ví dụ: VD 1:Cho 100 số tự nhiên tuỳ ý. Chứng minh rằng tồn tại 10 số sao cho hiệu hai số bất kỳ đều chia hết cho 11 Giải: Bài toán thực chất là đi chứng minh tồn tại 10 số trong 100 số đã cho có cùng số dư khi chia cho 11. Khi chia cho 11 ta nhận được tất cả 11 số dư: 0, 1,…,10 Ta xét 11 cái lồng: lồng thứ i bao gồm các số chia cho 11 dư i ( 0 i 10 ) .Ta có 100 chú thỏ là 100 số đã cho, nhốt vào 11 cái lồng nói trên. Theo nguyên tắc Dirichlet thì �100 � tồn tại một lồng chứa ít nhất: � �+ 1 = 10 số. Các số này thoả mãn yêu cầu bài ra, �11 � tức là hai số bất kỳ có hiệu chia hết cho 11 (ĐPCM). VD 2: Trong một tam giác đều cạnh 1, ta đặt 17 điểm. Chứng minh rằng, tồn 1 tại hai điểm mà khoảng cách giữa chúng nhỏ hơn . 4
Giải: Chia tam giác đã cho thành 16 tam giác đều nhỏ, cạnh có độ dài (như hình bên) Theo nguyên tắc Dirichlet thì tồn tại ít nhất hai điểm nằm trong cùng một 1 hình tam giác nhỏ. Hai điểm này có khoảng cách bé hơn .(ĐPCM) 4 VD 3: Một bà mẹ chiều con nên ngày nào cũng cho con ăn ít nhất một chiếc kẹo. Để hạn chế, mỗi tuần bà cho con không ăn quá 12 chiếc kẹo. Chứng minh rằng trong một số ngày liên tiếp nào đó bà mẹ đã cho con tổng số 20 chiếc kẹo. Giải: Xét 21 ngày liên tiếp kể từ một ngày thứ hai nào đó. Gọi S(n) là tổng số kẹo mà bà mẹ đã cho con tính đến ngày thứ n ( 1 n 21) Ta có:S(m) S(n), m n ( 1 m, n 21) và 1 S ( n ) 3 12 = 36 Vì có 21 ngày nên tồn tại m >1 ( 1 m, n 21) sao cho S ( m ) �S ( n ) ( mod 20 ) � S ( m ) − S ( n ) M20 � S ( m ) − S ( n ) = 20 (vì 0 ∃ i≠ j:a1 ≡ b1(mod 100).
(Các trường hợp khác không xảy ra). * Cách 2: Nếu có hai số cùng chia hết cho 100. Xét các cặp: (1,99), (2,98), …,(49, 51),(50, 50) Suy ra có hai số mà số dư của chúng khi chia cho 100 cùng rơi vào một cặp suy ra đpcm. Bài 4: Ở vòng chung kết cờ vua có 8 bạn tham gia. Hai bạn bất kỳ đều phải đấu với nhau một trận và người nào cũng phải gặp đủ 7 đấu thủ của mình. Chứng minh rằng trong mọi thời điểm của cuộc đấu, bao giờ cũng có hai đấu thủ đã đấu một số trận như nhau HD: Ta có: 0 ai 7, ∀1 i 8 . Xét các trường hợp: Tính đến thời điểm đó có một bạn chưa đấu trận nào suy ra không có bạn nào đấu đủ 7 trận. Khi đó: 0 �ai �6, ∀1 �i �8 � ∃ak = am (đpcm) Tính đến thời điểm đang xét, mỗi bạn đều đã đấu ít nhất một ván. Khi đó: 0 �ai �7, ∀1 �i �8 � ∃ak = am (đpcm) Bài 5: Chứng minh rằng trong 2001 người bất kỳ, luôn có ít nhất hai người có số người quen bằng nhau (số người quen chỉ tính trong nhóm) HD: Gọi số người quen của Ai là ai 0 ai 2001, ∀1 i 2001 Xét các trường hợp: Có một người không quen ai suy ra không có ai quen cả 2000 người còn lại trong nhóm. Khi đó: 0 �ai �1999, ∀1 �i �2001 � ∃ak = am Mỗi người đều quen ít nhất một người suy ra: 0 �ai �2000, ∀1 �i �2001 � ∃ak = am Tiết 3 BÀI TẬP Bài 1:Trong một hình tròn tâm O bán kính R = 1 ( đơn vị dài). Cho 7 điểm phân biệt, biết rằng: khoảng cách giữa hai điểm bất kỳ trong chúng đều không nhỏ hơn 1. Chứng minh rằng: một trong 7 điểm đó phải trùng với tâm O. Hướng dẫn: Cách 1: Giả sử không có điểm nào trùng vi tâm O. Ta chia hình tròn thành 6 hình quạt bằng nhau. Theo nguyên tắc Dirichlet thì tồn tại một hình quạt bằng chứa ít nhất hai điểm A và B trong số các điểm đã cho. Dễ thấy AB
Hướng dẫn: Chia hình vuông đã cho thành 16 hình vuông nhỏ cạnh 1 bởi các đường thẳng song song với cạnh của hình vuông đó. Vì có 33 điểm nên theo nguyên tắc Dirichlet tồn tại 3 điểm nằm trong cùng một hình vuông nhỏ. Ba điểm này thoả mãn yêu cầu đề bài ra. Bài 3: Cho 6 điểm trong mặt phẳng sao cho 3 điểm bất kỳ trong chúng tạo nên một tam giác có độ dài các cạnh khác nhau. Chứng minh rằng tồn tại một cạnh vừa là cạnh nhỏ nhất của một tam giác vừa là cạnh lớn nhất của một tam giác khác. Hướng dẫn: Trong mỗi tam giác ta tô màu đỏ cạnh nhỏ nhất, các cạnh khác không tô màu. Hãy chứng minh có ít nhất một tam giác có 3 cạnh màu đỏ. Khi đó cạnh lớn nhất của một tam giác khác. Bài 4: Trong một cuộc họp có 6 người. Người ta nhận thấy cứ ba người bất kỳ thì có hai người quen nhau. Chứng minh rằng thế nào cũng có ba ngưới đôi một quen nhau. Hướng dẫn: Các đại biểu tương ứng với 5 điểm A, B, C, D, E, F. Hai đại biểu X và Y nào đó mà quen nhau thì ta tô đoạn thẳng XY bằng màu xanh còn nếu X vá Y không quen nhau thì tô đoạn XY màu đỏ. Xét 5 đoạn thẳng AB, AC, AD, AE, AF: Theo nguyên tắc Dirichlet thì tồn tại ba đoạn cùng màu. Giả sử AB, AC, AD màu xanh. Xét ba điểm B, C, D: vì 3 đại biểu nào cũng có hai người quen nhau suy ra một trong ba đoạn BC, CD, DB màu xanh. Giả sử BC màu xanh A, B, C đôi một quen nhau. Còn nếu AB, AC, AD màu đỏ B, C, D đôi một quen nhau. Bài 5:Cho 2001 điểm trên mặt phẳng. Biết rằng cứ 3 điểm bất kỳ trong số 2001 điểm nói trên bao giờ cũng có hai điểm mà khoảng cách giữa chúng
các nhóm khác . Theo nguyên tắc Dirichlet thì với 4 người bất kỳ luôn có hai người thuộc cùng một nhóm. Hai người này không quen nhau. Bài 2: Cho 5 số nguyên phân biệt a1 , a2 ,..., a5 . Xét tích: P = ( a1 − a2 ) ( a1 − a3 ) ... ( a1 − a5 ) ( a2 − a3 ) ... ( a2 − a5 ) ( a3 − a5 ) ( a3 − a4 ) ( a 3 −a5 ) ( a4 − a5 ) Chứng minh: P M288 Hướng dẫn: Ta có:288 = 32.25 Chứng minh: P M9 Xét 4 số : a1 , a2 , a3 , a4 tồn tại hai số có cùng số dư khi chia cho 3. Giả sử a1 a2 ( mod 3) a1 − a2 M3 (1) Bỏ đi a1 và xét a2 , a3 , a4 , a5 tồn tại hai số có cùng số dư khi chia cho 3. Giả sử a3 a4 ( mod 3) a3 − a4 M3 (2) Từ (1) và (2) P M9. Chứng minh: P M25 . Trong 5 số đã cho có 3 số cùng tính chẵn lẻ. Xét các khả năng có thể: Có 4 số chẵn, giả sử là a1 , a2 , a3 , a4 Đặt a1 = 2b1 ; a2 = 2b2 ; a3 = 2b3 ; a4 = 2b4 ( b1 , b2 , b3 , b4 Z ) Khi đó: P= 32 ( b1 − b2 ) ( b1 − b3 ) ( b1 − b4 ) ( a1 − a5 ) ( b2 − b3 ) ( b2 − b4 ) ( a2 − a5 ) ( a3 − a4 ) ( a3 − a5 ) ( a4 − a5 ) chia hết cho 32. Có 3 số chẵn a1 , a2 , a3 còn a4, a5 lẻ: Đặt a1 = 2b1 ; a2 = 2b2 ; a3 = 2b3 ; a4 = 2b4 +1, a5 = 2b5 + 1 Khi đó: P = 16 ( b1 − b2 ) ( b1 − b3 ) ( b2 − b3 ) Q Trong 3 số b1, b2, b3 có hai số cùng tính chẵn lẻ Giả sử b1 �b2 ( mod 2 ) � b1 − b2 M2 � P M32 Có 3 số chẵn a1 , a2 , a3 còn a4, a5 chẵn : Đặt a1 = 2b1 + 1, a2 = 2b2 + 1, a3 = 2b3 + 1, a4 = 2b4 , a5 = 2b5 Xét tương tự các trường hợp trên. Bài 3:Chứng minh rằng trong 12 số nguyên tố phân biệt luôn chọn được 6 số, gọi là a1 , a2 ,..., a6 sao cho tích: P = ( a1 − a2 ) ( a3 − a4 ) ( a5 + a6 ) chia hết cho 1800. Hướng dẫn: Trong 12 số đã cho có ít nhất 9 số lớn hơn 5. Giả sử 9 số này là b 1, b2, …,b9. Mỗi số trong 9 số này khi chia cho 3 chỉ cho số dư là 1 hoặc 2. Theo nguyên tắc Dirichlet thì tồn tại 5 số có cùng sồ dư khi chia cho 3, giả sử các số này làø b1 , b2 , b3 , b4 , b5 .
Mỗi số trong 5 số b1 , b2 , b3 , b4 , b5 khi chia cho 5 chỉ cho số dư là 1, 2, 3, 4. Theo nguyên tắc Dirichlet thì tồn tại hai số có cùng số dư khi chia cho 5, giả sử hai số này là b1, b2. Bây giờ, xét các số b1 , b2 , b3 , b4 , b5 Nếu có hai số nào đó có cùng số dư khi chia cho 5, chẳng hạn b3 và b4 thì chọn a1 = b1, a2 = b2, a3 = b3, a4 = b4, a5 = b5, và a6 = b6. Khi đó: a1 − a2 M3, a3 − a4 M3 P M9 a1 − a2 M5, a3 − a4 M5 P M25 a1 − a2 M2, a3 − a4 M2, a5 + a6 P M8 Vậy P chia hết cho 8.9.25 = 1800 Nếu không có hai số nào trong 4 số b1 , b2 , b3 , b4 , b5 có cùng số dư khi chia cho 5 dư 1 và một số chia cho 5 dư 4, giả sử b 5 1 (mod 5) vàb6 4 (mod 5). Khi đó a1 = b1, a2 = b2, a3 = b3, a4 = b4, a5 = b5, và a6 = b6. Ta có: a1 − a2 M3, a3 − a4 M3 P M9 , a1 − a2 M5, a3 − a4 M5 P M25 , a1 − a2 M2, a3 − a4 M2, a5 + a6 P M8 . Vậy trong trường hợp này ta cũng có P chia hết cho 1800. Bài 4:Cho 40 số nguyên dương a1 , a2 ,..., a19 và b1 , b2 ,..., b21 thoả mãn: 1 a1 < a2 < ... < a19 200 1 b1 < b2 < ... < b21 200 Chứng minh rằng tồn tại 4 số ai, aj, bk, bp ( 1 19,1 k, p 21) sao cho: ai < a j bk < bp a j − ai = bp − bk Hướng dẫn: Xét các tổng có dạng: ai +bj. Có tất cả 19x21 =399 tổng như thế. Các tổng này nhận giá trị từ 2 đến 400. Các tổng trên nhận đủ 399 giá trị từ 2 đến 400 � a1 = b1 = 1, a19 = b21 = 200 � đpcm Các tổng trên không nhận đủ 399 giá trị từ 2 đến 400 có hai tổng bằng nhau đpcm. Tiết 5 BÀI TẬP Bài 1:Tại một cuộc họp, một nhà Toán học tuyên bố : “ Số các nhà Toán học tham gia tại đây là một số có hai chữ số, số náy bé hơn hai lần tích 2 chữ số của nó 9 đơn vị”. Hỏi có bao nhiêu nhà Toán học tham dự cuộc họp? Hướng dẫn: Gọi số đã cho là xy , ta có: 10 x + 9 10x + y + 9 = 2xy y= 2x −1
Với x = 4, ta suy ra y = 7. Các khả năng khác của x đều không cho ta giá trị y chấp nhận được . Vậy có 47 nhà Toán học tham dự. Bài 2:A và B tiến hành một trò chơi với 2001 hạt đậu. A đi nước và luân phiên nhau. Một nước đi là một lần lấy khỏi đốn hạt đậu đi 1, 2 hay 3 hạt. Người nào đi nước cuối (hết đậu trong đống), ngưới ấy thắng. Vậy người nào có chiến thuật để chiến thắng và chiến thuật đó ra sao? Hướng dẫn: A luôn chiến thắng nếu A tiến hành như sau : Nước đi đầu tiên, A lấy 1 hạt , nước tiếp theo A sẽ lấy đi 4x hạt, với x là số hạt B lấy ở nước đi trước đó. Thật vậy, sau khi A đi đầu tiên, còn lại 2000 hạt đậu. Tiếp theo, cứ sau mỗi lần B rồi A đi, đống đậu luôn còn lạisố hạt bằng một bội số của 4. Do vậy, cuối cùng sẽ còn lại 4 hạt. Bấy giờ đến B đi và A đi nước cuối thì sẽ còn 0 hạt: A thắng. Bài 3: Trong một thời gian nọ của một lớp học Toán có một nhóm gồm 5 học sinh mà cứ mỗi người trong nhóm này thì rơi vào trong trạng thái ngủ gục trong lớp đúng 2 lần. Với mỗi cặp học sinh, đều có cả hai cùng ngủ gục một lần. Chứng minh rằng, tại một thời điểm nào đó có 3 học sinh tronh nhóm đó đồng thời ngủ gục . Hướng dẫn: Giả sử ngược lại, rằng không hề có chuyện 3 học sinh đồng thời ngủ gục. Ta sẽ chứng minh điều này mâu thuẩn. Thật vậy, trong khoảng thời gian có hai người đồng thời ngủ gục, 3 người còn lại tỉnh táo. Theo đề bài, mỗi học sinh trong nhóm đều ngủ gục đúng hai lần nên một trong hai người(đang ngủ gục) sẽ có lúc lại ngủ gục với một trong 3 người còn lại. Như vậy, nhiều nhất sẽ có tất cả là 9 khoảng thời gian diễn ra ngủ gục từng cặp. Nhưng nhóm này có 5 học sinh, số cặp là C52 = 10 , mà chỉ có nhiều lắm là 9 khoảng thời gian. Do vậy sẽ có ít nhất một cặp không đồng thời ngủ gục. Ta có điều mâu thuẫn. Bài 4: Có 5 người đấu cờ với nhau. Hãy xác định kết quả của tất cả các trận đấu nếu biết rằng mỗi người chơi một lần với 4 người kia và số điểm của mỗi người nhận được đều khác nhau. Ngoài ra: a) Người xếp thứ nhất không hoà trận nào. b) Người xếp thứ nhì không thua trận nào. c) Người xếp thứ tư không thắng trận nào. Hướng dẫn: Theo điều kiện của bài ra ta thấy ngay người xếp thứ nhất thắng người xếp thứ ba, thứ tư, thứ năm và được tất cả 3 điễm. Còn người thứ nhì thắng người xếp thứ nhất. Người thứ nhì hoà trong các trận đấu với người xếp thứ ba, thứ tư, thứ năm và nhận 2,5 điểm. Những người còn lại chỉ nhận số điểm lớn nhất lần lượt là 2; 1; 5; 1. Ta chứng minh họ không thể nhận ít hơn. Thật vậy, vì có 5 người nên họ chơi tất cả 10 trận và nhận tất cả 10 điểm. Nhưng người xếp thứ nhất và thứ nhì đã nhận 5,5 điểm nên ba
người còn lại nhận 4,5 điểm. Mặt khác: 2 + 1,5 +1 = 4,5 nên họ không thể nhận ít hơn. Như vậy, do người thứ tư không thắng trận nào nên anh ta hoàvới người xếp thứ ba và thứ năm. Còn lại người thứ ba thắng người thứ năm. Tiết 6 BÀI TẬP Bài 1:Trong một cuộc tranh giải vô địch quốc gia về bóng đá có 20 đội tham gia. Số nhỏ nhất các trận đấu là bao nhiêu để trong 3 đội bất kỳ luôn tìm được 2 đội đã chơi với nhau? Hướng dẫn: Ta chia 20 đội thành 2 nhóm, mỗi nhóm 10 đội và chỉ các đội trong cùng1 nhóm mới thi đấu với nhau. Rõ ràng cách sắp xếp này thoả mãn các điều kiện của bài toán và tất cả có 90 trận đấu. Ta chứng minh rằng nếu các điều kiện của bài toán thoả mãn thì số trận đấu sẽ 90. Giả sử ngược lại, ta tìm đôi một A đấu số trận k 8. Ta ký hiệu các đội đã đấu với A là X. Các đội không đấu với A là Y: X= k, Y = 19 –k. Dĩ nhiên các đội trong Y sẽ đấu với nhau nếu không hai đội thuộc Y và A sẽ là 3 đội mà không có đội nào chơi với nhau. Giả sử trong X có P cặp không chơi với nhau. Do đó mỗi đội Y phải đấu với mỗi đội trong P cặp đó của X và mỗi đội trong X có mặt không quá (k 1) cặp trong số P cặp (X có tất cả k đội). Vì vậy giữa các đội của X và Y đấu số trận bé hơn 19 − k hoặc bằng = . k −1 19 − k Mặt khác: do k 8 nên .P P. Như vậy: nếu thay các trận của các đội k −1 trong X đấu với các đội trong Y bởi các trận đấu cần thiết sẽ giảm đi. Như vậy số trận đấu cần phải tiến hành là: k ( k − 1) ( 19 − k ) ( 18 − k ) = k 2 − 18k + 9.19 = ( k − 9 ) + 90 90 2 + 2 2 Vậy số các trận đấu ít nhất cần phải tiến hành là 90 Bài 2:Các học sinh được phát bài kiểm tra, mỗi môn một bài, trong n (n 3) môn học. Biết rằng với một môn học bất kỳ có đúng 3 học sinh đạt điểm tối ưu, còn với hai môn tuỳ ý thì có đúng 1 học sinh đạt điểm tối ưu cho mỗi môn trong cả hai môn đó. Hãy xác định số n bé nhất sao cho từ các điều kiện trên có thể suy ra rằng có đúng 1 học sinh đạt điểm tối ưu cho mỗi môn trong cả n môn học. Hướng dẫn: Giá trị nhỏ nhất của n là 8. Ta biểu thị mỗi học sinh bằng một điểm trong mặt phẳng sao cho không có ba điểm nào thẳng hàng. Nếu hai học sinh đạt điểm tối ưu ở một môn nào đó, ta nối hai điểm tương ứng lại với nhau. Khi đó, theo đề bài, mỗi môn học sẽ cho tương ứng duy nhất một tam giác vàbất cứ hai tam giác nào cũng có đúng một đỉnh chung. Chú ý rằng nếu như bốn tam giác có chung một đỉnh thì tất cả các tam giác đều có chung đỉnh đó, bởi vì nếu không thì tam giác thứ năm sẽ có chung đỉnh với mỗi một
trong bốn tam giác đó. Như vậy tam giác thứ năm này sẽ có bốm đỉnh, điều này mâu thuẩn. Bây giờ, nếu n 8 thì một tam giác sẽ có chung một đỉnh với mỗi một trong 7 tam giác còn lại. Theo nguyên lí Dirichlet , một trong các đỉnh của nó sẽ có chung đỉnh với ít nhất ba tam giác khác, tức là tồn tại 4 tam giác có chung một đỉnh. Cuối cùng ví dụ sau đây chứng tỏ rằng trường hợp n = 7 không thỏa mãn đề bài (do vậy n n) mỗi sợi dây cáp chỉ nối được một máy tính và một máy in. Tại một thời điểm bất kỳ mỗi máy tính chỉ có thể điều khiển được một máy in và người lại mỗi máy in chỉ in được cho một máy tính. Hỏi phải dùng ít nhất là bao nhiêu sợi dây cáp để n máy tính bất kỳ có thể đồng thời in được ? Hướng dẫn: Ta xét một cách nối thoả mãn đề bài như sau: Với n máy tính đầu tiên mỗi máy nối với một máy in; với (mn) máy tính còn lại, mỗi máy nối với tất cả n máy in. Số dây cáp cần dùng trong cách nối này là: S = n + n(m–n) = n (mn +1). Ta sẽ chứng minh rằng nếu số dây cáp S
Một dự đoán khác cho rằng thứ tự xếp hạng là D, A, E, C, B . Kết quả sau khi thi, có đúng 2 học sinh đã đạt vị trí dự đoán và cũng đã có được hai cặp học sinh khác nhau xếp thứ tự kề nhau như đã dự đoán . Hãy xác định kết quả xếp hạng của 5 học sinh đó. Hướng dẫn: Ta bắt đầu tự dự đoán thứ hai. Theo dự đoán này, các cặp học sinh khác nhau chỉ có thể là DA và EC, DC và CB hay AE và CB. Cũng theo dự đoán đó, có đúng hai học sinh đã đạt vị trí như dự đùoán. Do vậy, thứ tự xếp hạng là một trong những khả năng sau: DABEC (1) DACBE (2) EDACB (3) AEDCB (4) Đến đây , ta xét kết hợp với dự đoán ban đầu. Kết quả (1) không thể xảy ra vì AB rơi đúng vị trí liên tiếp như dự đoán ban đầu . Kết quả (2) cũng không xảy ra bởi C xếp đúng vị trí như dự đoán ban đầu. Cũng vậy kết quả (4) không xảy ra vì nếu thế thì A lại xếp đúng vị trí của dự đoán ban đầu. Tóm lại: E, D, A, C, B xếp theo thứ tự tương ứng từ 1 đến 5, đó là kết quả sau kỳ thi. Hết