Tài liệu Bài tập về ứng dụng một số nguyên lý cơ bản

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI ************ NGUYỄN QUỐC PHƢƠNG BÀI TẬP VỀ ỨNG DỤNG MỘT SỐ NGUYÊN LÝ CƠ BẢN Chuyên ngành: Đại số và lý thuyết số Mã số : 60.46.05 LUẬN VĂN THẠC SĨ KHOA HỌC TOÁN HỌC Ngƣời hƣớng dẫn khoa học: PGS - TS Dƣơng Quốc Việt HÀ NỘI - 2011 MỤC LỤC LỜI MỞ ĐẦU ........................................................................................................................4 CHƢƠNG I: NGUYÊN LÝ DIRICHLET....................................................................6 1.1 Nguyên lý Dirichlet: ............................................................................. 6 1.2 Một số ví dụ: ........................................................................................ 6 1.2.1 Những bài toán khi giải phải nhận ra “lồng”: .................................. 6 1.2.2 Những bài toán khi giải phải nhận ra cả thỏ và lồng: ...................... 8 1.3 Một số bài tập....................................................................................... 9 1.3.1 Đề bài ............................................................................................... 9 1.3.2 Lời giải ........................................................................................... 11 CHƢƠNG II: NGUYÊN LÝ CƠ BẢN CHO CÁC BÀI TOÁN ĐẾM ........... 16 2.1 Nguyên lý đếm: .................................................................................. 16 2.1.1 Nguyên lý cộng: ............................................................................. 16 2.1.2 Nguyên lý nhân: ............................................................................. 16 2.1.3 Hoán vị - Chỉnh hợp - Tổ hợp: ...................................................... 16 2.1.4 Nguyên lý bù trừ: ........................................................................... 17 2.2 Một số ví dụ: ...................................................................................... 18 2.2.1 Các bài toán sử dụng nguyên lý cộng và nhân để giải: ................. 18 2.2.2 Các bài toán sử dụng hoán vị - chỉnh hợp - tổ hợp để giải: ........... 20 2.2.3 Các bài toán sử dụng nguyên lý bù trừ để giải: ............................ 21 2.2.4 Sử dụng phép song ánh: ................................................................. 21 2.3 Một số bài tập..................................................................................... 23 2.3.1 Đề bài ............................................................................................. 23 2.3.2 Lời giải ........................................................................................... 28 CHƢƠNG III: NGUYÊN LÝ CỰC TRỊ RỜI RẠC ............................................... 53 3.1 Nguyên lý cực trị rời rạc: ................................................................... 53 3.2 Một số ví dụ: ...................................................................................... 53 3.2.1 Áp dụng nguyên lý để giải toán hình học: ..................................... 53 2 3.2.2 3.2.3 3.2.4 Áp dụng nguyên lý để giải các bài toán số học và đại số: ............ 57 Tìm cực trị rời rạc: ......................................................................... 59 Thiết lập thứ tự trên các yếu tố bình đẳng ..................................... 60 3.3 Một số bài tập:.................................................................................... 63 3.3.1 Đề bài ............................................................................................ 63 3.3.2 Lời giải ........................................................................................... 64 CHƢƠNG IV: NGUYÊN LÝ XUỐNG THANG ................................................... 68 4.1 Nguyên lý xuống thang: ..................................................................... 68 4.2 Một số ví dụ: ...................................................................................... 68 4.2.1 Nguyên lý xuống thang với phƣơng trình nghiệm nguyên ............ 68 4.2.2 Nguyên lý xuống thang trong hình học ......................................... 69 4.3 Một số bài tập..................................................................................... 70 4.3.1 Đề bài ............................................................................................. 70 4.3.2 Lời giải ........................................................................................... 71 CHƢƠNG V: PHƢƠNG PHÁP HÀM SINH .......................................................... 78 5.1 Phƣơng pháp hàm sinh ....................................................................... 78 5.2 Một số ví dụ: ...................................................................................... 78 5.2.1 Xác định số hạng tổng quát của dãy số truy hồi ............................ 78 5.2.2 Phƣơng pháp hàm sinh cho các bài toán chứng minh, rút gọn ...... 80 5.2.3 Phƣơng pháp hàm sinh cho bài toán đếm số nghiệm .................... 81 5.3 Một số bài tập..................................................................................... 84 5.3.1 Đề bài ............................................................................................. 84 5.3.2 Lời giải ........................................................................................... 85 KẾT LUẬN .......................................................................................................................... 91 TÀI LIỆU THAM KHẢO ............................................................................................... 92 3 LỜI MỞ ĐẦU Các nguyên lý cơ bản tuy rất đơn giản, nhƣng việc vận dụng nó nhƣ thế nào trong tình huống cụ thể thật không đơn giản chút nào. Luận văn tập trung sƣu tầm, phân loại, hệ thống, sáng tác, giải các bài toán về 5 nguyên lý cơ bản, đó là: Nguyên lý Dirichlet; Nguyên lý cực trị rời rạc; Nguyên lý xuống thang; Nguyên lý cơ bản cho các bài toán đếm; Phƣơng pháp hàm sinh và đƣa ra hệ thống bài tập phù hợp. Luận văn đƣợc chia làm 5 chƣơng sau đây:  Chương I: Nguyên lý Dirichlet. Chương này gồm 3 phần chính: Phát biểu về nguyên lý Dirichlet, các ví dụ điển hình được chia làm 2 loại (những bài toán khi giải phải nhận ra thỏ và những bài toán khi giải phải nhận ra cả lồng và thỏ). Cuối cùng là hệ thống bài tập chọn lọc có lời giải.  Chương II: Nguyên lý cơ bản cho các bài toán đếm. Trước hết chúng tôi nhắc lại nguyên lý cộng, nguyên lý nhân và nguyên lý bù trừ, định nghĩa hoán vị, chỉnh hợp, tổ hợp. Sau đó là các ví dụ điển hình cho các dạng toán được trình bày lời giải một cách chi tiết theo các cách khác nhau. Cuối cùng là hệ thống bài tập với lời giải chi tiết.  Chương III: Nguyên lý cực trị rời rạc. Chương này gồm các vấn đề: Phát biểu nguyên lý cực trị rời rạc; Các ví dụ điển hình, phân dạng về áp dụng nguyên lý để giải các bài toán hình học, giải các bài toán đại số và số học, tìm cực trị rời rạc, thiết lập thứ tự trên các yếu tố bình đẳng. Sau cùng là một số bài tập chọn lọc với lời giải chi tiết.  Chương IV: Nguyên lý xuống thang. Chương này gồm ba phần chính: Sơ lược về nguyên lý xuống thang; Các ví dụ điển hình về nguyên lý xuống thang cho phương trình nghiệm nguyên và cho các bài toán hình học. Cuối cùng là hệ thống bài tập chọn lọc có lời giải chi tiết. 4  Chƣơng V: Phƣơng pháp hàm sinh. Chƣơng này cũng bao gồm 3 phần: Phần đầu nêu khái niệm hàm sinh và kiến thức hỗ trợ. Phần 2 gồm các ví dụ điển hình sử dụng phƣơng pháp hàm sinh để tìm số hạng tổng quát của dãy số cho dƣới dạng truy hồi, sử dụng phƣơng pháp hàm sinh cho các bài toán chứng minh, rút gọn và sử dụng phƣơng pháp hàm sinh cho các bài toán đếm số nghiệm. Phần 3 là hệ thống bài tập có lời giải. Tác giả xin bày tỏ lòng biết ơn sâu sắc đến PGS.TS. Dƣơng Quốc Việt, ngƣời thầy đã tận tình hƣớng dẫn và tạo mọi điều kiện thuận lợi giúp tác giả hoàn thành luận văn này. Hà nội, ngày 15 tháng 9 năm 2011 Tác giả 5 CHƢƠNG I: NGUYÊN LÝ DIRICHLET 1.1 Nguyên lý Dirichlet: Khi giải một số bài toán số học và hình học chúng ta đã đƣợc làm quen với một nguyên lí rất nổi tiếng về sự tồn tại, đó là nguyên lí Dirichlet hay vẫn gọi là “Nguyên lí Lồng và Thỏ”. Nguyên lí đƣợc phát biểu nhƣ sau: Phát biểu 1: Không thể nhốt 5 chú thỏ vào 2 chiếc lồng, sao cho mỗi lồng không quá 2 chú. Phát biểu 2: Có 10 cái lồng, mỗi cái chỉ nhốt đƣợc nhiều nhất là 10 con và có 101 con thỏ thì có ít nhất 1 con thỏ ở ngoài lồng. Phát biểu 3: Nếu k lồng chứa kn+1 thỏ, thì tồn tại một trong các lồng chứa ít nhất n+1 thỏ. .… Tuy đƣợc phát biểu dƣới nhiều dạng khác nhau nhƣng cái cốt của nguyên lí vẫn là chỉ ra sự tồn tại. Nguyên lí không xác định đƣợc chính xác đối tƣợng nhƣng việc chỉ ra nó tồn tại đã mang lại nhiều ý nghĩa trong cuộc sống cũng nhƣ trong toán học. Cái khó của nguyên lý này là phải nhận biết đƣợc hoặc tự sáng tạo ra “lồng” và “thỏ”. Các yếu tố “thỏ” và “lồng” thƣờng bị che khuất, chúng đòi hỏi ngƣời giải phải tự phát hiện. 1.2 Một số ví dụ: 1.2.1 Những bài toán khi giải phải nhận ra “lồng”: Ví dụ 1: Chứng minh rằng trong n + 1 số nguyên dƣơng phân biệt không vƣợt quá 2n, bao giờ cũng có 2 số nguyên tố cùng nhau. Lời giải: Chia các số từ 1 đến 2n thành n tập hợp * +;{3;4};…;{2n-1;2n}. Vì ta có n+1 số nên theo nguyên lý Dirichlet có 2 số trong cùng một tập hợp. Rõ ràng hai số đó nguyên tố cùng nhau. 6 Trong lời giải này ta đã sáng tạo ra n lồng,đó chính là n tập hợp. Ví dụ 2: Cho hình vuông và 13 đƣờng thẳng phân biệt sao cho mỗi đƣờng thẳng đó chia hình vuông thành 2 tứ giác có tỉ số diện tích là 2:3. Chứng minh rằng có ít nhất 4 đƣờng thẳng trong số 13 đƣờng thẳng đã cho đồng quy. Lời giải: Nếu một đƣờng thẳng chia một hình vuông thành 2 tứ giác có tỉ số diện tích là 2:3 thì nó phải đi qua điểm nằm trên đƣờng nối trung điểm hai cạnh đối diện của hình vuông và chia đoạn đó theo tỉ số là 2:3. Trong hình vuông thì có tất cả 4 điểm nhƣ vậy và 13 đƣờng thẳng đã cho đều đi qua 1 trong 4 điểm đó. Theo nguyên lý Dirichlet, ít nhất 4 đƣờng thẳng trong số 13 đƣờng thẳng đã cho đồng quy ⟹ điều phải chứng minh. Ví dụ 3: Cho a, b, c, d, e, f, g, h, k là các hằng số thực khác 0, còn x, y là các biến, đặt A = ax + by + c, B = dx + ey + f, C = gx + hy + k. Chứng minh rằng trong 8 hệ sau có ít nhất một hệ vô nghiệm: { ,{ ,{ , { , { ,{ , { ,{ Lời giải: Mỗi miền nghiệm của một hệ tƣơng ứng với một miền mở trong mặt phẳng, bị giới hạn bởi ba đƣờng thẳng có phƣơng trình là A = 0; B = 0; C = 0. Vì 3 đƣờng thẳng chỉ phân mặt phẳng thành tối đa 7 miền nên trong 8 hệ đã cho có ít nhất một hệ vô nghiệm. Ví dụ 4: Ngƣời ta tung ngẫu nhiên nhiều hơn 200 viên sỏi vào một mảnh đất hình vuông có diện tích 100m2. Chứng minh rằng tồn tại 3 viên thẳng hàng hoặc lập thành 3 đỉnh một tam giác có diện tích không vƣợt quá 0,5m2. Lời giải: Ta chia đám đất thành 100 ô vuông bằng nhau bởi các đƣờng thẳng song song với các cạnh của hình vuông. Vì số viên sỏi lớn hơn 200 nên ắt có ba viên A; B; C thuộc cùng một ô vuông. Nếu A, B, C không thẳng hàng thì chúng lập thành một tam giác nằm trong một hình vuông có độ dài bằng 1m. Do đó diện tích của nó không vƣợt quá 0,5m2. 7 Trong lời giải bài toán này ta đã phải sáng tạo ra 100 cái lồng, đó là 100 ô vuông. Ví dụ 5: Với n là một số nguyên dƣơng cho trƣớc, chứng minh rằng trong n + 1 số nguyên dƣơng tùy ý, luôn tồn tại 2 số có hiệu chia hết cho n. Lời giải: Nhận xét rằng các số dƣ có đƣợc khi mang chia n + 1 số nguyên cho n chỉ có thể là 0,1,2,…,n – 1. Vì vậy ắt phải có hai số khi chia cho n có cùng số dƣ. Do đó hiệu hai số này phải chia hết cho n. Số lồng mà ta cần nhận ra trong bài toán này chính là n. 1.2.2 Những bài toán khi giải phải nhận ra cả thỏ và lồng: Ví dụ 1: Chứng minh rằng luôn tồn tại một số nguyên dƣơng n, không vƣợt quá 2010, để 2n – 1 chia hết cho 2011. Lời giải: Xét dãy ai = 2i, i = 1,2,3,…,2011. Nhận thấy các số trong dãy đều không chia hết cho 2011. Vì vậy, khi mang những số này chia cho 2011 thì các số dƣ của nó chỉ nằm trong tập 2010 số { 1,2,3,…,2010}. Do có 2011 số nên phải có 2 số at > ah khi chia cho 2011có cùng số dƣ. Đặt n = t – h, khi đó n < 2011 và at – ah = ah(2n – 1) chia hết cho 2011, nên 2n – 1 chia hết cho 2011. Mấu chốt là ta phải tạo ra 2011 thỏ ai = 2i, i =1,2,3,…,2011 và 2010 lồng {1,2,3,..,2010}. Ví dụ 2: Chứng minh rằng trong n + 1 số nguyên dƣơng không vƣợt quá 2n, bao giờ cũng tồn tại hai số sao cho số này là bội của số kia(Bài toán của Erdos). Lời giải: Gọi các số đã cho là a1,a2,…,an+1. Bây giờ ta phân tích các số này ở dạng tiêu chuẩn: ai = .bi với bi là số tự nhiên lẻ, i = 1,2,3,…,n+1. Nhƣ vậy ta đƣợc n + 1 số tự nhiên lẻ b1, b2,…,bn+1 không vƣợt quá 2n. Nhƣ vậy, trong 2n số nguyên dƣơng đầu tiên, chỉ có n số lẻ, cho nên trong các số b1,b2,…,bn+1 8 ắt phải có hai số nhƣ nhau, chẳng hạn bj = bm = b. Khi đó aj = b và am = b sẽ có một số là bội của số kia. Đây là một bài toán mà khi giải ta phải nhận ra n lồng, đó là n số lẻ nằm trong các số không vƣợt quá 2n, sáng tạo ra n + 1 thỏ b1, b2,…,bn+1. Ví dụ 3: Ngƣời ta sơn tất cả các cạnh và đƣờng chéo của một hình lục giác lồi bởi hai màu khác nhau, mỗi cạnh hoặc đƣờng chéo chỉ đƣợc sơn một màu. Chứng minh rằng trong đó tồn tại một tam giác có ba cạnh cùng màu. Lời giải: Giả sử lục giác đó là ABCDEF và hai màu sơn là xanh và đỏ. Trong 5 đoạn AB,AC,AD,AE,AF phải có ba đoạn đƣợc sơn cùng màu. Chẳng hạn 3 đoạn đó là AB,AC,AD, và đƣợc sơn màu đỏ. Ta xét tiếp 3 đoạn BC,CD,DB. Nếu trong ba đoạn này có một đoạn đƣợc sơn màu đỏ, chẳng hạn BC, thì ba cạnh của tam giác ABC đƣợc sơn cùng màu đỏ. Nếu ba đoạn BC,CD,DB không có đoạn nào sơn màu đỏ thì nó phải đƣợc sơn toàn màu xanh khi đó tam giác BCD có ba cạnh đƣợc sơn cùng màu xanh. 1.3 Một số bài tập 1.3.1 Đề bài Bài 1: Trong mặt phẳng tọa độ cho đa giác lồi có số cạnh không nhỏ hơn 5 và tất cả các đỉnh có tọa độ nguyên(ta gọi chúng là các điểm nguyên). Chứng minh rằng bên trong hoặc trên cạnh đa giác có ít nhất một điểm nguyên khác nữa. Bài 2: Trong mặt phẳng cho 25 điểm sao cho từ 3 điểm bất kỳ trong số chúng đều tìm đƣợc hai điểm có khoảng cách nhỏ hơn 1. Chứng minh rằng tồn tại một hình tròn có bán kính bằng 1 chứa không ít hơn 13 điểm. Bài 3: Giả sử a,b,x0 là các số tự nhiên khác 0. Chứng minh rằng, trong dãy x0, x1= ax0+b, x2 = ax1+b,…,xn= axn-1+b,…có vô hạn số là hợp số. Bài 4: Chứng minh rằng nếu x1,x2,…,x12 là nghiệm của hệ bất phƣơng trình: 9 { ( ( ) ) ( ) thì có ít nhất 3 số âm. Bài 5: Chứng minh rằng trong một hình tròn có bán kính bằng 1, không thể có nhiều hơn 5 điểm sao cho khoảng cách giữa 2 điểm bất kỳ trong chúng đều lớn hơn 1. Bài 6: Cho 40 số nguyên dƣơng a1,a2,….,a19 và b1,b2,…,b21 thỏa mãn: { Chứng minh rằng tồn tại 4 số ai, aj,bk,bl sao cho { Bài 7: Tại một vòng chung kết cờ vua có 8 bạn thí sinh thi đấu theo thể thức vòng tròn( bất kể hai thí sinh nào cũng phải thi đấu với nhau một ván). Chứng minh rằng tại một thời điểm bất kỳ của cuộc thi bao giờ cũng có ít nhất 2 thí sinh có số ván đã đấu là nhƣ nhau. Bài 8: Một cửa hàng đồ điện trong mỗi ngày bán đƣợc ít nhất một chiếc quạt và trong mỗi tuần bán đƣợc không quá 12 chiếc. Chứng minh rằng trong một số ngày liên tiếp nào đó cửa hàng đã bán đƣợc tổng số 20 chiếc quạt. Bài 9: Cho dãy số u1,u2,…,un trong đó ui bằng 0 hoặc bằng 1 thỏa mãn điều kiện sau: Bất kỳ 2 bộ 5 số liên tiếp nào từ dãy số đã cho đều không trùng nhau. Chứng minh rằng n ≤ 36. Bài 10: Cho một dãy gồm 4n số dƣơng có tính chất: 4 số khác nhau bất kỳ của dãy lập thành một cấp số nhân. Chứng minh rằng dãy số đó phải có ít nhất n số bằng nhau. 10 Bài 11: Số hạng thứ nhất và công sai d ≠ 0 của một cấp số cộng có vô hạn số hạng là các số nguyên. Chứng minh rằng tồn tại một số hạng của dãy mà biểu diễn thập phân của nó chứa chữ số 9. Bài 12: Cho dãy số nguyên u1,u2,…,un với n ≥ 2. Chứng minh rằng tồn tại dãy con trong đó 1 ≤ k1 < … < km ≤ n sao cho n. Bài 13: Chứng minh rằng không tồn tại một dãy tăng các số tự nhiên u1; u2; u3; …; un;…sao cho với mọi n và m ta có umn = um + un. Bài 14: Ngƣời ta sơn đen một số cung của đƣờng tròn với tổng độ dài các cung đó bé hơn nửa đƣờng tròn. Chứng minh rằng tồn tại một đƣờng kính có hai đầu không bị sơn đen. Bài 15: Trong một đƣờng tròn bán kính bằng 1 cho 7 điểm phân biệt mà khoảng cách giữa hai điểm bất kỳ đều không nhỏ hơn 1. Chứng minh rằng trong 7 điểm đã cho có ít nhất một điểm trùng với tâm. 1.3.2 Lời giải Bài 1: Từ đề bài suy ra số đỉnh của đa giác lớn hơn hoặc bằng 5. Mỗi cặp số nguyên (xi ,yi) chỉ có thể rơi vào 1 trong 4 trƣờng hợp sau: xi chẵn và yi chẵn; xi chẵn và yi lẻ; xi lẻ và yi chẵn; xi lẻ và yi lẻ. Vì ta có nhiều hơn hoặc bàng 5 đỉnh nên có ít nhất hai đỉnh mà hoành độ và tung độ của chúng có tính chẵn lẻ giống nhau. Khi đó trung điểm của đoạn thẳng nối hai điểm này là một điểm nguyên và hiển nhiên trung điểm đó nằm trên hoặc trong cạnh của đa giác. Bài 2: Nếu 2 điểm bất kỳ trong số 25 điểm đã cho đều có khoảng cách nhỏ hơn 1 thì ta chọn một điểm bất kỳ làm tâm vẽ một đƣờng tròn bán kính bằng 1 thì hình tròn vừa dựng sẽ chứa cả 25 điểm đó. Trong trƣờng hợp có hai điểm, giả sử là A và B có khoảng cách không nhỏ hơn 1, vẽ hình tròn (C1) tâm A bán kính 1 và đƣờng tròn (C2) tâm B bán kính 1. Khi đó không tồn tại điểm nào trong 25 điểm đã cho nằm ngoài cả (C1) và (C2). Thật vậy, giả sử ngƣợc 11 lại có điểm C nằm ngoài (C1)và (C2), rõ ràng khi đó AB ≥ 1, AC ≥ 1, CB ≥ 1 mâu thuẫn với giả thiết. Nhƣ vậy có ít nhất một trong hai đƣờng tròn (C1) hoặc (C2) chứa không ít hơn 13 điểm đã cho. Bài 3: Dễ thấy xn= axn-1+b xn-1+b >xn-1 với mọi số tự nhiên n ≠ 0. Do đó x0,x1,x2,…,xn,…lập thành một dãy số tăng.Và x1= ax0+b>a nên các số hạng của dãy kể từ x1 đều lớn hơn a. Đặt d = ƢCLN(a,b). Xét trƣờng hợp d > 1, khi đó xi chia hết cho d với mọi i≥1, suy ra điều phải chứng minh. Xét trƣờng hợp d = 1, khi đó a và xk (k≥1) nguyên tố cùng nhau. Gọi N là số nguyên dƣơng nguyên tố cùng nhau với a. Xét các số xk,xk+1,…,xk+N, với k 1. Khi đó ta tìm đƣợc 2 số xp, xq(p > q) có cùng số dƣ (modN). Do đó xp – xq = a(xp-1-xq-1) và (a,N) = 1, suy ra xp-1-xq-1 chia hết cho N. Tiếp tục quá trình đó xp-2 - xq-2,…, xp-q+k-xk chia hết cho N. Chọn N = xk (thì N > a ≥ 1) , ta suy ra xp-q+k chia hết cho N. Do đó xp-q+k là hợp số. Nhƣ vậy trong dãy xk,xk+1,…, xk+N có chứa hợp số là xp-q+k.Thay thế xk bởi xp-q+k+1 ta lại có trong dãy xh, xh+1, …, ( h = p-q+k+1) cũng chứa một hợp số. Từ đó suy ra các hợp số trong dãy * + là vô hạn. Bài 4: Giả sử trong 12 số x1, x2, …, x12, là nghiệm của hệ bất phƣơng trình đã cho có ít hơn 3 số dƣơng. Khi đó bao giờ cũng chọn đƣợc bốn chỉ số liên tiếp i-1, i, i+1, i+2 sao cho xi-1, xi, xi+1+, xi+2 đều âm. Theo các bất phƣơng trình trong hệ, ta có: xi-1 - xi + xi+1 > 0, xi - xi+1 + xi+2 > 0. Từ đó suy ra xi-1 + xi+2 > 0. Điều này mâu thuẫn với giả thiết xi-1 và xi+2 đều âm. Vì vậy số các số dƣơng phải lớn hơn hoặc bằng 3. Hoàn toàn tƣơng tự ta chứng minh đƣợc cho các số âm. Bài 5: Xét 6 điểm trong đƣờng tròn tâm O. Ta sẽ chứng minh rằng trong 6 điểm đó tồn tại hai điểm có khoảng cách ≤ 1. Ta xét điểm P1, kéo dài OP1 cắt đƣờng tròn tại A. Lấy trên đƣờng tròn, về hai phía của A điểm B và C sao cho 12 ̂ = ̂ = 600. Nếu trong hình quạt AOB có chứa một điểm khác P1, ta gọi là P2, thì dễ thấy P1P2 ≤ 1. Tƣơng tự, nếu trong hình quạt AOC chứa một điểm khác P1. Ta chia hình quạt lớn BOC thành 4 hình quạt bằng nhau, suy ra góc ở tâm của mỗi hình quạt bằng 600. Ta có 5 điểm còn lại trong 4 hình quạt, vì vậy có ít nhất một hình quạt chứa 2 điểm đang xét, suy ra khoảng cách giữa hai điểm đó ≤ 1. Từ đó ta có điều phải chứng minh. Bài 6: Gọi S là tập các tổng có dạng ai + bj với 1≤ i ≤ 19, 1≤ j ≤ 21, khi đó | | = 19.21 = 399. Từ giả thiết suy ra các phần tử của S chỉ nhận các giá trị từ 2 đến 400. Nếu S = {2,3,…,400} thì a1 = b1 = 1 và a19 = b21 = 200, suy ra điều phải chứng minh. Nếu S ≠ {2,3,…,400} thì tồn tại 2 phần tử của S có cùng giá trị. Giả sử đó là ai + bk = aj + bl, ta cũng suy ra điều phải chứng minh. Bài 7: Xét một thời điểm bất kỳ của cuộc thi. Nếu có ít nhất hai ngƣời chƣa thi đấu thì bài toán là hiển nhiên. Nếu tồn tại đúng một ngƣời chƣa chơi ván nào thì 7 thí sinh còn lại, mỗi ngƣời thi đấu tối thiểu là 1 ván, tối đa là 6 ván, theo nguyên lý Dirichlet tồn tại 2 thí sinh có số ván thi đấu nhƣ nhau. Tƣơng tự, nếu cả 8 ngƣời đã thi đấu thì mỗi ngƣời phải đấu ít nhất 1 ván và tối đa là 7 ván nên cũng tồn tại 2 thí sinh có số ván đấu nhƣ nhau. Bài 8: Xét 21 ngày liên tiếp bất kỳ. Gọi S(n) là số quạt mà cửa hàng đó bán đƣợc tính đến ngày thứ n (1≤ n ≤ 21). Vì trong mỗi ngày, cửa hàng bán đƣợc ít nhất một chiếc quạt nên {S(n)} là dãy tăng nghiêm ngặt. Hơn nữa, trong mỗi tuần cửa hàng bán đƣợc không quá 12 chiếc quạt nên 1≤ S(n)≤ 36 với mọi n = . Vì { S(n) / 1 ≤ n ≤ 21} có 21 số hạng nên theo nguyên lý Dirichlet, tồn tại 1 ≤ i 25. Hơn nữa, ta lại chỉ có 25 cách lập các bộ gồm 5 số (a1, a2, a3, a4, a5), trong đó ai = 0 hoặc ai = 1. Suy ra từ dãy n ≥ 37 tồn tại ít nhất hai bộ 5 số liên tiếp trùng nhau (mâu thuẫn). Vậy ta phải có n ≤ 36. Bài 10: Vì n = 1 thì bài toán là hiển nhiên nên chỉ cần xét n > 1. Giả sử trong dãy số đã cho,mỗi số hạng của nó chỉ lặp lại nhiều nhất là n – 1 lần. Khi đó theo nguyên lý Dirichlet, trong 4n số dƣơng đó bao giờ cũng chọn đƣợc 5 số khác nhau là a,b,c,d,e. Không mất tính tổng quát, giả sử a < b < c < d < e. Khi đó 4 số a, b, c, d và 4 số a, b, c, e đều lập thành cấp số nhân. Do đó nên e = d. Điều này mâu thuẫn với giả thiết e ≠ d. Vậy ta có điều phải chứng minh. Bài 11: Số hạng thứ s của cấp số cộng tính bởi công thức us = u1 +(s -1).d, trong đó u1 là số hạng đầu tiên, d là công sai. Không mất tính tổng quát, giả sử d > 0. Theo nguyên lý Dirichlet, trong d + 1 số sau: 9, 99, 999 ,…, ⏟ có hai số có cùng số dƣ khi chia cho d. Tức là luôn tồn tại số có dạng 99… ⏟ chia hết cho d. Giả sử u1 là số nguyên có n chữ số. Bổ sung các chữ số 0 nếu cần, ta có thể coi k ≥ n và số A = 99… ⏟ Khi đó nếu đặt m = chia hết cho d. thì số hạng thứ m + 1 trong cấp số cộng đã cho có biểu diễn thập phân chứa chữ số 9. Bài 12: Xét n +1 số . Theo nguyên lý Dirichlet trong n+1 số đó phải có ít nhất 2 số , khi chia cho n có cùng số dƣ (0≤ j < k ≤ n, ở đây ta hiểu khi j = 0 thì 14 là số 0). Điều đó có nghĩa là số ( ( ) chia hết cho n. Suy ra ) chia hết cho n. Bài 13: Giả sử tồn tại dãy thỏa mãn yêu cầu bài toán. Chọn n là số tự nhiên lớn hơn u2. Khi đó u2n = un + u2 < un + n. Điều này chứng tỏ các số un+1, un+2, …, u2n là n số nguyên phân biệt nằm trong đoạn [un+1, un+ n-1]. Đoạn này chỉ gồm n – 1 số nguyên phân biệt, nên giả sử sai ⟹ điều phải chứng minh. Bài 14: Ta sơn xanh tất cả các cung đối xứng với các cung đã bị sơn đen của đƣờng tròn. Từ giả thiết suy ra tổng độ dài tất cả các cung đã bị sơn bé hơn nửa vòng tròn. Do đó tồn tại một điểm chƣa bị sơn, và đƣờng kính qua điểm này chính là đƣờng kính cần tìm. Bài 15: Giả sử không có điểm nào trong 7 điểm đã cho trùng với tâm. Chia hình tròn đã cho thành 6 hình quạt bằng nhau. Theo nguyên lý dirichlet, tồn tại hai điểm cùng nằm trong hình quạt( kể cả biên), nhƣ vậy khoảng cách giữa hai điểm đó nhỏ hơn 1 (mâu thuẫn với giả thiết). Do đó phải có ít nhất một điểm trùng tâm. 15 Chƣơng II: NGUYÊN LÝ CƠ BẢN CHO CÁC BÀI TOÁN ĐẾM 2.1 Nguyên lý đếm: Bài toán đếm số phần tử của một tập hợp xuất hiện khá phổ biến trong khoa học cũng nhƣ trong đời sống. Nếu số phần tử không nhiều thì ta có thể đếm số phần tử của nó bằng cách liệt kê. Tuy nhiên nếu số phần tử của nó lớn thì cách đếm trực tiếp là không khả thi. Ba nguyên lý cơ bản nhất cho các bài toán đếm là nguyên lý cộng, nguyên lý nhân và nguyên lý bù trừ. 2.1.1 Nguyên lý cộng: Giả sử một công việc có thể tiến hành theo một trong k phƣơng án A1, A2,…, Ak. Có n1 cách chọn phƣơng án A1, n2 cách chọn phƣơng án A2,…, nk cách chọn phƣơng án Ak. Khi đó công việc có thể đƣợc thực hiện bởi n1 + n2 + … + nk cách. 2.1.2 Nguyên lý nhân: Giả sử một công việc A gồm k công đoạn A1, A2, …, Ak . Công đoạn A1 có thể thực hiện theo n1 cách, công đoạn A2 có thể thực hiện theo n2 cách,…, công đoạn Ak có thể thực hiện theo nk cách. Khi đó công việc đó có thể thực hiện theo n1.n2…nk cách. 2.1.3 Hoán vị - Chỉnh hợp - Tổ hợp: Hoán vị : Cho tập A gồm n phần tử (n ≥ 1). Mỗi cách sắp thứ tự n phần tử của tập hợp A đƣợc gọi là một hoán vị của n phần tử đó. Số hoán vị của n phần tử là: Pn = n! =1.2.3...n.(n ≥ 1). Chỉnh hợp: Cho tập hợp A gồm n phần tử (n ≥ 1). Mỗi bộ gồm k phần tử (1 ≤ k ≤ n) sắp thứ tự của tập A đƣợc gọi là một chỉnh hợp chập k của n phần tử đó. Số chỉnh hợp chập k của n phần tử là: 16 =( ) (1 ≤ k ≤ 1). Tổ hợp: Cho tập hợp A gồm n phần tử (n ≥ 1). Mỗi tập hợp con của A gồm k phần tử phân biệt (0 ≤ k ≤ n), đƣợc gọi là một tổ hợp chập k của n phần tử đã cho. Số tổ hợp chập k của n phần tử là: = ( ) với (0 ≤ k ≤ n). 2.1.4 Nguyên lý bù trừ: Nguyên lý bù trừ là một quy tắc hữu hiệu, trong việc giải quyết những bài toán đếm. Khi hai công việc có thể được làm đồng thời, ta không thể dùng quy tắc cộng để tính số cách thực hiện nhiệm vụ gồm cả hai 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 việc thứ nhất và số cách làm việc thứ hai 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ý đếm này bằng ngôn ngữ tập hợp. Cho A1, A2 là hai tập hữu hạn, khi đó │A1∪ A2│ =│A1│ +│A2│- │A1∩A2│. Từ đó với 3 tập hợp A1,A2,A3, ta có: |⋃ | ∑| | ∑| | Bằng quy nạp, với k tập hữu hạn A1,A2,…,Ak ta có: │ A1∪ A2∪ …∪ Ak│ =N1 – N2 +N3 -…+ (-1)k-1 Nk. Trong đó Nm (1≤ m≤ k) là tổng phần tử của tất cả các giao m tập lấy từ k tập đã cho. Bây giờ ta đồng nhất tập Am(1 ≤ m ≤ k) với tính chất Am cho trên tập hữu hạn U nào đó và đếm xem có bao nhiêu phần tử của U sao cho không thỏa mãn 17 bất kỳ một tính chất Am nào. Gọi N là số phần tử của U, là số cần đếm. Ta có: = N - │ A1 ∪ A2 ∪ … ∪ Ak│ = N – N1 + N2 -…+ (-1)kNk.. Trong đó Nm là tổng các phần tử của U thỏa mãn m tính chất lấy từ k tính chất đã cho. Công thức này đƣợc gọi là nguyên lý bù trừ. Nó cho phép tính qua các Nm trong trƣờng hợp các số này dễ tính toán hơn. Ngoài các nguyên lý trên ta còn có thể sử dụng phép song ánh, phương pháp đếm bằng hệ thức truy hồi,… 2.2 Một số ví dụ: 2.2.1 Các bài toán sử dụng nguyên lý cộng và nhân để giải: Ví dụ 1: Có bao nhiêu số tự nhiên a) Lẻ có 4 chữ số, đôi một khác nhau. b) Chẵn có bốn chữ số đôi một khác nhau. Lời giải: a) Mỗi số tự nhiên có 4 chữ số có dạng . Ta cần chọn a,b,c,d để đƣợc một số thỏa mãn đầu bài đòi hỏi.  Công đoạn 1, chọn d: có 5 cách.  Công đoạn 2, chọn a: có 8 cách.  Công đoạn 3, chọn b: có 8 cách.  Công đoạn 4, chọn c: có 7 cách . Theo quy tắc nhân có 5.8.8.7 = 2240 số thỏa mãn yêu cầu đòi hỏi. b) Mỗi số tự nhiên chẵn có 4 chữ số khác nhau có một trong các dạng: hoặc (d ϵ {2,4,6,8}). Theo quy tắc nhân: 1. Dạng có 9.8.7 = 504 số, 18 2. Dạng (d ϵ {2,4,6,8}) có 4.8.8.7 = 1792 số. Do đó theo quy tắc cộng có 504 + 1792 =2296 số thỏa mãn bài toán. Trong câu a) của ví dụ 1 ta chỉ cần sử dụng quy tắc nhân, trong câu b) của ví dụ 1 ta sử dụng quy tắc cộng kết hợp quy tắc nhân. Ví dụ 2: Trong 6 chữ số 0, 1, 2, 3, 4, 5 có thể lập đƣợc bao nhiêu số gồm bốn chữ số khác nhau và trong bốn chữ số nhất thiết phải có chữ số 1. Lời giải: Cách 1: Mỗi số cần lập có một trong các dạng ,  Dạng có 5.4.3 = 60 số.  Dạng có 4.4.3 = 48 số. Tương tự mỗi dạng cũng có 48 số. Vậy theo quy tắc cộng, có 60 + 48 + 48 + 48 =204 số thoả mãn đề bài. Cách 2: Số các số tự nhiên có 4 chữ số khác nhau là : 5.5.4.3 = 300. Số các số tự nhiên có 4 chữ số khác nhau trong đó không có mặt chữ số 1 là 4.4.3.2 = 96. Do đó số các số thỏa yêu cầu đề bài là: 300 – 96 = 204. Ví dụ 3: Từ các chữ số 1, 2, 3, 4, 5, 6, 7, 8, 9 lập tất cả các số gồm bốn chữ số không trùng nhau. Hãy tìm tổng của tất cả các số này. Lời giải: Cách 1: Gọi A là tập hợp các số thoả mãn đề bài. Ta có | | = 9 . 8. 7. 6 = ∈ A đều tồn tại duy nhất một số 3024 số. Đối với số bất kì A sao cho ∈ = 11110. Do đó tập A gồm 3024: 2 = 1512 cặp + số, mỗi cặp có tổng là 11110. Vậy tổng tất cả các số trong A là: 1512.11110 = 16798320. Cách 2: Số các số có dạng tƣơng tự, mỗi dạng: , lập đƣợc là 8.7.6 = 336 số. Hoàn toàn ,… , 19 cũng có 336 số. Do đó tổng tất cả các chữ số hàng nghìn của tất cả các số lập đƣợc là 336(1+2+…+9) =15120. Hoàn toàn tƣơng tự, tổng các chữ số hàng trăm, chục, đơn vị của tất cả các số lập đƣợc mỗi loại cũng là: 22680. Vậy tổng tất cả các số lập đƣợc là: 15120(1+10+100+1000) = 16798320. 2.2.2 Các bài toán sử dụng hoán vị - chỉnh hợp - tổ hợp để giải: Ví dụ 1: Có 6 tem thƣ khác nhau và 6 phong bì khác nhau, hỏi có bao nhiêu cách chọn 3 tem thƣ dán vào 3 phong bì. Lời giải: Công đoạn 1, chọn ra 3 phong bì: Có Công đoạn 2, chọn ra 3 tem thƣ: Có cách. cách. Công đoạn 3, dán 3 tem thƣ vừa chọn vào 3 phong bì đã chọn : Có 3! Cách. Theo quy tắc nhân, có = 2400 cách. Trong bài này ta sử dụng hoán vị và tổ hợp kết hợp với quy tắc nhân. Ví dụ 2: Có bao nhiêu số tự nhiên có 13 chữ số sao cho chữ số 0 xuất hiện 2 lần, chữ số 1 xuất hiện 3 lần, các chữ số khác xuất hiện đúng một lần. Lời giải: Xét 13 ô trống: Ta cần đặt các chữ số 0,1,2,3,4 vào các ô( mỗi ô một chữ số) để đƣợc một số thỏa mãn yêu cầu bàn toán.  Công đoạn 1: Đặt 2 chữ số 0 vào, có cách.  Công đoạn 2: Đặt 3 chữ số 1 vào, có cách.  Công đoạn 3: Đặt 8 chữ số còn lại vào, có 8! cách. Theo quy tắc nhân có tất cả = 439084800 số thỏa mãn yêu cầu bài toán. 20