mở đầu: Có bao nhiêu cách xếp 4 viên bi giống nhau vào 3 hộp khác nhau. Lời giải Ở bài toán bày chúng ta có thể liệt kê các trường hợp có thể xảy ra. Gọi số viên bi xếp vào hộp 1, hộp 2, hộp 3, lần lượt là x, y, z. Các trường hợp có thể xảy ra ñối với (x, y, z) là: (4; 0; 0)(0; 4; 0), (0; 0; 4), (1; 1; 2), (1; 2; 1), (2; 1; 1), (1; 3; 0), (1; 0; 3), (0; 1; 3), (0; 3; 1), (3; 0; 1), (3; 1; 0), (0; 2; 2), (2; 2; 0), (2; 0; 2).
Vậy có 15 cách xếp. Nhận xét: Với bài toán này có thể liệt kê tất cả các trường hợp, nhưng với những bài toán tương tự như thế nhưng số bi và số hộp lớn hơn rất nhiều thì chúng ta sẽ gặp nhiều khó khăn trong việc liệt kê. Vậy có một phương pháp nào giúp chúng ta giải những bài toán như thế đơn giản hơn không? “Tổ hợp lặp – Chỉnh hợp lặp”, chúng sẽ giúp chúng ta giải các bài toán phức tạp một cách dễ dàng hơn. Biển đăng kí ô tô có 6 chữ số và 2 chữ cái đầu tiên trong 26 chữ cái (không dùng chữ O và I ).
Hỏi số ô tô ñược đăng kí nhiều nhất là bao nhiêu? Lời giải Gọi X là tập hợp các chữ cái dùng trong bảng đăng kí, suy ra X có 24 phần tử (vì không dùng O và I). Vì vậy ta có A¯2 = 242 cách chọn cho hai chữ cái đầu tiên. 24 Gọi Y là tập hợp các chữ số dùng trong bảng đăng kí, suy ra Y có 10 phần tử. Vì vậy có A¯6 = 106 cách chọn cho 6 chữ số còn lại.
10 Do đó có tất cả 242. Hỏi có bao nhiêu số có 10 chữ số mà 3 chữ số đầu và 3 chữ số cuối tương ứng giống nhau? Lời giải 21 Ta thấy với 1 cách chọn cho 3 chữ số đầu cũng chỉ có 1 cách chọn cho 3 chữ số cuối để chúng tương ứng giống nhau. Ta có A¯3 = 103 cách chọn tùy ý cho 3 chữ số đầu. Ta phải loại trường hợp số 0 10 đứng đầu, suy ra có A¯210 = 102 cách bị loại.
Như vậy ta có A¯3 − A¯2 = 900 cách chọn cho 3 chữ số đầu. 10 10 Nên ta có 900 cách chọn cho 3 chữ số đầu và 3 chữ số cuối tương ứng giống nhau. Ta còn lại 4 ô trống, mà từ 4 ô trống đó ta lập được A¯4 = 104 = 10000. Giả sử có n viên bi giống nhau và m cái hộp, ta xếp bi vào các hộp.
Gọi xi với i = 1, 2, 3., m là số bi ở hộp i. Chứng minh rằng m+n−1 a) Số cách xếp khác nhau n viên bi vào m cái hộp là . n m+n−1 m−1 b) Trong cách xếp đó có cách xếp cho tất cả các hộp n n−1 đều có bi. Lời giải a) Ta biểu diễn m cái hộp từ m + 1 gạch thẳng đứng, còn các viên bi biểu diễn bằng các ngôi sao (*).
Chẳng hạn như | ∗ ∗| ∗ | ∗ ∗ ∗ | ∗ |. Như vậy ở ngoài cùng luôn luôn là các vạch thẳng đứng, còn lại m − 1 vạch thẳng đứng và n viên bi được sắp xếp theo thứ tự tùy ý. n phần tử Như vậy số cách sắp xếp khác nhau bằng số cách chọn trong tập hợp m+n−1 m − 1 + n phần tử (cả vạch và ngôi sao) đó chính là . n b) Trường hợp mỗi hộp có ít nhất 1 viên bi tương ứng với cách biểu diễn mỗi vạch phải bao gồm giữa hai ngôi sao.
Nhưng có tất cả n − 1 khoảng trống giữa n ngôi sao. Vì vậy phải xếp m − 1 vạch vào n − 1 khoảng trống đó. m−1 Vậy có tất cả cách xếp. Tìm số nghiệm nguyên không âm của phương trình x1 + x2 + x3 + x4 = 20 (1) thỏa điều kiện x1 ≤ 3; x2 ≥ 2; x3 > 4.
(*) Lời giải Ta viết điều kiện đã cho thành x1 ≤ 3; x2 ≥ 2; x3 ≥ 5. Xét các điều kiện sau x2 ≥ 2,; x3 ≥ 5 (**); x1 ≤ 4; x2 ≥ 2; x3 ≥ 5 (***). Gọi p, q, r lần lượt là các số nghiệm nguyên không âm của phương trình (1) thỏa các ñiều kiện (*), (**), (***). Ta có p = q − r đặt x1 = x1 ; x2 = x2 − 2; x3 = x3 − 5; x4 = x4 , kết hợp với (**), phương trình (1) trở thànhx1 + x2 + x3 + x4 = 13 (2).
Số nghiệm nguyên không âm của phương trình (1) thỏa điều kiện (**) bằng số nghiệm nguyên không âm của phương trình (2). 4 + 13 − 1 16 Theo hệ quả trên số nghiệm đó là C¯413 = = . 13 4+9−1 12 Lý luận tương tự, ta có r = C¯49 = = . 13 9 Vậy số nghiệm nguyên không âm của phương trình (1) thỏa điều kiện (*) là 340.
Tìm số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1có nhất 5 bi, biết rằng hộp 2 và hộp 3 không chứa quá 6 bi. Lời giải Trước hết ta tìm số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 có ít nhất 5 bi. Nhận xét rằng ta cần lấy 5 bi để xếp trước vào hộp 1, do đó số bi còn lại là 25. Suy ra số cách xếp trong trường hợp này bằng số cách xếp 25 bi vào 5 hộp mà không có điều kiện gìthêm.
5 + 25 − 1 29 Số cách xếp đó là C¯525 = = = 23751. 25 25 23 Tương tự ta có, - Số cách xếp 30 viên bi giống nhau vào 5 hộp khácnhau sao cho hộp 1 chứa ít 5 + 18 − 1 22 nhất 5 bi, hộp chứa ít nhất 7 bi là C¯518 = = . 18 18 - Số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 chứa ít 5 + 18 − 1 22 nhất 5 bi, hộp 3 chứa ít nhất 7 bi là C¯518 = = . 18 18 - Số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 chứa ít 5 + 11 − 1 15 nhất 5 bi, mỗi hộp 2 và 3 chứa ít nhất 7 bi là C¯511 = = .
11 11 Sử dụng công thức |A ∪ B| = |A| + |B| − |A ∩ B suy ra số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 chứa ít nhất 5 bi, đồng thời hộp 2 hay hộp 3 chứa ít nhất 7 bi là 22 22 22 C¯518 + C¯518 − C¯511 = + − .(2) 18 18 18 Theo yêu cầu của bài toán, khi xếp 30 viên bi vào 5 hộp thì hộp 1 phải có ít nhất 5 bi còn mỗi hộp 2 và 3 phải có không quá 6 bi. Do đó số cách xếp này sẽ bằng hiệu của hai cách xếp 23751 − 13265 = 10486.3 Dạng toán đánh số Khi chọn các vị trí để sắp xếp các phần tử theo yêu cầu bài toán đặt ra phức tạp, ta nên đánh số các vị trí và thay thế mỗi cách chọn một bộ số tương ứng có tính chất tương ứng với các yêu cầu của bài toán. Việc tìm các bộ số có tính chất cho trước là hết sức đơn giản. Một tổ học sinh có 7 nam, 4 nữ.
Hỏi có bao nhiêu cách sắp xếp tổ thành một hàng ngang sao cho 2 em nữ không đứng cạnh nhau? Lời giải 24 Ta đánh số các vị trí từ 1 đến 11. Khi đó việc chọn 4 vị trí không kề nhau để sắp xếp các em nữ tương ứng với việc chọn 4 số a, b, c, d thỏa mãn tính chất sau 4 ≤ a + 3 < b + 2 < c + 1 < d ≤ 11. Để có bộ 4 số (a, b, c, d) thỏa mãn yêu cầu bài toán ta chỉ cần chọn 4 số phân biệt a + 3, b + 2, c + 1, d trong 8 số từ 4 đến 11. Số cách chọn bằng C84.
Suy ra có C84 cách chọn 4 vị trí không kề nhau để xếp các học sinh nữ. Ta có 4! cách xếp 4 nữ, 7! cách xếp 7 nam. Vậy số cách xếp là C84. Có 200 học sinh tham dự một kỳ thi Olympic Toán học.
Đề thi gồm 6 bài toán. Biết rằng mỗi bài toán có ít nhất 120 học sinh giải đúng. Chứng minh rằng có ít nhất 2 học sinh sao cho mỗi bài toán đều được ít nhất một trong hai học sinh này giải đúng. Lời giải Giả sử ngược lại, nghĩa là với mỗi cặp học sinh đều tồn tại ít nhất một bài toán nào đó mà cả hai học sinh này đều không giải được.
Đánh số thứ tự các bài toán là 1, 2, 3, 4, 5, 6 và số thứ tự các học sinh là 1, 2,. Xây dựng bảng (aij ) kích thước 6 × 200, với (aij ) = 1 nếu học sinh j giải được bài toán i và (aij ) = 0 nếu học sinh j không giải được bài toán i. Gọi T là tập các cặp số (0, 0) thuộc cùng một dòng của ma trận (aij ). Ta đếm số phần tử của T theo hai cách.
• Theo giả thiết, mỗi cặp cột có ít nhất một cặp số 0 thuộc cùng một dòng. Do 2 2 có tất cả C200 cặp cột nên |T | ≥ C200. • Do mỗi bài toán đều giải được bởi ít nhất 120 học sinh nên mỗi dòng có 2 2 nhiều nhất C80 cặp số 0. Điều này vô lí.
Người ta xếp tùy ý chúng thành các từ có 8 chữ cái (có lặp 25 lại) và sắp xếp chúng theo kiểu từ điển. Như vậy từ đầu tiên là AAAAAAAA và từ cuối cùng là NNNNNNNN. Hỏi từ đứng ở vị trí thứ tự 2017 là từ nào? Hỏi từ DHANDHAN đứng ở vị trí thứ tự bao nhiêu? Lời giải Ta sẽ sử dụng hệ đếm cơ số 4. Ta đánh số các chữ cái A, D, H, N tương ứng với các chữ số 0, 1, 2, 3.
Như vậy AAAAAAAA = 00000000(4) = 0 đứng ở vị trí đầu tiên (đánh số 0),. Lúc đó từ đứng ở vị trí thứ tự tự 2017 (đánh số 2016) với 2016 = 00133200(4) , nên từ đứng ở vị trí thứ tự 2017 là AADNNHAA.