Những Nguyên Lí Cơ Bản Trong Các Bài Toán đếm - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.pdf) (19 trang)

Trang chủ

Luận Văn - Báo Cáo

Kinh tế - Quản lý

những nguyên lí cơ bản trong các bài toán đếm

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 (744.7 KB, 19 trang )

NHỮNG NGUYÊN LÍ CƠ BẢNTRONG CÁC BÀI TOÁN ĐẾMMôn học: Đại số sơ cấpKhoa Toán-TinGiảng Viên: TS. Tạ Thị Nguyệt NgaLời nói đầu:Lí thuyết tổ hợp là một phần quan trọng của toán học rời rạc chuyên nghiên cứu sựphân bố các phần tử vào các tập hợp. Thông thường các phần tử này là hữu hạn vàviệc phân bố chúng phải thoả mãn những điều kiện nhất định nào đó, tùy theo yêucầu của bài toán cần nghiên cứu.Mỗi cách phân bố như vậy gọi là một cấu hình tổ hợp. Chủ đề này đã được nghiêncứu từ thế kỉ 17, khi những vấn đề về tổ hợp được nêu ra trong những công trìnhnghiên cứu các trò chơi may rủi. Liệt kê, đếm các đối tượng có những tính chất nàođó là một phần quan trọng của lí thuyết tổ hợp. Đếm các đối tượng để giải nhiềubài toán khác nhau.Lý thuyết tổ hợp được áp dụng trong nhiều lĩnh vực khác nhau: lý thuyết số, hìnhhọc hữu hạn, biểu diễn nhóm, đại số không giao hoán, thống kê xác xuất, … Lýthuyết tổ hợp gắn liền với việc nghiên cứu sự phân bố các phần tử vào các tập hợp.Các phần tử là hữu hạn và việc phân bố chúng phải thỏa mãn những điều kiện nàođó tùy theo yêu cầu của công việc (bài toán).Dù đã rất cố gắng nhưng nội dung được trình bày ở luận văn này chắc chắn sẽ cósai sót nhất định, nhóm rất mong sự đóng góp ý kiến từ cô và các bạn.TP HCM 10 tháng 5 năm 2018Tạ Quốc KhánhĐỗ Đức ChungNhắc lại lý thuyết tập hợp:Trước tiên, ta có khái niệm về phần tử của tập hợp hữu hạn:Một tập hợp A được gọi là tập hợp hữu hạn nếu A có hữu hạn phần tử. Nếu A có nphần tử, ta kí hiệu số phần tử của A bởi | |(n nguyên dương)Ta có thể tìm phần tử của tập hợp hữu hạn bằng 2 cách đơn giản nhất:-Liệt kê các phần tử của tập hợp.- Chỉ rõ các tính chất đặc trưng cho các phần tử của tập hợp.Ngoài ra ta có các phép toán trên tập hợp:- Giao của 2 tập hợp A và B kí hiệu là AB: AB = {x | xA và x- Hợp của 2 tập hợp A và B kí hiệu là AB: AB = {x | xA hoặc x- Hiệu của 2 tập hợp A và B kí hiệu là A\B: A\B = {x | xA và x- Phần bù của A trong X kí hiệu là :A}= {x |xX và xB}B}B}- Tích đề các của 2 tập hợp A và B kí hiệu A x B hoặc A.B – A x B = {(a, b)| avà b B}A1/ Quy tắc đếm:* Định nghĩa:Trong nhiều trường hợp ta cần phải đếm số phần tử, số tập hợp,số các số hạng củatổng.Ví dụ 1: Người ta cần làm một hàng rào dài 20m, cứ cách 2m thì chôn 1 cọc. Tínhsố cọc cần dùng?Dễ dàng tìm được số khoảng cách giữa các cọc là: 20:2 = 10.Kể từ cọc thứ 2 trở đi số cọc bằng số khoảng cách.Do đó số cọc là 20:2 + 1 = 11.Ngoài ra trong một số bài toàn ta chỉ có thể áp dụng quy tắc đếm để giải.-Dấu hiệu chia hết cho 2: Chữ số tận cùng là các chữ số: 0;2;4;6;8.-Dấu hiệu chia hết cho 3: Tổng các chữ số chia hết cho 3.-Dấu hiệu chia hết cho 4: 2 chữ số tận cùng tạo thành số chia hết cho 4.-Dấu hiệu chia hết cho 5: Chữ số tận cùng là các chữ số: 0; 5.-Dấu hiệu chia hết cho 6: Vừa chia hết cho 2 và đồng thời vừa chia hết cho 3.-Dấu hiệu chia hết cho 7: Hiệu của số tạo bởi các chữ số đứng trước số tận cùng.với 2 lần chữ số tận cùng chia hết cho 7 (có thể làm nhiều lần cho tới khi chắc chắnchia hêt cho 7).-Dấu hiệu chia hết cho 8: 3 chữ số tận cùng tạo thành số chia hết cho 8.-Dấu hiệu chia hết cho 9: Tổng các chữ số chia hết cho 9.Ví dụ 2:- 12 có 1+2=3 chia hết cho 3 nên 12 chia hết cho 3.- 123 có 1+2+3=6 chia hết cho 3 nên 123 chia hết cho 3.- 136 chia hết cho 4 vì 36 là 2 chữ số tận cùng chia hết cho 4.- 342 chia hết cho 9 vì 3+4+2=9 chia hết cho 9.- 67182 chia hết cho 6 vì tận cùng là 2 và có 6+7+1+8+2=24 chia hết cho 3.2/Quy tắc cộng:* Định nghĩa:Giả sử có k công việccác việc này có thể được thực hiện tươngứng bằng ,cách, và giả sử không có 2 việc nào có thể thực hiệnđồng thời khi đó áp dụng nguyên tắc cộng ta có l +.+ Quy tắc cộng có thế phát biểu dưới dạng tập hợp như sau:Nếulà các tập hợp đôi một rời nhau khi đó số phần tử của hợp cáctập này bằng tổng các phần tử của các tập hợp, và giả sử không có 2 việc nào cóthể thực hiện đồng thời khi đó ta có:||=||||||||Ví dụ 1: Một sinh viên có thể chọn 1 bài thực hành trong ba danh sách tương ứngcó 23, 15 và 19 bài. Vì vậy theo quy tắc cộng sinh viên có 23 + 15 + 19 = 57 cáchchọn bài thực hành.Ví dụ 2: Người ta có thể đi từ Hải Phòng đến Đà Nẵng bằng một trong ba phươngtiện: tàu hoả, tàu thuỷ và máy bay. Nếu có hai cách đi bằng tàu hoả, ba cách đibằng tàu thuỷ, và 1 cách đi bằng máy bay thì sẽ có 2+3+1 = 6 cách đi từ Hải Phòngđến Đà Nẵng.2/Quy tắc nhân:* Định nghĩa:Giả sử ta có 1 công việc được tách ra thành k công việc trong đó mỗi công việctrong k công việc có n cách thực hiệntương ứng có,thì khi đó áp dụng nguyên tắc nhân ta có .cách làmk công việc đó.+Quy tắc nhân có thế phát biểu dưới dạng tập hợp như sau:Nếulà các phần tử hữu hạn khi đó số phần tử của tích Descastescủa các tập hợp này bằng tích của số các phần tử của mọi tập thành phần.Ta biếtrằng việc chọn một phần tử từ tích Descastesđược tiến hành bằng̅̅̅̅̅.chọn lần lượt các phần tử||||||||||Ví dụ 1: Đề đi từ thành phố A đến thành phố D người ta phải đi lần lượt qua haithành phố B và C. Nếu có hai cách đi từ A đến B, ba cách đi từ B đến C và mộtcách đi từ C đến D thì sẽ có 2x3x1 = 6 cách đi từ A đến B.Ví dụ 2: Có bao nhiêu số tự nhiên có ba chữ số được lấy từ tập 1,2,3,4,5,6 nếua)Các chữ số không cần phải khác nhau?b)Các chữ số phải khác nhau?c)Các chữ số phải khác nhau và chứa số 3?Đáp số:a) 6x6x6; b) 6x5x4; c)3x5x4Ví dụ 3: Một đội thanh viên tình nguyện có 15 người gồm 12 nam, 3 nữ . Hỏi cóbao nhiêu cách phân công đội thanh niên đó về giúp đỡ 3 tỉnh miền núi, sao chomỗi tỉnh có 4 nam và 1 nữ?GiảiĐầu tiên, chọn 4 nam và 1 nữ cho tỉnh thứ nhất. Theo quy tắc nhân số cách chọnlà:Sau đó chọn 4 nam (trong 8 nam còn lại) và 1 nữ (trong 2 nữ còn lại) cho tỉnh thứ2. Lại theo quy tắc nhân, số cách chọn là:Dĩ nhiên còn lại ta chọn xong tỉnh thứ 3Vậy theo quy tắc nhân, số cách phân công theo yêu cầu là:Ví dụ 4: Người ta có thể ghi nhãn cho những chiếc ghế trong một giảng đườngbằng một chữ cái và một số nguyên dương không vượt quá 100. Bằng cách nhưvậy, nhiều nhất có bao nhiêu chiếc ghế có thể được ghi nhãn khác nhau? Thủ tụcghi nhãn cho một chiếc ghế gồm hai việc, gán một trong 26 chữ cái và sau đó gánmột trong 100 số nguyên dương. Quy tắc nhân chỉ ra rằng có 26x100=2600 cáchkhác nhau để gán nhãn cho một chiếc ghế. Như vậy nhiều nhất ta có thể gán nhãncho 2600 chiếc ghế.Ví dụ 5: Một đội thanh niên tình nguyện có 15 người gồm 12 nam và 3 nữ. Hỏi cóbao nhiêu cách phân công đội về giúp đỡ 3 tỉnh miền núi sao cho mỗi tỉnh có 4nam và 1 nữ.Giải.Gọi 3 tỉnh có tên là A, B, CChọn đội thanh niên tình nguyện phục vụ tỉnh A có C124 .C13Chọn đội thanh niên tình nguyện phục vụ tỉnh A có C84 .C12Chọn đội thanh niên tình nguyện phục vụ tỉnh A có C44 .C11Theo quy tắc nhân ta có: C124 .C13 . C84 .C12 C44 .C11 = 2079003. Hoán vị* Định nghĩa:Cho tập hợp A gồm n phần tử, mỗi kết quả của sự sắp xếp thứ tự n phần tử củatậphợp A được gọi là một hoán vị của n phần tử đó.* Số hoán vị.Số hoán vị của n phần tử, được ký hiệu là PnPn = n!Ví dụ 1: Có bao nhiêu cách sắp xếp 4 học sinh vào 4 chỗ ngồi trong một bàn họcsinh.GiảiSố cách sắp xếp 4 học sinh vào 4 chỗ ngồi bằng số hoán vị của 4 phần tửVậy P4 = 4! = 1.2.3.4 = 24 cách sắp xếp.Ví dụ 2: Cho 5 quả cầu màu trắng khác nhau và 4 quả cầu xanh khác nhau. Ta sắpxếp 9 quả cầu đó vào một hàng 9 chỗ cho trước. Có bao nhiêu cách sắp xếp khácnhau?GiảiCó 9! = 362880 cách4. Chỉnh hợp.* Định nghĩa:Cho tập hợp A gồm n phần tử (n  1)Kết quả của việc lấy k phần tử khác nhau từ n phần tử của tập hợp A và sắpxếp chúng theo một thứ tự nào đó được gọi là một chỉnh hợp chập k của n phần tửđã cho.* Số chỉnh hợp.Số chỉnh hợp chập k của n phần tử được ký hiệu là A knA kn =n!(1  k  n)n  k !+ Chỉnh hợp chập n của n phần tử chính là một hoán vị của n phần tử.A nn  PnVí dụ 1: Từ các chữ số 1; 2; 3; 4; 5; 6; 8. Hỏi có thể lập được bao nhiêu số có 3chữ số khác nhau.GiảiCó A 37 = 5.6.7 = 210 số có 3 chữ sốkhác nhau.Ví dụ 2: với các chữ số 0, 1, 2, 3, 4, 5 có thể lập được bao nhiêu:a. Số lẻ gồm 4 chữ số khác nhau.b. Số chẵn gồm 4 chữ số khác nhau:GiảiGọi số có 4 chữ số là abcda. Số cần lập là số lẻ nên:Có 3 cách chọn số d.Có 4 cách chọn số a.Có A 24 cách chọn số bcVậy có: 3. 4 . A 24 = 144 số.b. Số cần lập là số chẵn:Trường hợp 1: d = 0 Số cách lập được số có 4 chữ số với d = 0 là A 35Trường hợp d  0Có 2 cách chọn số d.Có 4 cách chọn số aCó A 24 cách chọn bc có 2.4. A 24 = 96 số.Vậy có A 35 + 96 = 156 số.5. Tổ hợp.* Định nghĩa:Giả sử tập A có n phần tử (n  1). Mỗi tập con gồm k phần tử của A được gọilà một tổ hợp chập k của n phần tử đã cho* Số các tổ hợp.Số các tổ hợp chập k của n phần tử, ký hiệu là CknCkn =n!k!n  k !Ví dụ 1: Hãy tính tổ hợp C36GiảiTa có: C 36 6! 4.5.6 203!3! 1.2.3Ví dụ 2: Một cỗ bài túlơkhơ có 52 quân bài, chia cỗ bài trên thành 4 phần bằngnhau (mỗi phần 13 quân). Hỏi có bao nhiêu cách chia được 1 phần sao cho:a. có 2 con át.b. có ít nhất một con át.Giảia. Số cách chọn 2 con át từ 4 con át là: C 24Số cách chọn 11 con bài còn lại trong 48 con bài là: C1148Theo quy tắc nhân ta có: C 24 . C1148 cách chia.b. Số cách chia được phần có 13 con bài là C1352Số cách chia được 1 phần mà không có con át nào cả là: C1348Vậy số cách chia được 1 phần có ít nhất 1 con át là C1352 - C1348* Tính chất của tổ hợp:+ Tính chất 1: C kn  C nn  k+ Tính chất 2: C kn 11  C kn 1  C kn6. Nguyên lí bù trừ:* Định nghĩa:Khi 2 công việc có thể cùng được làm đồng thời, ta không thể dung quy tắc cộngđể tính số cách thực hiện gồm cả 2 việc. Để tính đúng số cách thực hiện nhiệm vụnày ta cộng số cách làm mỗi một trong 2 việc rồi trừ đi số cách làm đồng thời cảhai việc. Ta có thế phát biểu nguyên lí này bằng ngôn ngữ tập hợp:||||||||Ví dụ 1: Cho 3 tập hợp A, B, C. biết: A = {0,1,2,7,11,14,25}, B = {-5,4,0,2,7,13,15,16,19}, C = {-5,-2,2,7,13,14,16,20,21}. Tính N(A B C) = ?Giải:Ta có N(A) = 7; N(B)=9; N(C)=9;N1=7+9+9 =25N2=N(A B)+N(A C)+N(B C) = 3 + 3+5=11N3 = N(A B C) = 2Theo nguyên lí bù trừ ta có: N(ABC)=N1-N2+N3 = 25-11+2=16Ví dụ 2: Trong 1 đề thi chọn đội tuyển toán quốc gia có 3 câu: 1 câu về số học, 1câu về đại số và 1 câu về hình học. Trong 40 thí sinh dự thi có 25 thí sinh làm đượccâu số học, 30 thí sinh làm được câu đại số và 15 thí sinh làm được câu hình học.Ngoài ra, số thí sinh làm được cả 2 câu số học và đại số là 20, số thí sinh làm đượccả 2 câu số học và hình học là 5, số thí sinh làm được cả 2 câu đại số và hình học là10. Biết rằng không có thí sinh nào không làm được câu nào. Hỏi có bao nhiêu thísinh làm được cả 3 câu?GiảiGọi A, B, C tương ứng là tập hợp các thí sinh làm được câu số học, đại số và hìnhhọc. Theo giả thuyết ta có:| || || |||||||Vì không có thí sinh không làm được câu nào nên||Áp dụng nguyên lí bù trừ ta có||| || || |||Suy ra 40 = 25 + 30 + 15 – 20 - 10 – 5 + ||||||||Vậy có 5 học sinh làm được cả 3 câu.7. Ứng dụng của phép đếm nâng cao+Phương pháp song ánh: Phương pháp song ánh dựa vào một ý tưởng rất đơn giản:Nếu tồn tại một song ánh từ A vào B thì |A| = |B|. Do đó, muốn chứng minh hai tậphợp có cùng số phần tử, chỉ cần xây dựng một song ánh giữa chúng. Hơn nữa, ta cóthể đếm được số phần tử của một tập hợp A bằng cách xây dựng song ánh từ A vàomột tập hợp B mà ta đã biết cách đếm.+Phương pháp quan hệ đệ quy: Phương pháp quan hệ đệ quy là phương pháp giảibài toán với n đối tượng thông qua việc giải bài toán tương tự với số đối tượng íthơn bằng cách xây dựng các quan hệ nào đó, gọi là quan hệ đệ quy. Sử dụng quanhệ này, ta có thể tính được đại lượng cần tìm nếu chú ý rằng với n nhỏ, bài toánluôn có thể giải một cách dễ dàng.Bài tập1. Một cuộc họp gồm 12 người tham dự để bàn về 3 vấn đề. Có 8 người phát biểuvề vấn đề I, 5 người phát biểu về vấn đề II và 7 người phát biểu về vấn đề III.Ngoài ra, có đúng 1 người không phát biểu vấn đề nào. Hỏi nhiều nhất là có baonhiêu người phát biểu cả 3 vấn đề.2. Có 17 nhà bác học viết thư cho nhau trao đổi 3 vấn đề. Chứng minh rằng luôntìm được 3 người cùng trao đổi một vấn đề.3. Trong kỳ thi kết thúc học phần toán học rời rạc có 10 câu hỏi. Có bao nhiêu cáchgán điểm cho các câu hỏi nếu tổng số điểm bằng 100 và mỗi câu ít nhất được 5điểm.4. Phương trình x1 + x2 + x3 + x4 + x5 = 21 có bao nhiêu nghiệm nguyên khôngâm?5. Có bao nhiêu xâu khác nhau có thể lập được từ các chữ cái trong từMISSISSIPI, yêu cầu phải dùng tất cả các chữ?6. Lớp Toán- Tin có 40 sinh viên cần bầu một lớp trưởng, một lớp phó và một bankiểm phiếu 3 người không có trưởng ban. Hỏi có bao nhiêu cách chọn 5 người này.7. Trong kì thi sinh viên phải trả lời ngẫu nhiên 20 câu hỏi trong bộ đề gồm 100câu hỏi dạng đúng hoặc sai. Hỏi có bao nhiêu đáp án8. Có 12 chiếc kẹo cần chia ra một số gói, mỗi gói có chẵn số kẹo hỏi có bao nhiêucách chia.9. Một hình tròn có bán kính 5cm. Bên trong đó có 10 điểm bất kì. Chứng minhrằng luôn tồn tại ít nhất 2 điểm có khoảng cách nhỏ hơn 4cm.10. Tính tổng tất cả các số là hoán vị của số 12345 .11. Có 5 tem thư khác nhau và 6 bì thư cũng khác nhau. Người ta muốn chọn ra từđó 3 tem thư và 3 bì thư, mỗi bì thư dán 1 tem. Có bao nhiêu cách như vậy?12. Có bao nhiêu số có 6 chữ số khác nhau mà có mặt của chữ số 0 và chữ số 9.13. Từ các chữ số 0, 1, 2, 3, 4 lập được bao nhiêu số tự nhiên có 7 chữ số, trong đósố 1 có mặt đúng 3 lần và các số khác có mặt đúng 1 lần.14. Có thể thành lập bao nhiêu số có 8 chữ số, trong đó chữ số 1 và chữ số 6 đều cómặt 2 lần, các chữ số 2, 3, 4, 5 đều cómặt đúng 1 lần.15. Có bao nhiêu số tự nhiên có 7 chữ số, trong đó chữ số 2 có mặt đúng 2 lần, chữsố 3 có mặt đúng 3 lần, các chữ số còn lại có mặt không quá 1 lần.8. Tài liệu tham khảo:[1] Nguyễn Minh Tuấn, Chuyên đề đại số tổ hợp, lưu hành nội bộ tháng 8 năm2013.[2] Trần Nam Dũng, Chuyên đề phép đếm_ Các nguyên lí cơ bản của phép đếmNGUYÊN LÍ DIRICHLET VÀ ỨNG DỤNG1.Vài nét về phương pháp Dirichlet:Dirichlet(1805-1859)- Nguyên lý Dirichlet do nhà toán học người Đức nổi tiếng 1là Dirichlet đề xuất từthế kỷ XX đã được áp dụng để chứng minh sự tồn tại nghiệm trong nhiều bài toántổ hợp. Nguyên lý này được phát triển từ một mệnh đề rất đơn giản gọi là nguyênlý “nguyên lý quả cam” hay là nguyên lý “chuồng chim bồ câu”: Giả sử có mộtđàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì chắcchắn có ít nhất một ngăn có nhiều hơn một con chim.-Phương pháp sử dụng nguyên lý Dirichlet là phương pháp mà học sinh được làmquen sớm nhất ngay từ khi học ở bậc tiểu học. Đây là một trong những phươngpháp thể hiện rõ cái đẹp của toán học, làm cho học sinh thêm yêu thích môn toán.Chính vì vậy mà trong các kỳ thi học sinh giỏi các cấp, các bậc: Tiểu học, THCS,THPT… thường xuyên có mặt các bài toán phải sử dụng phương pháp này.2.Khái niệm nguyên lí Dirichlet:-Nguyên lý: “Nếu nhốt hết 5 con thỏ vào 4 cái chuồng thì luôn có ít nhất là hai conthỏ bị nhốt trong cùng một chuồng”.+ Nguyên lí Dirichlet cơ bản: Nếu xếp nhiều hơn n+1 đối tượng vào n cái hộp thìtồn tại ít nhất một hộp chứa không ít hơn hai đối tượng.Ta chứng minh bằng phản chứng: Giả sử không hộp nào chứa nhiều hơn một đốitượng thì chỉ có nhiều nhất là n đối tượng được xếp trong các hộp, trái với giả thiếtlà số đối tượng lớn hơn n.+ Nguyên lí Dirichlet 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*+ con thỏ, ở đây kí hiệu [α] để chỉ phần nguyên của số α.Ta chứng minh nguyên lí Dirichlet mở rộng như sau : Giả sử trái lại mọi chuồngthỏ không có đến *+ *+ * +con, thì số thỏ trong mỗichuồng đều nhỏ hơn hoặc bằng *hoặc bằng m. *chứng là sai.++ con. Từ đó suy ra tổng số con thỏ nhỏ hơncon. Điều này vô lí vì có n con thỏ. Vậy giả thiết phảnDựa vào 2 nguyên lí Dirichlet cơ bản và mở rộng ta có thể phân chia các đối tượngthành các nhóm khác nhau khi không cần quan tâm đến tính chất của đối tượng màchỉ cần quan tâm đến số “vật” và “ngăn”.3.Ứng dụng của nguyên lí Dirichlet trong các dạng toán cơ bản.Bài 1: Một trường học có 1000 học sinh gồm 23 lớp. Chứng minh rằng phải có ítnhất một lớp có từ 44 học sinh trở lên.iải:Giả sử 23 lớp mỗi lớp có không quá 43 học sinh.hi đó số học sinh là:43.23=989 học sinh(vô lý).Theo nguyên lí Dirichlet phải có ít nhất một lớp có từ 44 học sinh trở lên.Bài 2: Một lớp có 50 học sinh. Chứng minh rằng có ít nhất 5 học sinh có tháng sinhgiống nhau.iảiGiả sử có không quá 44 học sinh có tháng sinh giống nhauMột năm có 12 tháng, khi đó số học sinh của lớp có không quá: 12.4=12.4=48 (họcsinh)Theo nguyên lí Dirichlet phải có ít nhất 5 học sinh có tháng sinh giống nhau.Bài 3: 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ọcsinh được điểm 10. Chứng minh rằng ít nhất cũng tìm được 6 học sinh có điểmkiểm tra bằng nhau (điểm kiểm tra là một số tự nhiên)iải:Có 43 học sinh phân thành 8 loại điểm (từ 2 đến 9)Giả sử trong 88 loại điểm đều là điểm của không quá 5 học sinh thì lớp học có:5.8=40 học sinh, ít hơn 3 học sinh so với 43.Theo nguyên lý Dirichlet tồn tại 6 học sinh có điểm kiểm tra bằng nhau.Bài 4:Một lớp học có 50 học sinh, có duy nhất một học sinh thiếu nhiều bài tậpnhất là thiếu 3 bài tập. Chứng minh rằng tồn tại 17 học sinh thiếu 1 số bài tập nhưnhau (trường hợp không thiếu bài tập coi như thiếu 0 bài).iải:Giả sử mỗi loại bài tập có 16 học sinh.Số học sinh không quá 16×3=48 (thiếu 2 học sinh).Theo nguyên lí Dirichlet có ít nhất 17 học sinh thiếu một số bài tập như nhau.Bài 5:Trong hình vuông đơn vị (cạnh bằng 1) có 101 điểm. Chứng minh rằngcó năm điểm trong các điểm đã chọn được phủ bởi một đường tròn bán kínhGiải:Chia hình vuông ra làm 25 hình vuông bằng nhau, mỗi cạnh của hình vuông là0.2.Vì có 101 điểm, mà chỉ có 25 hình vuông, nên theo nguyên lí Dirichlet tồn tạihình vuông nhỏ chứa ít nhất năm điểm (trong 101 điểm đã cho). Vì hình vuông√√√này nội tiếp trong đường tròn bán kính R =. Donên dĩ nhiên đường tròn đồng tâm với đường tròn ngoại tiếp trênvà có bán kính chứa ít nhất năm điểm nói trên.Bài 6: Chứng minh rằng đối với một số n nguyên dương bất kì bao giờ ta cũng tìmđược một số tự nhiên mà các chữ số của nó bao gồm chỉ có chữ số 5 và chữ số 0 vàchia hết cho n.Giải: Xét n+ 1 số sau: 5; 55;...; 55...5 a1  a2  an1  ( n+1 chữ số 5). Theonguyên lý Dirichlet : với n+1 số trên ắt tồn tại hai số có cùng số dư khi chia cho n.Hiệu của hai số này là số có dạng: 55…50…0 gồm toàn chữ số 5 và chữ số 0 vàchia hết cho n.Bài 7: Cho 4 số dương bất kì. Chứng minh rằng có hai trong bốn số đó,chẳng hạn x và y, thoả mãn bất phương trình sau:√Giải:Gọi các số đã cho là x1, x2, x3, x4. Đặt(Đặt) ra làm 3 đoạn mỗi đoạnSuy ra tồn tại hai sốthuộc cùng 1 đoạn, mỗi đoạn (nguyên lí dirichlet).()( )√√√()()√4.Bài tập tự giải:Bài 1: Một lớp học có 30 học sinh. Khi viết chính tả, em A phạm 14 lỗi, các emkhác phạm ít lỗi hơn. Chứng minh rằng có ít nhất là 3 học sinh không mắc lỗi hoặcmắc số lỗi bằng nhau.Bài 2: Cho 5 người tùy ý. Chứng minh rằng trong số đó có ít nhất là hai người cósố người quen bằng nhau ( chú ý là A quen B 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ủalịch thi đấu cũng có hai đội đã đấu được một số trận như nhau.Bài 4: Chứng minh rằng trong 1007 số tự nhiên bất kỳ luôn tồn tại hai số sao chotổng hoặc hiệu của chúng chia hết cho 2011.Bài 5: Chứng minh rằng trong 2011 số tự nhiên liên tiếp bất kỳ luôn tồn tại một sốcó tổng các chữ số chia hết cho 28.5.Tài liệu tham khảo:[1] Nguyễn Hữu Điển, Phương pháp DIRICHLET và ứng dụng, NXB Khoa họcvà kĩ thuật Hà nội, 1999.[2] Phan Huy Khải, Các bài toán cơ bản của số học, NXB Giáo dục, 2009.[3]Nguyễn Văn Vĩnh, 23 chuyên đề giải 1001 bài toán sơ cấp, NXB Giáo dục,2005.

Tài liệu liên quan

Những nguyên tắc cơ bản trong phân tích công ty.doc
- 37
- 901
- 3
Những nguyên lí cơ bản của chủ nghĩa mac lenin
- 15
- 570
- 0
những nguyên lí cơ bản của chủ nghĩa mác_lênin
- 8
- 496
- 0
NHỮNG NGUYÊN LÍ CƠ BẢN CỦA CHỦ NGHĨA mác lê nin pptx
- 40
- 8
- 0
bài tiểu luận môn những nguyên lí cơ bản của chủ nghĩa mac – lenin
- 37
- 2
- 6
bài giảng những nguyên tắc cơ bản trong luật thương mại quốc tế
- 12
- 5
- 10
Những nguyên tắc cơ bản trong kinh doanh khởi nghiệp
- 72
- 701
- 0
Những nguyên tắc cơ bản trong khởi nghiệp kinh doanh potx
- 72
- 758
- 1
những nguyên lý cơ bản trong nghiệp vụ quản tri nhà hàng khách sạn.
- 56
- 689
- 0
Những nguyên tắc cơ bản trong khai cuộc pot
- 6
- 497
- 0