Tài liệu Về các bài toán số học tổ hợp

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC Nguyễn Thị Hồng Huế VỀ CÁC BÀI TOÁN SỐ HỌC - TỔ HỢP Chuyên Ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP MÃ SỐ:60.46.01.13 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: GS.TSKH. Hà Huy Khoái Thái Nguyên - 2013 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ Công trình được hoàn thành tại Trường Đại Học Khoa Học - Đại Học Thái Nguyên Người hướng dẫn khoa học: GS.TSKH. Hà Huy Khoái Phản biện 1: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .................................................................... Phản biện 2: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .................................................................... Luận văn sẽ được bảo vệ trước hội đồng chấm luận văn họp tại: Trường Đại Học Khoa Học - Đại Học Thái Nguyên Ngày .... tháng .... năm 2013 Có thể tìm hiểu tại Thư Viện Đại Học Thái Nguyên Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 1 Mục lục Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Chương 1. Tỷ số vàng 1.1. Sơ lược về tỷ số vàng . . . . . . . . . . . . . . . . . . 1.2. Các bài toán . . . . . . . . . . . . . . . . . . . . . . . . 4 4 9 Chương 2. Các dãy nhị phân 2.1. Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Các bài toán . . . . . . . . . . . . . . . . . . . . . . . . 14 14 14 Chương 3. 3.1. Bài 3.2. Bài 3.3. Bài 3.4. Bài 3.5. Bài 3.6. Bài 18 18 19 20 21 23 23 Tính chia toán 3.1.1 toán 3.1.2 toán 3.1.3 toán 3.1.4 toán 3.1.5 toán 3.1.6 hết . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chương 4. Trò chơi 4.1. Sơ lược về Lý thuyết trò chơi . . . . . . . . . . 4.1.1. Khái niêm về Lý thuyết trò chơi . . . . 4.1.2. Biểu diễn trò chơi . . . . . . . . . . . . . 4.2. Các bài toán về số học - tổ hợp có liên quan trò chơi . . . . . . . . . . . . . . . . . . . . . . . . Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . Soá hoùa bôûi trung taâm hoïc lieäu . . . . . . . . . . . . . . . . . . . . . . . . . . . đến . . . . . . 25 25 25 25 27 34 http://www.lrc.tnu.edu.vn/ 2 Mở đầu Các bài toán số học tổ hợp từ lâu đóng một vai trò quan trọng trong việc rèn luyện tư duy toán học và kỹ năng giải toán. Bài toán số học tổ hợp có một số đặc điểm quan trọng mang tính khác biệt sau: + Có thể giảng dạy tại các bậc, lớp khác nhau. + Không có khuôn mẫu nhất định cho việc giải (Không giống như việc giải phương trình, khảo sát hàm số, tính tích phân...). Do vậy đòi hỏi sự sáng tạo từ phía học sinh. + Thường phải phát biểu bằng lời văn, đòi hỏi học sinh phải có kỹ năng đọc hiểu và rút tích thông tin, biết cách biểu đạt bằng ngôn ngữ toán học. Bài toán số học tổ hợp thường mang tính thực tế và thẩm mỹ cao khiến học sinh yêu thích, ghi nhớ. Tuy nhiên khi nói "các bài toán thuộc loại Số học - Tổ hợp" thì thực ra không có một " định nghĩa" nào cho loại bài toán đó. Vì thế ở đây chỉ giới hạn ở việc đưa ra một số ví dụ về loại bài toán thường gặp trong các kỳ thi học sinh giỏi các cấp. Cuốn luận văn này được trình bày gồm bốn chương: Chương 1: Tỷ số vàng Chương 2: Các dãy nhị phân Chương3: Tính chia hết Chương4: Trò chơi Trong khi trình bày lời giải, chúng tôi cố gắng mô tả quá trình hình thành nên lời giải đó hơn là đưa ra một lời giải ngắn gọn. Luận văn này được hoàn thành với sự hướng dẫn và chỉ bảo tận tình Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 3 của GS.TSKH Hà Huy Khoái - Viện Toán Học Hà Nội. Từ đáy lòng mình, em xin được bày tỏ lòng biết ơn sâu sắc đối với sự quan tâm, động viên và sự chỉ bảo hướng dẫn của thầy. Em xin trân trọng cảm ơn tới các Thầy Cô trong Trường Đại Học Khoa Học - Đại Học Thái Nguyên, phòng Đào Tạo Trường Đại Học Khoa Học. Đồng thời tôi xin gửi lời cảm ơn tới tập thể lớp Cao Học Toán K5c Trường Đại Học Khoa Học đã động viên giúp đỡ tôi trong quá trình học tập và làm luận văn này. Tôi xin cảm ơn tới Sở Giáo dục - Đào tạo Tỉnh Bắc Ninh, Ban Giám Hiệu, các đồng nghiệp Trường THPT Lý Thường Kiệt - Thành phố Bắc Ninh đã tạo điều kiện cho tôi học tập và hoàn thành kế hoạch học tập. Thái Nguyên, ngày ...tháng ... năm 2013 Tác giả Nguyễn Thị Hồng Huế Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 4 Chương 1 Tỷ số vàng 1.1. Sơ lược về tỷ số vàng Tỷ số vàng φ là tỷ số mà khi chia đoạn thẳng thành hai phần a và b sao cho tỷ số giữa cả hai đoạn thẳng (a + b) và đoạn lớn a bằng tỷ số giữa đoạn lớn a và đoạn nhỏ b. Tức là: a+b a = a b Ta qui độ dài a + b về đơn vị 1. Gọi độ dài đoạn lớn là x, đoạn bé là 1 − x. Ta được: √ 1 x −1 + 5 φ= = ⇔ x2 + x − 1 = 0 ⇔ x = x 1−x 2 √ 1 1 1+ 5 √ = φ= = ≈ 1, 6180339887... x 2 −1 + 5 2 * Hình chữ nhật vàng: Là hình chữ nhật có tỷ số giữa chiều dài và chiều rộng bằng φ. * Đường xoắn ốc lôgarít tiếp xúc trong với các cạnh của một chuỗi các hình chữ nhật vàng được gọi là Đường xoắn ốc vàng Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 5 - Tỷ lệ vàng được áp dụng trong nghệ thuật mang đến cho con người một cảm giác đẹp hài hòa và dễ chịu một cách khó giải thích. Do đó, nó nó được giảng trong các môn học như nghệ thuật, kiến trúc, mỹ thuật, trang trí, hội họa, điêu khắc, nhiếp ảnh vv...như là một quy luật tương hợp kỳ lạ với óc thẩm mỹ của con người. Trong tự nhiên: hình ảnh các đường xoắn ốc vàng được sắp xếp ở nhị hoa của hoa hướng dương tạo cảm giác rất đẹp mắt. Trong kiến trúc Tỷ lệ vàng đã được áp dụng trong các kích thước kiến trúc của các công trình nổi tiếng như đền Parthenon Hi lạp, các kim tự tháp Giza. “Hình chữ nhật vàng” trong thiết kế đền thờ Parthenon tại Hy Lạp: Tại Toronto, Canada là tòa tháp cao nhất thế giới, cũng được thiết kế theo tỉ lệ vàng. Tỉ số giữa tổng chiều cao tháp so với độ cao của đài quan sát là: 553, 33m : 342m = 1, 618 = φ Trong nghệ thuật: Với thiếu nữ bên hoa huệ của Tô Ngọc Vân, ta có thể vạch một đường Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 6 cong tự nhiên theo cơ thể cô gái và qua các điểm: một ở nhụy bông hoa bên phải, một ở đài nụ cong xuống, một ở đầu ngón tay phải và điểm cuối cùng ở trung tâm bố cục có ý nghĩa nhất bức tranh: nhụy bông hoa ở giữa. Đó là đường xoắn ốc vàng. Chính bố cục xoắn ốc vàng tạo nên hiệu quả thẩm mỹ của tác phẩm Mona Lisa. Tỷ số vàng cũng đã được áp dụng thành công trong nhiều tác phẩm hội họa. Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 7 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 8 Xuất hiện trong nhiếp ảnh, tỷ số vàng- hằng số chi phối hầu như mọi thiết kế của tự nhiên nói chung và các sinh thể nói riêng, tạo ra vẻ đẹp hài hòa. Tỷ lệ vàng là một khuỗn mẫu đã đi vào sách vở và vẫn được giảng dạy cho đến ngày nay, do đó việc người ta áp dụng nó trong nhiếp ảnh là môt điều dễ hiểu. Và trong hình học thật ngạc nhiên "tỷ số vàng" cũng xuất hiện .Ví dụ là tỷ số giữa cạnh của 1 ngũ giác đều với đường chéo của ngũ giác đều đó. Nếu chúng ta vẽ vào đó tất cả các đường chéo của ngũ giác thì mỗi đường chéo cắt đường chéo cắt đường chéo khác theo "tỷ số vàng"như hình vẽ. Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 9 Đặc biệt "tỷ số vàng "còn xuất hiện trong các bài toán số học và tổ hợp. 1.2. Các bài toán Bàitoán 1.2.1 Cho dãy số xác định bởi a0 = a1 = 1, an+2 = an+1 + an (n ≥ 0). Tìm công thức xác định an theo n Lời giải: Xét phương √ trình đặc trưng: √ 1 + 5 1 − 5 t2 = t + 1 ⇔ t1 = ; t2 = . 2 2 an = u.tn1 + v.tn2 , n ≥ 0, u, v =? Xác định u,v : 1 = a0 = u.t01 + v.t02 = u + v √ √ 1+ 5 1− 5 1 = a1 = u.t1 + v.t2 = u( ) + v( ) 2 2 Ta có hệ phương trình:  u+v = p1 √ u(1 + 5) + v(1 − 5) = 2  u+v =1 ⇔ √ 5(u − v) = 1 √  1 + 5   u= √ 2 5√ ⇔  −1 + 5  v= √ 2 5 Vậy: √ √ √ √ 1+ 5 1+ 5 n 1− 5 1− 5 n an = √ ( ) − √ ( ) 2 2 2 5 2 5 √ n+1 √ n+1 1+ 5 1− 5 ( ) −( ) 2 2 √ an = . 5 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 10 . Bài toán 1.2.2: Gia sử γ, δ là những số vô tỷ dương, thỏa mãn: 1 1 + = 1. γ δ Chứng minh rằng nếu đặt:an = [nγ] , bn = [nδ] thì mỗi số nguyên dương xuất hiện đúng một lần trong một trong hai dãy an, bn . Rõ ràng yêu cầu của bài toán tương đương với việc chứng minh rằng các số trong mỗi đoạn hữu hạn tùy ý [1, 2, ...N ] có mặt ở một trong hai dãy, và xuất hiện đúng một lần. Như vậy vấn đề chỉ còn là đếm xem trong N-1 số nguyên dương nhỏ hơn N, có bao nhiêu số thuộc một trong hai dãy nói trên. N Lời giải: Xét mọi số nguyên dương n thỏa mãn [nγ] < N , tức là n < γ   N Như vậy, các số n thỏa mãn là n = 1, 2, ... . Tương tự như vậy, các γ   N số m sao cho [mδ] < N là m = 1, 2, ..., δ Như vậy, trong số các số nhỏ hơn N, số các số thuộc một  nguyên   dương  N N trong hai dãy an , bn là + . γ δ     N N Do γ, δ là các số vô tỷ nên ; thuộc Z. γ δ Từ đó ta có:   N N N −1< < , γ γ γ   N N N −1< < δ δ δ Suy ra:     1 1 N N 1 1 N( + ) − 2 = N − 2 < + < N ( + ) = N. γ δ γ δ γ δ Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 11 Do đó     N N + =N −1 γ δ Do đó trong N − 1 số nhỏ hơn N có đúng N − 1 số thuộc một trong hai dãy đang xét. Vậy ta có điều phải chứng minh. Bài toán 1.2.3 Tìm các dãy số nguyên dương {an } , {bn } thỏa mãn những tính chất sau: 1) a1 = 1. 2) Với mọi n ≥ 1, bn = an + n. 3) an là số nguyên dương nhỏ nhất không thuộc tập hợp {a1 , a2 , ...an−1 ; b1 , b2 , ..., bn−1 } . Lời giải: Rõ ràng ba điều kiện nói trên xác định một cách duy nhất các dãy {an } , {bn } Hơn nữa, đối với hai dãy tăng, việc thỏa mãn các điều kiện 1),2),3),tương đương với việc thỏa mãn các điều kiện 1),2) và 3’) như sau: 3’) Mỗi số nguyên dương đều thuộc một trong hai dãy đang xét. Do tính xác định duy nhất của các dãy thỏa mãn 1), 2), 3’) ta chỉ cần chứng minh sự tồn tại, bằng cách chỉ ra ví dụ cụ thể. Bài toán 1 cho ta tìm hai dãy thỏa mãn điều kiện 3’) đó chính là các dãy an = [nγ] , bn = [nδ] trong đó γ, δ là những số vô tỷ dương thỏa mãn: 1 1 + = 1. γ δ Vấn đề chỉ là tìm γ để các điều kiện 1) và 2)được thỏa mãn. Để ý rằng: n = n + [nγ] − [nγ] = [n + nγ] − [nγ] = [(1 + γ)n] − [nγ] Như vậy chỉ cần chọn γ vô tỷ, thỏa mãn: 1 1 + = 1. γ γ+1 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 12 √ 1+ 5 Nghiệm của phương trình trên là "tỷ số vàng" 2 Các dãy an , bn là: " " √ # √ # 1+ 5 1+3 5 an = n ; bn = n . 2 2 Bài sau đây có thể xem là "tổng hợp" của những bài toán trên, và là một bài tập khó: Bài toán 1.2.4 Lập dãy số theo cách sau: lấy x1 = 1, với i ≥ 2 số xi nhận được từ xi−1 bằng cách đổi ( trong cách viết số xi−1 ) số 1 thành số 01, số 0 thành số 1. Làm như vậy, ta được dãy số 1,01,101,01101,...Trong dãy này, gọi an là vị trí của chữ số 1 thứ n, bn là vị trí của chữ số 0 thứ n (như vậy a1 = 1, a2 = 3, a3 = 4, b1 = 2, b2 = 5, ...). Tìm công thức xác định an , bn . Lời giải: Trước tiên ta cần tìm một công thức xác định mối liên hệ giữa an , bn Gọi kn là số chữ số 0 đứng trước chữ số 1thứ n. Theo định nghĩa hai dãy đang xét ta có: an = n + kn Theo bài ra, chữ số 0 thứ n được "sinh ra" từ chữ số 1 thứ n. Mặt khác, chữ số 1"biến thành" hai chữ số 01, chữ số 0"biến thành" một chữ số 1. Trước chữ số 1thứ n có kn chữ số 0 và"biến thành" kn chữ số; còn n chữ số 1 "biến thành" 2n chữ số. Từ đó suy ra: bn = kn + 2n Từ hai công thức trên đây, ta có: b n = an + n Vì : an và bn đều là các "số thứ tự" nên hai dãy này là những dãy tăng, đồng thời mỗi một số nguyên dương xuất hiện đúng một lần trong một trong hai dãy. Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 13 Vậy theo các bài toán 1.2.2 và bài toán 1.2.3 cho ta đáp số: " " √ # √ # 1+ 5 1+3 5 an = n ; bn = n . 2 2 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 14 Chương 2 Các dãy nhị phân 2.1. Đặt vấn đề Trong rất nhiều bài toán tổ hợp, đặc biệt là các bài toán "đếm", chúng ta thường bắt gặp các tình huống mà tại đó có hai khả năng xảy ra, chẳng hạn như: có thể tô bởi hai màu; học sinh nam hay học sinh nữ; số chẵn hay số lẻ...Nhìn chung về thực chất, những bài toán kiểu như vậy luôn luôn có thể đưa về cùng một dạng phát biểu, trong đó thông thường nhất là các dãy nhị phân ( dãy gồm hai chữ số 0 và 1) Để hiểu rõ hơn về điều đó, ta xét các bài toán sau đây: 2.2. Các bài toán Bài toán 2.2.1 Sau giờ tan học, các em học sinh xếp hàng để nhận xe đạp ở nhà để xe. Giá tiền gửi mỗi xe là 1000 đồng. Giả sử có k em học sinh có tờ 1000 đồng, m em có tờ 2000 đồng. Hỏi có bao nhiêu cách xếp hàng lấy xe sao cho không em nào phải chờ lấy tiền trả lại (với giả thiết người trông xe không có đồng tiền lẻ nào). Lời giải: Đây là một bài toán thuộc loại "hai khả năng": mỗi em học sinh hoặc có tờ 1000 đồng, hoặc có tờ 2000 đồng, Như vậy, để dễ thấy bản chất của bài toán, ta có thể lập tương ứng mỗi hàng học sinh với một dãy gồm hai chữ số 0,1. Giả sử ứng với mỗi học sinh có tờ 1000 đồng trong hàng, ta viết chữ số 0; ứng với học sinh có tờ 2000 đồng, ta viết số 1. Như vậy, mỗi hàng học sinh tương ứng một dãy gồm k chữ số 0, m chữ số 1. Để tồn tại cách xếp hàng mà không có em nào phải chờ lấy tiền trả lại, điều kiện là k ≥ m. Cũng tương tự như nhiều bài toán khác, khi việc đếm số phần tử thỏa mãn bài ra là khó, ta đếm "phần bù" của nó, tức là phần tử không thỏa mãn bài ra. Như vậy, ở đây ta sẽ xem xét có bao nhiêu hàng mà có học Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 15 sinh nào đó đến lượt mình phải chờ lấy tiền trả lại. Theo cách tưng ứng của chúng ta, một hàng như vậy sẽ tương ứng một- một với một dãy gồm k số 0, m số 1, trong đó tồn tại vị trí 2s+1 sao cho tại đó có số 1, đồng thời ở 2s vị trí đầu, số số 0 và số số 1 là như nhau. Ta gọi một hàng như vậy là " hàng xấu". Nếu ta đổi số 0 thành số 1, số 1 thành số 0 ở 2s+2 vị trí đầu, một hàng như trên sẽ tương ứng với một hàng gồm k+1 chứ số 0, m chữ số 1, nhưng với số 1 đứng đầu tiên. Lại bỏ đi số 1 đầu tiên này, ta được một hàng gồm k+1 chữ số 0, m-1 chữ số 1. Như vậy, mỗi hàng xấu gồm k chữ số 0, m chữ số 1sẽ được tương ứng với một hàng gồm k+1 chữ số 0, m-1 chữ số 1 theo cách trên đây. Dễ thấy rằng, tương ứng trên là một -một. Thật vậy, xét một hàng tùy ý gồm k+1 chữsố 0, m chữ số 1. Do điều kiện k ≥ m nên trong hàng này phải tồn tại vị trí (2s+2) mà từ đó trở lên, số số 0 bằng số số 1. Ta đổi số 0 thành số 1 và ngược lại ở các vị trí từ đó trở lên, để được hàng gồm k+1 chữ số 0, m chữ số 1, với số 0 đứng đầu. Bỏ số 0 đầu tiên này, ta nhận được một hàng xấu. Từ những tương ứng trên suy ra rằng, số các hàng xấu gồm k chữ số 0, m chữ số 1 bằng số các hàng (tùy ý) với k+1 chữ số 0, m-1 chữ số 1, tức là bằng Ck+1 m+k Như vậy, số cách xếp hàng sao cho không học sinh nào phải chờ lấy tiền trả lại là: Ckm+k − Ck+1 m+k . Bài toán 2.2.2 Có 2k học sinh chiều cao khác nhau đôi một. Người ta muốn xếp họ thành hai hàng ngang, sao cho trong mỗi hàng, chiều cao của học sinh giảm dần và ở mỗi vị trí, em đứng hàng trước cao hơn em đứng hàng sau. Hỏi có bao nhiêu cách xếp hàng thỏa mãn yêu cầu? Lời giải: Ta nhận thấy nếu mới đọc đầu bài thì đây là bài toán khác hẳn với bài toán trên. Tuy nhiên, nếu để ý kỹ và nắm chắc nguyên tắc "hai khả năng" thì đây là bài toán cùng loại với bài toán trên. Thật vậy, chỉ cần xếp học sinh vào một trong hai hàng. Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 16 Với cách suy luận như trên, ta cho mỗi em đứng hàng trước cầm một tấm biển ghi số "0", mỗi em hàng sau cầm tấm biển ghi số "1". Sau đó gọi tất cả 2k em xếp lại thành một hàng dọc theo thứ tự chiều cao giảm dần. Làm như vậy, ta được một dãy gồm k chữ số 0, k chữ số 1. Dễ thấy rằng, một cách xếp hàng thỏa mãn bài ra chính là một cách xếp hàng sao cho tại mỗi vị trí 2s+1, số số 0 từ vị trí đầu tiên đến đó phải ≥ s + 1. Theo bài toán 2.2.1, số cách xếp hàng thỏa mãn bài toán là: Ck2k − Ck+1 2k = (2k)! . k!(k + 1)! Bài toán 2.2.3 Tìm bộ 3 số nguyên dương (x, y, z) thỏa mãn đẳng thức : x + y + z = 100. (1) Lời giải: Mỗi bộ số nguyên dương (x ;y; z) thỏa mãn (1) ta đặt tương ứng với một dãy: ! 11...1 | {z } 0 |11...1 {z } 0 |11...1 {z } x y z Để có một bộ số như trên ta cần chọn 2 vị trí không kề nhau trong 102 vị trí để đặt 2 số không, còn lại đặt số một. Hai vị trí cần tìm tương ứng với 2 số a,b thỏa mãn 3 ≤ a + 1 < b ≤ 101 (Vì 2 số 0 không thể đứng đầu và cuối) Như vậy số bộ số thỏa mãn yêu cầu của bài toán bằng số cách chọn 2 số 2 phân biệt trong 99 số từ 3 đến 101. Vậy có C99 bộ số thỏa mãn yêu cầu bài toán. Bài toán 2.2.4 Có bao nhiêu cách phát 5 viên bi đen, 7 viên bi đỏ cho 3 học sinh. Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 17 Lời giải: Ta phát 5 viên bi đen cho 3 học sinh. Gọi C1 là số viên bi đen phát cho học sinh thứ 1, C2 là số viên phát cho học thứ 2, C3 là số viên phát cho học sinh thứ 3. Ta có : C1 + C2 + C3 = 5(Ci ≥ 0) Mỗi cách phát là một bộ 3 số (C1 ; C2 ; C3 ) thỏa mãn tính chất trên ta đặt tương ứng với những dãy nhị phân như sau: (11...1 | {z } 0 |11...1 {z } 0 |11...1 {z }) c1 c2 c3 Nếu Ci = 0 ta không viết số nào. Bộ các số 0,1 trên gồm : p = C1 + 1 + C2 + 1 + C3 = C1 + C2 + C3 + 2 = 7 Để có 1 bộ số như vậy ta cần chọn 2 vị trí trong 7 vị trí để đặt số 0. Suy ra số cách phát là :C72 . Tương tự số cách phát 7 viên bi đỏ cho 3 học sinh là:C92 . Vậy theo qui tắc nhân thì số cách phát 5 bi đen và 7 bi đỏ cho 3 học sinh là:C72 .C92 . Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 18 Chương 3 Tính chia hết Đầu tiên ta bắt đầu bằng bài toán đơn giản sau đây: 3.1. Bài toán 3.1.1 Tìm tất cả các tập hợp A = {a1 , a2 , a3 . . . an ; n > 2012} gồm những số nguyên và có tính chất sau: 2012∈ A, đồng thời mỗi tập con tùy ý gồm 2012 số thuộc A đều có thể chia thành 4 nhóm có số phần tử bằng nhau và tổng các phần tử trong mỗi nhóm bằng nhau. Lời giải: Điều kiện của bài toán cho ta thấy rằng, tổng của 2012 số tùy ý thuộc A là một số chia hết cho 4. Mặt khác, nếu thay trong tập hợp 2012 phần tử nào đó một phần tử bất kỳ bởi một phần tử khác tùy ý không thuộc tập đã chọn, theo giả thiết, tính chất tổng chia hết cho 4 không hề thay đổi. Như vậy có thể thấy ngay rằng, mọi phần tử thuộc A đều đồng dư nhau modulo 4. Dĩ nhiên ta nảy ra ngay dự đoán rằng, các phần tử của A đều bằng nhau. Để có thể kiểm chứng dự đoán này, ta xét phần tử nhỏ nhất của A: a. Khi đó tập hợp B = {a1− a, a2 − a, . . . an − a} rõ ràng cũng thỏa mãn những tính chất nêu trong bài toán như đối với tợp hợp A. Do đó, mọi phần tử của B cũng đồng dư nhau modulo 4, và vì B chứa phần tử bằng 0 nên suy ra mọi phần tử của B đều chia hết cho 4. Từ đây, suy luận "quy nạp lùi" quen thuộc cho ta lời giải: Tập hợp b nhận được từ B bằng cách thay mọi phần tử b∈ B bởi cũng có tính 4 chất nêu trong bài ra; và do đó các phần tử của tập hợp này cũng chia hết cho 4. Tiếp tục quá trình, dễ ràng suy ra mọi phần tử của B đều bằng 0. Như vậy, mọi số thuộc A đều bằng 2012. Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/