Một số kiến thức cơ bản
Một số quy tắc cơ bản của phép đếm
Phép đếm đóng vai trò quan trọng trong cả đời sống và khoa học Hàng ngày, chúng ta thường xuyên sử dụng phép đếm để xác định số lượng các đối tượng xung quanh Tuy nhiên, trong các kỳ thi đại học và thi học sinh giỏi, bài toán đếm lại trở thành một thách thức lớn đối với nhiều thí sinh.
Trong phần này, chúng ta sẽ khám phá các quy tắc đếm cơ bản, giúp tính toán chính xác và nhanh chóng số lượng phần tử trong một tập hợp mà không cần phải đếm từng phần tử một cách trực tiếp.
A k là các tập hợp hữu hạn đôi một rời nhau, tức là
1 2 k 1 2 k với A i là số phần tử của tập hợp A , i 1, 2, 3, , k.
A k là các tập hợp hữu hạn và A A A là tích
Descartes của các tập đó thì
Quy tắc cộng và quy tắc nhân cũng thường được phát biểu dưới dạng tương ứng dưới đây:
Quy tắc cộng: Giả sử một công việc nào đó có thể thực hiện theo một trong k i
A , A , , A Phương án A có n i cách thực hiện
Khi đó công việc có thể thực hiện theo n n n cách.
Quy tắc nhân: Giả sử một công việc nào đó bao gồm k công đoạn A , A , , A Nếu
1 2 k công đoạn A có thể làm theo n cách Với mỗi i 2 và với mỗi cách thực hiện các công đoạn A , A , , A thì công đoạn A có thể thực hiện theo n cách Khi đó
1 2 i1 i i công việc có thể thực hiện theo n n n
1.1.3 Quy tắc bù trừ cách.
Cho X là tập hữu hạn và A X Gọi A X \ A Khi đó, ta có
1.1.4 Số phần tử của hợp hai hoặc ba tập hợp hữu hạn bất kì Định lí 1.1.1 (Công thức tính số phần tử của hợp hai tập hợp bất kì) Cho A và B là hai tập hợp hữu hạn bất kì Khi đó, ta có
Ta có B và A\ B là hai tập hợp không giao nhau và A B B A \ B
B và A \ B là hai tập hợp không giao nhau và
Định lý 1.1.2 cung cấp công thức tính số phần tử của hợp ba tập hợp hữu hạn A, B và C Theo đó, nếu thay (1.6) vào (1.5), ta sẽ nhận được kết quả (1.4).
Theo định lí 1.1.1 ta có
Mặt khác cũng theo định lí 1.1.1
Thay (1.9) và (1.10) vào (1.8) ta được công thức (1.7).
1.1.5 Ví dụ áp dụng một số quy tắc đếm cơ bản
Ví dụ 1.1.1 Từ ba chữ số 2, 3, 4 có thể tạo ra bao nhiêu số tự nhiên gồm năm chữ số, trong đó có đủ cả ba chữ số nói trên?
Gọi số cần tìm có dạng a 1 a 2 a 3 a 4 a 5 Bởi số tạo thành phải có đủ cả ba chữ số 2, 3, 4 nên ta xét các trường hợp sau:
Trường hợp 1: Số tạo thành gồm ba chữ số 2, một chữ số 3 và một chữ số
4 Ta xếp chữ số 4 có 5 cách chọn một trong các ví trí a
Có 4 vị trí để xếp chữ số 3 vào, tương ứng với 4 cách khác nhau Sau khi đã xếp chữ số 3, ba vị trí còn lại sẽ được lấp đầy bằng ba chữ số 2, và chỉ có 1 cách để thực hiện điều này Áp dụng quy tắc nhân, ta tính được tổng số cách xếp là 5 x 4 x 1 = 20 số.
Trường hợp 2: Số tạo thành gồm ba chữ số 4, một chữ số 2 và một chữ số 3.
Tương tự trường hợp 1 có 20 số.
Trường hợp 3: Số tạo thành gồm ba chữ số 3, một chữ số 2 và một chữ số
4 Tương tự, ta có 20 số.
Trường hợp 4: Số tạo thành gồm hai chữ số 2, hai chữ số 3 và một chữ số 4.
Có năm vị trí để xếp chữ số 4, cho phép thực hiện theo 5 cách khác nhau Sau đó, từ bốn vị trí còn lại, ta chọn hai vị trí để xếp hai chữ số 2, có 6 cách thực hiện Cuối cùng, hai chữ số 3 sẽ được xếp vào hai vị trí còn lại chỉ có 1 cách Theo quy tắc nhân, tổng số cách xếp là 5 x 6 x 1 = 30 số.
Trường hợp 5: Số tạo thành gồm hai chữ số 2, hai chữ số 4 và một chữ số 3.
Tương tự trường hợp 4 có 30 số.
Trường hợp 6: Số tạo thành gồm hai chữ số 3, hai chữ số 4 và một chữ số 2.
Tương tự, ta có 30 số.
Vậy theo quy tắc cộng có tất cả 20 + 20 + 20 +30 + 30 +30 = 150 số.
Trong đề thi tuyển sinh ĐHQG TP HCM năm 1999, có một bàn dài với hai dãy ghế đối diện nhau, mỗi dãy có 6 ghế Nhiệm vụ là sắp xếp chỗ ngồi cho 6 học sinh trường A và 6 học sinh trường B trên bàn này Câu hỏi đặt ra là có bao nhiêu cách xếp chỗ ngồi trong các trường hợp khác nhau.
Trong một lớp học, bất kỳ hai học sinh nào ngồi cạnh nhau hoặc đối diện nhau đều phải đến từ những trường khác nhau Điều này đảm bảo rằng không có hai học sinh nào ngồi đối diện nhau cùng thuộc một trường.
Lời giải Đánh số các ghế theo hình vẽ
(i) Theo yêu cầu của bài toán, ta có số cách chọn như sau:
Số cách xếp chỗ ngồi 12 6 5 5 4 4 3 3 2 2 1 1
Theo quy tắc nhân, ta có 12.6.5.5.4.4.3.3.2.2.1.1 = 1036800 cách.
(ii) Theo yêu cầu của bài toán, ta có số cách chọn như sau:
Số cách xếp chỗ ngồi 12 6 10 5 8 4 6 3 4 2 2 1
Theo quy tắc nhân, ta có 12.6.10.5.8.4.6.3.4.2.2.1 = 33177600 cách.
Ví dụ 1.1.3 Xét tập hợp X 1, 2, 3, , 2009 Đặt
(ii)Tìm số tập con B của X sao cho B A .
Để xác định số tập con B của tập X đáp ứng yêu cầu bài toán, chúng ta áp dụng quy tắc bù trừ Gọi P(X) là tập hợp tất cả các tập con của X, và M là tập hợp các tập con B của X sao cho B giao A không rỗng.
P X \ M là tập các tập con B của
X mà B A hay B X \ A Suy ra P(X ) \ M P X \ A Do đó
Trong một lớp học gồm 45 học sinh, kết quả điều tra về thành tích học tập các môn Toán, Lý và Hóa cho thấy có 19 học sinh không giỏi môn nào Cụ thể, 18 học sinh đạt thành tích tốt ở môn Toán, 17 học sinh giỏi môn Lý, 13 học sinh giỏi môn Hóa, và 10 học sinh xuất sắc ở cả hai môn Toán và Lý.
Lý, 9 học sinh giỏi cả hai môn Lý và Hóa, 10 học sinh giỏi hai môn Toán và Hóa. Hỏi bao nhiêu học sinh giỏi cả ba môn?
Kí hiệu T là tập hợp học sinh của lớp sinh giỏi Toán, Lý, Hóa của lớp đó.
A, B,C lần lượt là tập hợp các học
Vì A B C T \ T \ A B C nên số học sinh giỏi ít nhất một môn là
Suy ra số học sinh giỏi cả ba môn là
Vậy có tất cả 7 học sinh giỏi cả ba môn.
Nguyên lý Dirichlet
Nguyên lý Dirichlet mang tên nhà toán học người Đức, Peter Gustav
Dirichlet (1805 – 1859), được phát biểu hết sức đơn giản:
“Nếu nhốt n 1 con thỏ vào n cái lồng n * thì có một lồng chứa ít nhất hai con thỏ”.
Một cách tổng quát, ta có nguyên lý Dirichlet mở rộng:
“Nếu nhốt m con thỏ vào n cái lồng m,n N * thì luôn tồn tại một lồng
m 1 chứa ít nhất 1 con thỏ”.
được dùng để chỉ phần nguyên của số thực a
Sử dụng phương pháp phản chứng, ta có thể dễ dàng chứng minh được nguyên lý Dirichlet.
Nguyên lý Dirichlet, mặc dù được trình bày một cách đơn giản, lại có nhiều ứng dụng đa dạng và hiệu quả trong nhiều lĩnh vực khác nhau Trong các bài toán tổ hợp, nguyên lý này thường thể hiện rõ vai trò quan trọng của nó.
Ví dụ 1.2.1 Xét tập hợp M 1, 2, 3, , 9 Với mỗi tập con X của M , ta kí hiệu
S(X) là tổng tất cả các phần tử thuộc X Chứng minh rằng trong số 26 tập con X của M với X
3, luôn tồn tại hai tập A và B sao cho S A S B
Ta chia các tập con X của M thỏa mãn X 3 vào các lồng, mỗi lồng bao gồm các tập có cùng tổng các phần tử Do 0 S X
24 nên có 25 lồng Do có
26 tập X với X 3 nên tồn tại hai tập A, B thuộc cùng một lồng Điều đó có nghĩa là tồn tại hai tập minh.
S A S B Vậy ta có điều phải chứng
Trong một nhóm gồm 6 người, mỗi cặp người có thể là bạn hoặc thù của nhau Điều này dẫn đến việc tồn tại ít nhất một bộ ba người trong nhóm, trong đó hoặc tất cả đều là bạn của nhau, hoặc tất cả đều là kẻ thù của nhau.
Trong một nhóm gồm sáu người, nếu gọi A là một trong số đó, năm người còn lại sẽ được chia thành hai nhóm: bạn của A và thù của A Theo nguyên lý Dirichlet, với 5 người được chia thành 2 nhóm, có ít nhất 3 người sẽ là bạn hoặc thù của A.
Không mất tính tổng quát, gọi B,C , D là các bạn của A
Nếu B, C, D không ai là bạn của nhau, thì bộ ba cần tìm là B, C, D Ngược lại, nếu trong B, C, D có hai người là bạn của nhau, giả sử là B và C, thì bộ ba cần tìm sẽ là A, B, C, khi đó A, B, C là các bạn của nhau.
Nếu B,C , D là thù của A thì lập luận tương tự, chỉ cần thay đổi vị trí “bạn” và “thù”.
Như vậy bài toán được chứng minh.
Trong bài toán VMO 2004, cho tập A = {1, 2, 3, , 16}, cần xác định số nguyên dương k nhỏ nhất sao cho trong mọi tập con gồm k phần tử của A đều tồn tại hai số phân biệt a và b thỏa mãn điều kiện a^2 = b Việc tìm ra giá trị k này giúp hiểu rõ hơn về cấu trúc của các tập con và mối quan hệ giữa các số trong tập A.
b 2 là một số nguyên tố.
Nếu a và b đều là số chẵn, thì giao của a² và b², ký hiệu là A, sẽ có hai phần tử phân biệt a và b, và A chỉ chứa các số chẵn Từ đó, ta suy ra rằng k và 9 là hợp số Do đó, nếu tập con X là một số nguyên tố, thì X không thể là hợp số.
Giá trị nhỏ nhất k được chứng minh là 9, có nghĩa là trong mọi tập con X gồm 9 phần tử bất kỳ của A, luôn tồn tại hai phần tử phân biệt a và b sao cho a^2.
b 2 là một số nguyên tố. Để chứng minh khẳng định trên, ta chia tập A thành các cặp hai phần tử phân biệt a,b mà a2
b2 là một số nguyên tố Ta có 8 cặp gồm
Theo nguyên lý Dirichlet thì trong 9 phần tử của X có hai phần tử thuộc cùng một cặp và ta có điều phải chứng minh.
Ví dụ 1.2.4 Trên mặt phẳng có 17 điểm, không có 3 điểm nào thẳng hàng Cứ qua
2 điểm ta kẻ một đoạn thẳng và tô nó bằng một trong ba màu: Xanh, đỏ, vàng. Chứng minh tồn tại tam giác có 3 cạnh cùng màu.
Trong một bài toán với 17 điểm, nếu gọi A là một trong số đó, ta có 16 đoạn thẳng nối A với 16 điểm còn lại Theo nguyên lý Dirichlet, vì 16 = 5.3 + 1, nên sẽ tồn tại ít nhất 6 đoạn thẳng cùng màu, giả sử là màu xanh Đầu mút của 6 đoạn thẳng này được ký hiệu là B, C, D.
Nếu tồn tại 1 đoạn thẳng nối 2 trong 6 điểm trên là màu xanh thì bài toán được chứng minh.
Nếu tất cả các đoạn thẳng nối 2 trong 6 điểm trên không có đoạn nào màu xanh Xét 5 đoạn thẳng BC , BD, BE, BF, BG Do 5
2.2 nên tồn tại ít nhất 3 đoạn cùng màu; chẳng hạn BC , BD, BE cùng màu đỏ Nếu trong CD,CE, DE có một đoạn màu đỏ; chẳng hạn CD thì bài toán được chứng minh do tồn tại tam giác
BCD thỏa mãn Nếu CD,CE, DE đều màu vàng thì bài toán được chứng minh do tồn tại tam giác CDE thỏa mãn.
Hoán vị
1.3.1 Hoán vị không lặp Định nghĩa 1.3.1 Cho tập hợp A có n n 1 phần tử Mỗi cách sắp xếp n phần tử này theo một thứ tự nào đó (mỗi phần tử có mặt đúng một lần) được gọi là một hoán vị của n phần tử đã cho Kí hiệu số hoán vị của n phần tử bằng P Định lí 1.3.1 Số các hoán vị của n phần tử
Việc sắp xếp thứ tự n phần tử của tập hợp A bao gồm n công đoạn Trong công đoạn đầu tiên, có n cách để chọn phần tử cho vị trí thứ nhất Sau khi hoàn thành công đoạn này, công đoạn tiếp theo cho phép chọn phần tử cho vị trí thứ hai với n-1 cách thực hiện Tiếp tục như vậy, sau khi hoàn thành công đoạn i, sẽ có n-i cách để chọn phần tử cho vị trí tiếp theo.
1 phần tử của A vào các vị trí thứ 1, 2, , i 1 ), công đoạn thứ i tiếp theo là chọn phần tử xếp vào vị trí thứ i : Có n i 1 cách thực hiện.
Công đoạn cuối cùng trong quy trình thực hiện có một phương pháp cụ thể Theo quy tắc nhân, số cách xếp thứ tự n phần tử của tập hợp A được tính bằng n! (n giai thừa), tức là có tổng cộng n! hoán vị khác nhau.
Ví dụ 1.3.1 Có bao nhiêu hoán vị của n phần tử, trong đó hai phần tử đã cho không đứng cạnh nhau?
Để xác định số hoán vị với hai phần tử a và b đứng cạnh nhau, ta có n - 1 cách chọn vị trí cho chúng Bên cạnh đó, a và b có thể đổi chỗ cho nhau, tạo ra 2(n - 1) cách sắp đặt Với mỗi cách sắp đặt này, còn lại (n - 2)! hoán vị của các phần tử khác Do đó, tổng số hoán vị mà a và b đứng cạnh nhau được tính bằng 2(n - 1) × (n - 2)!.
Vì vậy số các hoán vị cần tìm bằng n ! 2.(n 1)! (n 1)!(n 2).
Có 5 thẻ trắng và 5 thẻ đen, mỗi loại được đánh dấu từ 1 đến 5 Câu hỏi đặt ra là có bao nhiêu cách sắp xếp các thẻ này thành một hàng ngang sao cho không có hai thẻ cùng màu nằm cạnh nhau.
Trong trường hợp đầu tiên, các thẻ trắng được sắp xếp ở các vị trí số lẻ, trong khi các thẻ đen được đặt ở các vị trí số chẵn Mỗi cách sắp xếp thẻ trắng tại các vị trí số lẻ tạo thành một hoán vị của 5 thẻ trắng, dẫn đến số lượng hoán vị có thể được tính toán.
P 5 ! cách sắp xếp các thẻ trắng Tương tự, ta cũng có P 5 ! cách sắp xếp các
5 5 thẻ đen ở vị trí số chẵn Vậy ta có 5 ! 5 ! cách sắp xếp 10 thẻ theo yêu cầu bài toán.
Trường hợp 2: Các thẻ trắng ở vị trí số chẵn, các thẻ đen ở vị trí số lẻ.
Tương tự như trường hợp 1 có 5 ! 5 ! cách xếp thỏa mãn yêu cầu bài toán.
Vậy ta có tất cả cầu bài toán.
Có 2 cách để sắp xếp 5 thẻ trắng và 5 thẻ đen theo định nghĩa hoán vị lặp Định nghĩa 1.3.2 cho biết hoán vị lặp là hoán vị trong đó mỗi phần tử xuất hiện ít nhất một lần Theo định lý 1.3.2, số hoán vị lặp của n phần tử thuộc k loại khác nhau, với các phần tử loại i giống hệt nhau, được ký hiệu là P.
n 1, n ,, n k và được tính bằng công thức
Nếu coi n phần tử này là khác nhau thì sẽ có n ! cách sắp xếp Trong mỗi cách sắp xếp như vậy, n phần tử loại 1 có thể hoán vị theo n 1
! cách, n phần tử loại 2 có thể hoán vị theo n ! cách, …, n cách. phần tử loại k có thể hoán vị theo n !
Do n i phần tử loại i i 1, 2, ,k là giống nhau nên số cách sắp xếp chỉ còn n ! n 1 !n 2 ! n k !
Ví dụ 1.3.3 Với sáu chữ số 0, 1, 2, 3, 4, 5 có thể lập được bao nhiêu số chia hết cho
Số cần lập gồm 11 chữ số với các tần suất xuất hiện như sau: chữ số 1 xuất hiện 4 lần, chữ số 2 3 lần, chữ số 3 2 lần, chữ số 4 1 lần, và tổng số lần xuất hiện của chữ số 0 và chữ số 5 là 1.
1 2 3 4 5 6 7 8 9 10 11 chia hết cho 5, thì x phải tận cùng là chữ số 0 hoặc chữ số 5.
Nếu tổng số lần xuất hiện của chữ số 0 và 5 trong x là 1, thì khi x kết thúc bằng 0, chữ số 5 sẽ không xuất hiện Ngược lại, nếu x kết thúc bằng 5, thì chữ số 0 sẽ không có mặt.
Bởi vậy a i 1 i 10 chỉ có thể là một trong những chữ số 1, 2, 3, 4 Bởi vậy, số khả năng lập phần đầu độ dài 10 a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a
Số hoán vị lặp của 10 phần tử thuộc bốn loại chữ số 1, 2, 3, 4, với 1 xuất hiện 4 lần, 2 xuất hiện 3 lần, 3 xuất hiện 2 lần và 4 xuất hiện 1 lần, sẽ được tính bằng P ∩ 1, 2, 3, 4 ∩ Thêm vào đó, a11 có thể nhận giá trị 0 hoặc 5, do đó, tổng số các số cần tìm sẽ được xác định dựa trên các yếu tố này.
Với các chữ số 0, 1, 2, 3, 4, 5, ta có thể tạo ra bao nhiêu số gồm 8 chữ số, trong đó chữ số 1 xuất hiện 3 lần và các chữ số khác (0, 2, 3, 4, 5) xuất hiện đúng 1 lần?
Số tất cả các số có 8 chữ số (kể cả số 0 đứng đầu) trong đó chữ số 1 lặp lại
3 lần, các chữ số khác có mặt đúng 1 lần là
Trong các số đã liệt kê, cần loại bỏ những số bắt đầu bằng chữ số 0, tức là các số chỉ có 7 chữ số Các số này có chữ số 1 xuất hiện 3 lần, trong khi các chữ số 2, 3, 4 và 5 mỗi chữ số chỉ xuất hiện một lần Số lượng các số thỏa mãn điều kiện này là
Vậy số các số thỏa mãn yêu cầu của bài toán là
Ví dụ 1.3.5 ( Ví dụ dẫn dắt ) Mời sáu người khách ngồi xung quanh một bàn tròn
Hỏi có bao nhiêu cách sắp xếp?
Khi mời một người vào một vị trí cụ thể, sẽ có 120 cách để sắp xếp 5 người còn lại vào 5 vị trí còn lại, tương ứng với 5! = 120 cách sắp xếp.
Vậy có tất cả 120 cách xếp sáu người ngồi xung quanh một bàn tròn.
Nhận xét 1.3.1: Số hoán vị vòng quanh của n phần tử khác nhau được tính bởi công thức
Có bao nhiêu cách sắp xếp cho 6 bạn nữ và 6 bạn nam ngồi vào 12 ghế xung quanh một bàn tròn, đảm bảo rằng không có hai bạn nữ nào ngồi cạnh nhau?
Xếp 6 ghế quanh một bàn tròn rồi xếp nam vào ngồi: Có 5! cách Giữa hai bạn nam có khoảng trống Xếp 6 bạn nữ vào trong 6 khoảng trống đó có 6! cách.
Theo quy tắc nhân, ta có 5! 6! 86400 cách xếp.
Ví dụ 1.3.7 Một hội nghị bàn tròn có phái đoàn các nước: Việt Nam có 3 người,
Chỉnh hợp
1.4.1 Chỉnh hợp không lặp Định nghĩa 1.4.1 Cho tập hợp A gồm n phần tử và số nguyên dương k với
Khi chọn ra k phần tử từ tập hợp A và sắp xếp chúng theo một thứ tự nhất định, ta tạo ra một chỉnh hợp chập k của n phần tử trong A.
A ) Số các chỉnh hợp chập k của tập hợp có n phần tử được kí hiệu là A k
Hoán vị của một tập hợp A với n phần tử được định nghĩa là một chỉnh hợp chập n của A Theo định lý 1.4.1, số lượng các chỉnh hợp chập k của tập A có n phần tử được tính theo công thức k! / (n-k)!.
Việc thiết lập một chỉnh hợp chập k từ tập A có n phần tử bao gồm k công đoạn Trong công đoạn đầu tiên, chúng ta có n cách để chọn phần tử cho vị trí thứ nhất Sau khi hoàn thành công đoạn đầu, công đoạn tiếp theo là chọn phần tử cho vị trí thứ hai, với số cách thực hiện phụ thuộc vào số phần tử còn lại trong tập.
1 cách thực hiện Sau khi thực hiện xong i
Trong quá trình sắp xếp các phần tử của tập hợp A, tại vị trí thứ 1, 2, , i-1, bước tiếp theo là chọn phần tử để xếp vào vị trí thứ i, với n-i+1 cách thực hiện Ở bước cuối cùng (bước k), có n-k+1 cách thực hiện Theo quy tắc nhân, tổng số cách sắp xếp được tính bằng n.
n 1 n k 1 cách lập một chỉnh hợp chập k của tập A có n phần tử, tức là có n n 1 n k 1 chỉnh hợp chập k của tập A có n phần tử.
Ví dụ 1.4.1 Cho mười chữ số 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 Có bao nhiêu số lẻ có sáu chữ số khác nhau nhỏ hơn 600000 tạo ra từ mười chữ số đã cho?
Để tạo ra một số lẻ có sáu chữ số khác nhau từ mười chữ số đã cho, số này phải có dạng a1 a2 a3 a4 a5 a6 Để đảm bảo số này nhỏ hơn 600000, yêu cầu đặt ra là 1 < a < 5, và cần xem xét hai trường hợp riêng biệt để hoàn thiện quá trình tạo số.
Vì vậy ta phải xét
Trong trường hợp 1, ta có 3 cách chọn a6 và 4 cách chọn a, cùng với 4 cách chọn 4 chữ số từ 8 chữ số còn lại để xếp vào 4 vị trí a Áp dụng quy tắc nhân, tổng số cách sắp xếp sẽ là 3 x 4 x A4, tương đương với 20,160 số.
Trường hợp 2: a 6 A 2 7, 9 Khi đó ta có 2 cách chọn a 6 , có 5 cách chọn a và A 4 cách chọn 4 chữ số từ 8 chữ số còn lại để xếp vào 4 vị trí a ,a ,a ,a
Theo quy tắc nhân, ta có 2.5 A 4 16800 số.
Vậy theo quy tắc cộng, ta có 20160 + 16800 = 36960 số.
Ví dụ 1.4.2 Từ các chữ số 1, 3, 5, 7 có thể lập được bao nhiêu số tự nhiên mà trong mỗi số này các chữ số không lặp lại?
Vì có bốn chữ số khác nhau, nên số dài nhất trong các số cần tìm cũng chỉ gồm 4 chữ số.
Ta lập các loại số tự nhiên dạng a a a Dùng S để kí hiệu tập số dạng
1 2 n 1 a , S để kí hiệu tập số dạng a a , S để kí hiệu tập số dạng a a a , S để kí hiệu
Mỗi số thuộc S là một chỉnh hợp chập 1 của 4 phần tử của tập
Tập S chứa các chỉnh hợp chập 2, 3 và 4 của 4 phần tử Mỗi số trong tập S tương ứng với một chỉnh hợp chập 3 và chập 4 của các phần tử trong tập này.
Vậy số các số thỏa mãn yêu cầu của đề bài bằng
1.4.2 Chỉnh hợp có lặp Định nghĩa 1.4.2 Cho tập hợp hữu hạn A gồm n n
1 phần tử Mỗi dãy có độ dài k k
Chỉnh hợp lặp chập k của n phần tử thuộc tập A là các phần tử của tập A có thể lặp lại nhiều lần và được sắp xếp theo một thứ tự nhất định Số lượng các chỉnh hợp lặp chập k này được ký hiệu theo định lý 1.4.2.
A k và được tính bởi công thức k n k (1.14)
Chứng minh gồm n phần tử phân biệt Dãy số có độ dài k là a a a Ta thấy a có n cách chọn từ n phần tử của tập A,a cũng có n cách
1 2 k 1 2 chọn (vì có thể giống a ), …, a cũng có n cách chọn Vậy dãy có độ dài k có n k cách chọn, hay A k n k
Ví dụ 1.4.3 Có thể lập được bao nhiêu biển số xe với hai chữ cái đầu thuộc tập
A, B,C, D, E , tiếp theo là một số nguyên dương gồm năm chữ số chia hết cho 5?
Giả sử một biển số xe có dạng XYabcde, trong đó X và Y có thể trùng nhau Do đó, XY được xem là một chỉnh hợp lặp chập 2 của 5 phần tử A, B, C, D, E Số cách chọn XY sẽ được tính bằng công thức A(2, 5) = 25.
Do a 0 , nên có 9 cách chọn a Vì abcde chia hết cho 5 nên e 0 hoặc e 5 , suy ra có 2 cách chọn chữ số e Do b,c,d có thể trùng nhau nên mỗi n
A số bcd là một chỉnh hợp lặp chập 3 của 10 chữ số 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 Bởi vậy số cách chọn bcd là A 3 10 3 1000
Vậy số biển số xe có thể thành lập theo yêu cầu đề bài là
Ví dụ 1.4.4 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?
Có 900 cách chọn 3 chữ số đầu, với điều kiện không có số 0 đứng đầu Đối với mỗi cách chọn 3 chữ số đầu, chỉ có một cách tương ứng chọn 3 chữ số cuối Tổng số cách chọn 3 chữ số đầu là 3 × 10^3, nhưng cần loại bỏ 2 trường hợp khi số 0 đứng đầu Do đó, số cách chọn hợp lệ cho 3 chữ số đầu là A3 ∩ A2 ∩ 900.
10 10 chữ số đầu và 3 chữ số cuối tương ứng giống nhau.
Còn lại 4 vị trí, mà từ 4 vị trí đó có A 4 10 4 cách chọn.
Tổ hợp
9000000 số cần tìm. Định nghĩa 1.5.1 Cho tập hợp A gồm n phần tử và số nguyên dương k với
Mỗi tập con có k phần tử của tập hợp A được gọi là một tổ hợp chập k của n phần tử của A, thường được viết tắt là tổ hợp chập k của A Số lượng các tổ hợp chập k của một tập hợp có n phần tử được ký hiệu là C_k Định lý 1.5.1 cho biết rằng số lượng các tổ hợp chập k của tập hợp n phần tử có thể được tính bằng một công thức cụ thể.
Mỗi hoán vị của một tổ hợp chập k của tập A tương ứng với một chỉnh hợp chập k của A Như vậy, từ một tổ hợp chập k của A, chúng ta có thể tạo ra k! hoán vị khác nhau.
A k chỉnh hợp chập k của A Vậy A k k !C k hay C k
Chú ý : Ta quy ước 0! = 1 và C 0 A 0 1.
Với quy ước đó thì định lí 1.4.1 và 1.5.1 đúng cho cả k 0 Định lí 1.5.2 (Hai tính chất
A cơ bản của số C k ) và k n
(i) Cho số nguyên dương n và số nguyên k với 0 k n Khi đó
(ii) (Hằng đẳng thức Pascal) Cho số nguyên dương n và số nguyên k với
(i)Suy ra từ công thức
Ví dụ 1.5.1 Cho đa giác đều k ! n k 1 ! n1
A A A ( n và n 2 ) nội tiếp trong đường tròn (O) Biết rằng số tam giác có đỉnh là 3 trong 2n đỉnh A , A , , A nhiều gấp
20 lần số hình chữ nhật có các đỉnh là 4 trong 2n đỉnh A , A , , A Tìm n ?
Số tam giác có các đỉnh là 3 trong 2n đỉnh A , A , , A là C
Đa giác đều với n đỉnh A1, A2, , An có n đường chéo lớn đi qua tâm của đường tròn O Mỗi hình chữ nhật được tạo thành từ 4 trong số 2n điểm A1, A2, , A2n sẽ có hai đường chéo lớn Điều này cho thấy mối liên hệ giữa số lượng đường chéo lớn và cấu trúc của đa giác đều.
Mỗi cặp đường chéo lớn trong một đa giác tạo thành 4 đỉnh của một hình chữ nhật Do đó, số lượng hình chữ nhật tương ứng với số cặp đường chéo lớn của đa giác đó.
Vậy n 8 là giá trị cần tìm.
Ví dụ 1.5.2 Một tập thể có 14 người trong đó có An và Bình Người ta muốn chọn
Trong một tổ công tác gồm 6 người, có thể chọn 1 tổ trưởng và 5 tổ viên với điều kiện là An và Bình không thể cùng có mặt trong tổ Để giải quyết bài toán này, ta cần tính số cách chọn tổ trưởng và tổ viên sao cho đáp ứng đầy đủ yêu cầu trên.
Số cách chọn 6 người từ 14 người, trong đó An và Bình không có mặt, được tính bằng cách chọn 6 người từ 14 người có C(6, 14) cách Nếu chọn An và Bình, ta cần chọn thêm 4 người từ 12 người còn lại, tương ứng với C(4, 12) cách Do đó, tổng số cách chọn 6 người mà không có An và Bình là C(6, 14) - C(4, 12).
Với 6 người đã chọn xong có 6 cách chọn ra 1 người làm tổ trưởng Vậy số cách thỏa mãn yêu cầu của bài toán là 6 C 6 C 4 62508 15048 cách.
1.5.2 Tổ hợp lặp Định nghĩa 1.5.2 Cho tập hợp A a 1,a 2 , ,a n Một tổ hợp lặp chập m
Số tổ hợp lặp chập m của n phần tử thuộc tập hợp A, ký hiệu là C_m, là một bộ gồm m phần tử, trong đó mỗi phần tử được chọn từ A Định lý 1.5.3 chỉ ra rằng số lượng tổ hợp lặp chập m của n phần tử trong tập hợp A có thể được tính theo công thức: \( C_m = \frac{n^m}{m!} \).
Xét tổ hợp có lặp chập m từ n phần tử, trong đó bao gồm k phần tử a Với mỗi bộ (k, k, , k), ta có thể tạo ra một dãy nhị phân bằng cách viết k số 1 liên tiếp, sau đó là một số 0, tiếp tục với k số 1, rồi lại là số 0, và lặp lại cho đến khi hoàn thành Dãy nhị phân này phản ánh cấu trúc của tổ hợp, giúp dễ dàng nhận diện các phần tử và số lượng của chúng trong tổ hợp.
Nếu một phần tử a nào đó không có mặt trong tổ hợp lặp, tức là k 0 , thì ta không viết nhóm chữ số 1 tương ứng Như vậy, mỗi bộ
(k 1 , k 2 , , k n ) được tương ứng với một dãy nhị phân có độ dài m n 1, trong đó có m chữ số 1 và n 1 chữ số 0 Rõ ràng phép tương ứng đó là một đơn ánh.
Ngược lại, với mỗi dãy m n 1 kí tự với m kí tự 1 và n
1 kí tự 0, khi ta đếm từ trái sang phải mà có: k số 1, số 0, k số 1, số 0, …, số 0 và k chữ số 1
1 2 n thì dãy số đó sẽ tương ứng với bộ (k , k , , k ) thỏa mãn k k k m
Chúng ta đã thiết lập một mối quan hệ song ánh giữa các tổ hợp lặp chập m của n phần tử và các dãy nhị phân có độ dài m, trong đó có m kí tự 1 và n - 1 kí tự 0 Do đó, số lượng tổ hợp lặp chập m của n phần tử tương đương với số lượng dãy nhị phân có độ dài m với m kí tự 1 và n - 1 kí tự 0.
Một dãy nhị phân có độ dài m + n + 1 với m ký tự 1 và n + 1 ký tự 0 tương ứng với việc chọn n + 1 vị trí trong m + n + 1 vị trí để ghi số 0, trong khi m vị trí còn lại sẽ ghi số 1 Do đó, tổng số dãy nhị phân có độ dài m + n + 1 với m ký tự 1 và n + 1 ký tự 0 là C(n + 1).
Vậy số các tổ hợp có lặp chập m của n phần tử bằng m m n mn1 mn1 n1
Ví dụ 1.5.3 Tiền giấy của Ngân Hàng Nhà Nước Việt Nam lưu hành phổ biến trên thị trường có 10 loại: 200đ, 500đ, 1000đ, 2000đ, 5000đ, 10000đ, 20000đ, 50000đ,
100000đ, 500000đ Hãy xác định số bộ khác nhau gồm 15 tờ giấy bạc của Ngân Hàng Nhà Nước Việt Nam.
Mỗi bộ giấy bạc bao gồm 15 tờ thuộc không quá 10 loại khác nhau, với khả năng có các tờ giấy bạc cùng loại Do không quan tâm đến thứ tự sắp xếp, số bộ giấy bạc khác nhau sẽ được tính bằng số tổ hợp lặp chập 15 của 10 loại, tương ứng với công thức toán học.
Ví dụ 1.5.4 Có bao nhiêu cách mua 10 quả trứng trong số 3 loại: Trứng gà, trứng vịt và trứng ngỗng?
Mỗi bộ trứng gồm 10 quả, được phân chia từ không quá 3 loại trứng như trứng gà, trứng vịt và trứng ngỗng, với điều kiện có những quả cùng loại Do không quan tâm đến thứ tự sắp xếp trong mỗi bộ, số cách mua 10 quả trứng từ 3 loại này được tính bằng số tổ hợp lặp chập 10 của 3 loại, tương đương với C(10, 3) = 66.
Nhị thức Newton
Định lí 1.6.1 Với a,b là các số thực và n là số nguyên dương, ta có n n k nk k
Công thức (1.19) được gọi là công thức nhị thức Newton (gọi tắt là nhị thức
Trước hết ta chứng minh khẳng định P(n) sau:
Với mỗi số thực x và một số nguyên dương n, ta có
Chứng minh bằng quy nạp theo n Rõ ràng P(1) đúng Giả sử P(n) đúng, ta có
Thay (1.22) vào (1.21) và áp dụng hằng đẳng thức Pascal, ta được n 1 n1 n k k1 k n n k 1 n n 1
Vậy P(n 1) đúng Theo nguyên lý quy nạp ta có P(n) đúng với mọi n
Trở lại định lí, nếu a 0 thì công thức hiển nhiên đúng Giả sử a 0 Đặt x b a và áp dụng (1.20) ta có
Công thức (1.19) thể hiện sự khai triển của a b n theo lũy thừa giảm của a và lũy thừa tăng của b Ngoài ra, chúng ta cũng có thể diễn đạt khai triển này với lũy thừa tăng của a và lũy thừa giảm của b.
Ví dụ 1.6.1 Cho n là số nguyên dương Hãy xác định tổng sau:
Ví dụ 1.6.2 Cho n là số nguyên dương Hãy chứng minh đẳng thức
Ta thấy C n là hệ số của x n trong khai triển nhị thức Newton của biểu thức
S(x) 1 x 2n Ta xét một cách khai triển khác của S x : n n n n
Ta có hệ số của x n trong khai triển trên là n n n n n1
Ví dụ 1.6.3 Chứng minh rằng với mỗi số nguyên dương n 2 , ta có
Lấy đạo hàm cấp 2 hai vế theo biến x ta được n n 1 1 x n2 1.2C 2 2.3C 3 x n 1 nC n x n2
Ví dụ 1.6.4 ( Đề thi đại học khối A năm 2006 ) Tìm hệ số của số hạng chứa x 26
1 trong khai triển nhị thức Newton của
Trước tiên ta đi xác định n Ta có
Từ giả thiết ta suy ra 22n 1 220 1 n 10.
Bây giờ ta đi xác định hệ số của số hạng chứa x 26 Ta có khai triển
26 là C k ứng với k thỏa mãn 11k 40 26 k 6.
Một số cách tiếp cận tới bài toán tổ hợp
Sử dụng phương pháp liệt kê
Khi đếm số lượng phần tử trong một tập hữu hạn, chúng ta nên chia tập đó thành các tập con rời nhau để việc đếm trở nên dễ dàng hơn.
Từ các chữ số 1 đến 9, có thể tạo ra bao nhiêu số tự nhiên gồm 6 chữ số khác nhau, trong đó tổng các chữ số ở hàng chục, hàng trăm và hàng nghìn bằng 8? Bài toán này yêu cầu phân tích các chữ số để tìm ra các tổ hợp phù hợp, đồng thời đảm bảo rằng mỗi chữ số chỉ xuất hiện một lần Việc xác định số lượng các số thỏa mãn điều kiện trên là một thách thức thú vị trong lĩnh vực tổ hợp.
Giả sử lập được số abcdef thỏa mãn yêu cầu bài toán Ta có c d e 8 nên chỉ có thể xảy ra hai khả năng c,d,e {1,2, 5} hoặc c,d,e {1, 3, 4}.
2, 5} thì a,b, f {3, 4, 6, 7, 8, 9} Số các số lập được trong trường hợp này là
Trường hợp 2: trường hợp này là c,d,e {1,
3, 4} thì a,b, f {2, 5, 6, 7, 8, 9} Số các số trong
S P A 3 720 Vậy các số thỏa mãn yêu cầu bài toán là
Chúng ta sẽ phân tích bài toán đã được giải trong ví dụ 1.1.4 của chương 1 Lần này, chúng ta sẽ tiếp cận bài toán theo một phương pháp khác là đếm bằng cách liệt kê.
Bài toán 2.1.2 yêu cầu xếp chỗ ngồi cho 6 học sinh trường A và 6 học sinh trường B trên một bàn dài có hai dãy ghế đối diện nhau, mỗi dãy gồm 6 ghế Điều kiện đặt ra là bất kỳ hai học sinh nào ngồi đối diện nhau phải thuộc hai trường khác nhau Vậy, câu hỏi đặt ra là có bao nhiêu cách xếp chỗ ngồi thỏa mãn yêu cầu này?
Chúng ta đếm bằng cách liệt kê như sau:
Trường hợp 1: Dãy ghế 1 có 1 học sinh trường A và 5 học sinh trường B Xếp dãy 1: Có C 1 A 1 cách chọn ra 1 học sinh trường A và xếp vào 1 trong 6 ghế, có
Có 5 cách để chọn 5 học sinh từ trường B và xếp họ vào 5 ghế còn lại Đối với dãy 2, có 5! cách để xếp 5 học sinh từ trường A vào 5 ghế đối diện với 5 học sinh trường B ở dãy 1 Ngoài ra, có 1! cách để xếp 1 học sinh trường B còn lại Tổng số cách xếp được tính bằng S ∩ C 1 A 1 A 5 5!.
Trong trường hợp 2, dãy ghế 1 có 2 học sinh trường A và 4 học sinh trường B Để xếp dãy 1, có C(2, A) cách chọn 2 học sinh trường A và sắp xếp vào 2 trong 6 ghế, cùng với A(4) cách chọn 4 học sinh trường B và xếp vào 4 ghế còn lại Đối với dãy 2, có 4! cách xếp 4 học sinh trường A vào 4 ghế đối diện với 4 học sinh trường B.
B ở dãy 1, có 2! cách xếp 2 học sinh trường B vào hai ghế còn lại Vậy ta có
Trường hợp 3: Dãy ghế 1 có 3 học sinh trường A và 3 học sinh trường B Tương tự, ta có S C 3 A 3 A 3 3 ! 3 ! cách xếp.
Trường hợp 4: Dãy ghế 1 có 4 học sinh trường A và 2 học sinh trường B Tương tự, ta có S C 4 A 4 A 2 4 ! 2 ! cách xếp.
Trường hợp 5: Dãy ghế 1 có 5 học sinh trường A và 1 học sinh trường B
Trường hợp 6: Xếp 6 học sinh trường A ở dãy ghế 1 và 6 học sinh trường B ở dãy ghế 2 hoặc ngược lại Khi đó ta có S 2 !.6 !.6 ! cách xếp.
Vậy ta có tất cả S S S S S S S 33177600 cách xếp.
Trong bài toán 2.1.3, một người đưa thư phải phân phát thư đến 19 nhà trong một dãy phố, với quy tắc rằng không có hai nhà liền kề nào nhận thư cùng một ngày Đồng thời, không được có nhiều hơn hai nhà liền kề không nhận thư trong cùng một ngày Vậy câu hỏi đặt ra là có bao nhiêu cách phân phối thư hợp lệ cho 19 nhà này?
Theo giả thiết, không có hai nhà liền nhau nào cùng nhận được thư, do đó tối đa có 10 nhà nhận được thư và tối thiểu 9 nhà không nhận được Đồng thời, vì không có hơn 2 nhà liền nhau không nhận được thư, nên ít nhất có 6 nhà nhận được thư.
Trong một ngày, có 6 nhà nhận được thư, được đánh số 1 tại 6 vị trí, trong khi giữa hai vị trí này phải có một nhà không nhận được thư, đánh số 0 Điều này dẫn đến việc có 5 nhà không nhận được thư Với 8 nhà không nhận được thư còn lại, chúng ta có thể sắp xếp theo nhiều cách khác nhau.
Có hai nhà không nhận được thư ở vị trí đầu và hai nhà không nhận được thư ở vị trí cuối Bốn nhà còn lại được sắp xếp xen kẽ vào năm vị trí giữa các nhà nhận thư.
Trong cách 2, có hai nhà không nhận được thư ở vị trí đầu, một nhà không nhận được thư ở vị trí cuối, và năm nhà còn lại được sắp xếp vào năm vị trí xen kẽ theo một cách duy nhất.
Có 2 nhà không nhận được thư ở vị trí cuối, 1 nhà không nhận được thư ở vị trí đầu, và 5 nhà còn lại được sắp xếp xen kẽ trong 5 vị trí với chỉ 1 cách xếp duy nhất.
Sau khi xếp các nhà không nhận được thư vào các vị trí đầu và cuối, nếu số nhà còn lại lớn hơn hoặc bằng 6, thì không còn cách sắp xếp nào thỏa mãn yêu cầu bài toán Do đó, tổng số cách xếp là 7.
Trong trường hợp có 7 nhà nhận được thư và 6 nhà không nhận được thư trong một ngày, sẽ còn lại 6 nhà không nhận được thư Các cách sắp xếp 6 nhà không nhận được thư có thể được thực hiện như sau:
Cách 1 Có 2 nhà đầu và 2 cuối không nhận được thư, còn lại 2 nhà không nhận thư xếp vào 6 vị trí xen kẽ nên có C 2 15 cách xếp.
Cách 2 Có 2 nhà đầu và 1 nhà cuối không nhận thư, còn lại 3 nhà không nhận thư xếp vào 6 vị trí xen kẽ nên có C 3 20 cách xếp.
Cách 3 Có 1 nhà đầu và 2 nhà cuối không nhận thư, còn lại 3 nhà không nhận thư xếp vào 6 vị trí xen kẽ nên có C 3 20 cách xếp.
Cách 4 Có 1 nhà đầu và 1 nhà cuối không nhận được thư, còn lại 4 nhà không nhận thư xếp vào 6 vị trí xen kẽ nên có C 4 15 cách xếp.
Cách 5 Có 2 nhà đầu và 0 nhà cuối, còn lại 4 nhà xếp vào 6 vị trí xen kẽ nên có
Cách 6 Có 0 nhà đầu và 2 nhà cuối không nhận được thư, còn lại 4 nhà không nhận thư xếp vào 6 vị trí xen kẽ nên có C 4 15 cách xếp.
Cách 7 Có 1 nhà đầu và 0 nhà cuối không nhận được thư, còn lại 5 nhà không nhận thư xếp vào 6 vị trí xen kẽ nên có C 5 6 cách xếp.
Cách 8 Có 0 nhà đầu và 1 nhà cuối không nhận được thư, còn lại 5 nhà không nhận thư xếp vào 6 vị trí xen kẽ nên có C 5 6 cách xếp.
Cách 9 Có 0 nhà đầu và 0 nhà cuối không nhận được thư, 6 nhà không nhận được thư còn lại xếp vào 6 vị trí xen kẽ nên có C 6 1 cách xếp.
Vậy có tất cả 40 60 13 113 cách sắp xếp.
Trường hợp 3: Trong 1 ngày có 8 nhà nhận được thư Tương tự ta có 183 cách sắp xếp.
Trường hợp 4: Trong 1 ngày có 9 nhà nhận được thư Tương tự ta có 47 cách sắp xếp.
Trong trường hợp 5, có 10 nhà nhận được thư, trong khi 9 nhà còn lại không nhận thư Các nhà không nhận thư được xếp xen kẽ giữa các nhà nhận được thư, tạo thành một cách sắp xếp duy nhất.
Vậy ta có tất cả 7+113+183+47+151 cách phân phối thư.
Bài toán 2.1.4 Cho tập A {0,1, 2, 3, 4, 5, 6, 7, 8} Tìm số các số gồm 3 chữ số phân biệt của A, chia hết cho 3.
Lời giải gồm các số chia hết cho 3;
Đếm các phần tử của phần bù
Trong một số trường hợp các phần tử của phần bù dễ đếm, ta tìm số phần tử của tập cần đếm A qua số phần tử của phần bù.
A là tập con của tập X Khi đó
Bài toán 2.2.1 ( Đề tuyển sinh ĐHQG TPHCM – khối A – 2000 ) Một thầy giáo có
Trong số 12 cuốn sách đa dạng, bao gồm 5 cuốn Văn học, 4 cuốn Âm nhạc và 3 cuốn Hội họa, thầy quyết định chọn ra 6 cuốn sách để tặng cho 6 em học sinh.
A, B,C , D, E , F mỗi em một cuốn Giả sử thầy giáo muốn rằng sau khi tặng sách xong, mỗi một trong 3 thể loại Văn học, Âm nhạc, Hội họa đều còn lại ít nhất 1 cuốn Hỏi thầy giáo có tất cả bao nhiêu cách tặng?
Ta lấy 6 cuốn sách trong 12 cuốn, đem tặng cho 6 học sinh mỗi em một cuốn có A 6 665280 cách.
Chúng ta cần tính số cách để tặng sách sao cho mỗi loại đều được tặng hết Số cách tặng 5 cuốn sách Văn và 1 cuốn sách Nhạc hoặc Họa là 7! = 5040 cách Đồng thời, số cách tặng 4 cuốn sách Nhạc cũng cần được xem xét.
2 trong các cuốn Văn hoặc Họa là C 2 6 ! cách Số cách tặng 3 cuốn Họa và 3 trong các cuốn Văn hoặc Nhạc là C 3 6 ! cách.
Vậy số cách tặng theo yêu cầu bài toán là
Bài toán 2.2.2 Cho tập A {0,1,2, 3, 4, 5} Tìm số các số gồm 4 chữ số của
A sao cho trong 4 chữ số có ít nhất 2 chữ số giống nhau.
Số các số gồm 4 chữ số tạo thành từ tập A là S 5.6 3
Chúng ta cần xác định số lượng các số gồm 4 chữ số khác nhau được tạo thành từ tập A Gọi số cần tìm là n với a, b, c, d là các chữ số khác nhau từ tập A Lưu ý rằng a không được bằng 0.
1 có 5 cách chọn, có A 3 cách chọn ra 3 chữ số khác a và xếp vào 3 vị trí b,c,d Vậy có
Như vậy số các số thỏa mãn yêu cầu của đề bài bằng
Bài toán 2.2.3 (VMO – 2008) yêu cầu xác định tổng số tự nhiên chia hết cho 9, với điều kiện mỗi số có tối đa 2008 chữ số và phải chứa ít nhất hai chữ số 9.
Giả sử X là tập tất cả các số tự nhiên thỏa mãn các điều kiện của đề bài. Theo bài ra, ta cần tính X Ký hiệu:
A * {a | a không có quá 2008 chữ số};
Xét tập hợp A và các số a thuộc A*, với a có m chữ số Khi thêm 2008 chữ số 0 vào trước số a, ta tạo ra một biểu diễn (*) của a gồm 2008 chữ số mà không làm thay đổi giá trị của số Biểu diễn này được ký hiệu lần lượt từ a1 đến a2008, thể hiện dưới dạng a1 a2 a2008.
2008 a 1 ,a 2 , , a 2008 có đúng k chữ số 9 và a i i1 0 (mod 9) , k 0, 2008
Ta có X A \ (A A ) Từ đó, vì A , A A và A A nên
Từ định nghĩa A dễ thấy a a a
A khi và chỉ khi a {0,1,2, , 8}, i 1,2007 và a 9 r , trong đó r là số nguyên thuộc đoạn [1; 9] mà
0 i1 chính bằng số dãy 2007 chữ số có thể lập được từ các chữ số 0, 1, 2,…, 8 Vì thế A 0
Dễ thấy, số (trong dạng biểu diễn (*)) thuộc thực hiện liên tiếp hai bước sau:
A có thể được tạo ra từ việc
Bước 1: Từ các chữ số 0, 1, 2, …, 8, lập dãy số gồm 2007 chữ số thỏa mãn tổng các chữ số của dãy chia hết cho 9;
Bước 2: Sử dụng dãy số đã lập ở bước 1, bạn có thể thêm chữ số 9 bằng cách ghi nó ngay trước chữ số đầu tiên, ngay sau chữ số cuối cùng, hoặc đặt nó giữa hai chữ số liền nhau trong dãy.
Lập luận tương tự như cách tìm ra A , ta thấy có 9 2006 cách thực hiện bước
1 Từ đó, do có 2008 cách thực hiện ở bước 2 nên có 2008.9 200
Có 6 phương án để thực hiện liên tiếp hai bước đã nêu Mỗi phương án sẽ cho ra một số thuộc tập A, và hai phương án khác nhau sẽ tạo ra hai số khác nhau Do đó, ta có A .
Sử dụng nguyên lý bao gồm và loại trừ
Mục này sẽ mở rộng công thức tính số phần tử của hợp hai hoặc ba tập hợp hữu hạn, đồng thời áp dụng công thức tính số phần tử cho hợp n tập hợp hữu hạn bất kỳ.
Khi chúng ta biểu diễn tập cần đếm mà các tập A i n
A A i i1 có giao khác tập rỗng ( A A
) thì khi đó chúng ta không thể sử dụng quy tắc cộng mà cần xây dựng một quy tắc đếm mới.
Xét hai tập hợp hữu hạn A và B, nếu A và B có phần giao nhau là A ∩ B, thì khi cộng số phần tử của A và số phần tử của B, các phần tử thuộc A ∩ B sẽ bị đếm hai lần.
Xét ba tập hợp hữu hạn A , A , A , A A , A A , A A ,
A A A thì khi đó các phần tử của A A , A A , A
1 2 3 lần, các phần tử của A A A
1 2 2 3 3 1 được đếm ba lần Suy ra
Nguyên lý bao gồm và loại trừ là một khái niệm quan trọng trong lý thuyết tập hợp Định lý 2.3.1 nêu rõ rằng, với các tập hữu hạn A1, A2, , An (với n ≥ 2), ta có thể áp dụng nguyên lý này để tính toán số phần tử trong hợp của các tập này.
Chúng ta sẽ chứng minh công thức bằng cách chỉ ra rằng mỗi phần tử của hợp n tập hợp được đếm một lần duy nhất Giả sử m là phần tử chung của đúng r tập trong các tập A1, A2, , An, với điều kiện 1 ≤ r ≤ n.
Trong bài toán này, số lần xuất hiện của phần tử m được tính dựa trên số tập giao của các tập hợp khác nhau Cụ thể, có C2 tập giao từ hai tập chứa m (được đếm 2 lần), và C r tập giao từ r tập chứa m (được đếm r lần) Theo công thức (2.1), tổng số lần m được đếm là tổng hợp của các giá trị này.
Do đó, mỗi phần tử của hợp n tập hợp được đếm đúng một lần khi tính giá trị ở vế phải của công thức (2.1) Vậy định lí được chứng minh.
Bài toán 2.3.1 Tính số các hoán vị của dãy chữ " XAXAM " sao cho không có hai chữ cái nào giống nhau đứng cạnh nhau.
Gọi P là tập hợp chứa các hoán vị của dãy chữ " XAXAM " Khi đó
Gọi P là tập chứa các hoán vị của dãy chữ mà 2 chữ A đứng cạnh nhau,
P là tập chứa các hoán vị của dãy chữ mà 2 chữ X đứng cạnh nhau Hai chữ A đứng cạnh nhau coi là một chữ thì 4 !
A , 2 chữ X đứng cạnh nhau như một chữ thì P P 3 ! Suy ra số các hoán vị
1 2 thỏa yêu cầu bài toán bằng
Bài toán 2.3.2 yêu cầu tính số cách xếp bốn cầu thủ được đánh số từ 1 đến 4 thành hàng dọc, sao cho ít nhất một cầu thủ có số áo trùng với vị trí của mình trong hàng Để giải quyết bài toán này, ta có thể áp dụng nguyên lý bổ sung, tính tổng số cách xếp và trừ đi số cách xếp mà không có cầu thủ nào đứng đúng vị trí.
Kí hiệu A đại diện cho tập hợp các cách xếp hàng của cầu thủ mang áo số k đứng ở hàng thứ k (với k = 1, 2, 3, 4) Tập hợp các cách xếp hàng này bao gồm ít nhất một cầu thủ có số áo trùng với thứ tự của hàng, được ký hiệu là r.
Nếu cầu thủ mang áo số 1 đứng đầu thì có 3! cách xếp ba cầu thủ còn lại.
Xét tập A A là tập hợp các cách cách xếp hàng mà cầu thủ mang áo số 1
1 2 và cầu thủ mang áo số 2 lần lượt đứng ở các vị trí số 1 và số 2 Khi đó có 2! cách xếp các cầu thủ còn lại Suy ra
Xét tập A A A là tập hợp các cách xếp hàng mà cầu thủ mang áo số 1
Trong một đội hình, cầu thủ mang áo số 1 đứng ở vị trí số 1, cầu thủ số 2 ở vị trí số 2, và cầu thủ số 3 ở vị trí số 3 Điều này cho thấy chỉ có 1! cách để xếp cầu thủ còn lại.
Cuối cùng các cách xếp mà tất cả các cầu thủ có số áo trùng với số thứ tự trong hàng là 1 cách Suy ra
Theo công thức bao gồm và loại trừ ta có
Vậy có tất cả 15 cách xếp mà ít nhất một cầu thủ có số áo trùng với số thứ tự của cầu thủ đó ở trong hàng.
Bài toán 2.3.3 Cho tập X {1,2, 3, ,2010} Hỏi có bao nhiêu phần tử của X là bội của ít nhất một phần tử của tập T {2, 3,5,7}?
Kí hiệu M là tập các phần tử của X là bội của ít nhất một phần tử của tập
Vậy có 1542 phần tử của X là bội của ít nhất một phần tử của tập
Bài toán 2.3.4 (IMO - 1991) yêu cầu tìm số tự nhiên n nhỏ nhất trong tập S ∩ {1, 2, 3, , 280} sao cho mọi tập con gồm n phần tử của S đều chứa 5 số đôi một nguyên tố cùng nhau.
Kí hiệu A là số các phần tử của A , thì ta có
Vậy với 5 số tùy ý của A , theo nguyên lý Dirichlet phải có hai số thuộc
A (1 i 4) nào đó, rõ ràng hai số này không nguyên tố cùng nhau Do vậy, số n cần tìm phải lớn hơn 216.
Ta sẽ chứng minh n 217 thỏa mãn đề bài Ta đặt
Chúng ta có tập hợp P chứa số 1 và tất cả các số nguyên tố trong tập S Xét tập hợp T tùy ý có 217 số Để chứng minh điều này, chỉ cần xem xét trường hợp cụ thể.
Khi đó T (S \ P) 217 4 213 Điều này chứng tỏ rằng từ tập hợp tất cả các số không nguyên tố trong S (tất cả gồm nằm trong T Ta đặt
220 số) có nhiều nhất 7 số không
Rõ ràng M S \ P (i 1, 2, , 8) và mọi phần tử của
M đôi một nguyên tố cùng nhau Theo nguyên lý Dirichlet, tồn tại ít nhất 1 chỉ số i (1 i 8) sao cho M
0 T Ta có điều phải chứng minh.
Bài toán 2.3.5 ( IMO - 1989 ) Cho tập hợp E {1,2, ,2n} Một hoán vị
{x , x , , x } của tập hợp E được gọi là có tính chất P , nếu như tồn tại i, 1 i 2n 1 sao cho
1 i1 n (ở đây n là số nguyên dương cho trước).
Chứng minh rằng số các hoán vị có tính chất P lớn hơn số các hoán vị không có tính chất P
Ta chia các số 1, 2, , 2n thành từng cặp như sau
Gọi A là tập hợp tất cả những hoán vị sao cho trong các hoán vị đó, hai phần tử k và k n đứng kề nhau. k
Gọi A là tập hợp tất cả những hoán vị có tính chất P Khi đó n
Theo nguyên lý bao gồm và loại trừ, ta có n
Trong mỗi hoán vị của 2n phần tử, ta có C 1
2n 1 cách chọn cặp 2 phần tử kề nhau để đặt 2 số k và n k Vì vậy ta có
Trong mỗi hoán vị của 2n phần tử, ta có 2
3) cách chọn 2 cặp, mỗi cặp có 2 phần tử kề nhau để đặt 2 cặp số (k,n k) và (j,n j).
Số hoán vị của các phần tử trong tập E có tính chất P lớn hơn số hoán vị của các phần tử trong tập E không có tính chất P, điều này cần được chứng minh.
Sử dụng cách xây dựng phần tử đếm
Trong các bài toán đếm, để đạt được kết quả chính xác, việc mô tả phần tử cần đếm là rất quan trọng Sau đó, chúng ta tiến hành sắp xếp các phần tử này thông qua hoán vị Quá trình này bao gồm hai bước chính cần thực hiện.
1 Mô tả phấn tử đếm
Bài toán 2.4.1 yêu cầu xác định số lượng số có chín chữ số, bao gồm năm chữ số 1 và bốn chữ số khác là 2, 3, 4, 5 Câu hỏi đặt ra là có bao nhiêu số có thể được tạo ra khi các chữ số được xếp tùy ý.
Gọi số cần lập có dạng
Lời giải n a a a a a a a a a , trong đó có năm chữ số 1 và bốn chữ số còn lại là 2, 3, 4 và 5.
Như vậy với chín vị trí, ta có C 5 cách chọn ra năm vị trí và xếp năm chữ số
1 Khi đó còn lại bốn vị trí, xếp bốn chữ số 2, 3, 4, 5 có P 4 ! cách xếp.
Vậy có tất cả C 5 4 ! 3024 số thỏa mãn yêu cần bài toán.
Bài toán 2.4.2 trong đề thi tuyển sinh ĐHSP Hà Nội năm 2000 yêu cầu xác định số lượng số có tám chữ số được tạo thành từ các chữ số 1, 2, 3, 4, 5, 6, trong đó chữ số 1 và 6 xuất hiện đúng hai lần, còn các chữ số khác (2, 3, 4, 5) xuất hiện đúng một lần.
Gọi số cần lập có dạng n a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 , đúng hai lần, các chữ số còn lại có mặt đúng một lần.
49 trong đó chữ số 1 và 6 có mặt
Với tám vị trí, ta có C 2 cách chọn hai vị trí và xếp hai chữ số 1, có C 2 cách
8 6 chọn hai vị trí trong 6 vị trí còn lại xếp hai chữ số 6 Sau cùng ta có P 4 ! cách xếp bốn chữ số 2, 3, 4, 5 vào bốn vị trí còn lại.
Vậy có tất cả C 2 C 2 4 ! 10080 số thỏa mãn yêu cầu.
Bài toán 2.4.3 Cho tập A 1, 2, 3, 4, 5 có bao nhiêu số gồm 6 chữ số trong đó có
3 chữ số a , 2 chữ số b , 1 chữ số c với a A,b A,c
Lời giải và a,b, c khác nhau?
Để lấy ra 3 phần tử phân biệt từ tập A, ta có C3 cách thực hiện Sau khi chọn 3 chữ số này, có 3 cách để chỉ định số xuất hiện 3 lần, 2 cách để chỉ định một trong hai số còn lại xuất hiện 2 lần, và số còn lại sẽ xuất hiện 1 lần Do đó, tổng số cách chọn số xuất hiện 3 lần, 2 lần và 1 lần là C3 3 2, ví dụ như (3, 3, 3, 2, 2, 4).
Hoán vị các bộ số nhận được ta thu được số thỏa mãn yêu cầu bài toán.
Sử dụng các công thức tổ hợp
Trong nhiều bài toán, công thức và đẳng thức tổ hợp đóng vai trò quan trọng trong việc tìm ra lời giải hiệu quả Bài viết này sẽ làm rõ tác dụng của số C2 và phân tích thông qua một số bài toán tiêu biểu.
Trong bài toán 2.5.1 từ Liên Xô năm 1965, một cuộc hội thảo có tổng cộng 40 cuộc họp, mỗi cuộc họp quy tụ 10 thành viên Điều kiện đặt ra là hai thành viên bất kỳ chỉ có thể tham gia cùng một cuộc họp tối đa một lần Từ đó, cần chứng minh rằng số lượng thành viên tham gia hội thảo phải lớn hơn 60.
Giả sử cuộc hội thảo có n thành viên Do đó có C 2 cách chọn hai thành viên.
Trong một cuộc họp, có hai cách để chọn hai thành viên Vì mỗi cặp thành viên chỉ có thể tham dự cùng nhau một lần, ta có thể tính số cách chọn bằng công thức C 2 ∩ 40C 2, tương đương với n(n-1) ∩ n 10 3600 hay n ∩ 60 Điều này cần được chứng minh rõ ràng.
Nếu giả thiết được thay đổi thành hai thành viên bất kỳ tham dự họp với nhau ít nhất một lần, thì số lượng thành viên tối đa trong cuộc hội thảo sẽ là 60 Tổng quát, với một cuộc họp có m thành viên, ta có thể diễn đạt bằng công thức: C(2) ∩ kC(2) ∩ n(n + 1).
Số C2 đóng vai trò quan trọng trong việc tìm ra lời giải cho bài toán Tiếp theo, chúng ta sẽ khám phá một bài toán mới.
Trong một hội nghị sử dụng 4 ngôn ngữ chính thức, nếu hai đại biểu bất kỳ luôn có một ngôn ngữ chung mà cả hai đều biết, thì có thể chứng minh rằng ít nhất 60% đại biểu sẽ biết một ngôn ngữ nào đó.
Nếu một người chỉ biết một ngôn ngữ, ta có thể suy ra rằng tất cả những người khác đều thông thạo ngôn ngữ đó Kết luận này là điều hiển nhiên trong bài toán.
Giả sử tất cả đại biểu đều biết ít nhất 2 ngôn ngữ Gọi số đại biểu là n và tập
A, B,C , D lần lượt là tập những người biết các ngôn ngữ những người biết ngôn ngữ I , II , III , IV là C 2 ,C 2 ,C
2 ,C 2 nhất 2 ngôn ngữ, cho nên ta có bất đẳng thức sau:
I , II , III , IV Số cặp
Do một người biết ít
Bất đẳng thức này tương đương với
Không mất tính tổng quát, ta giả sử A là tập nhiều phần tử nhất trong các tập
Từ bất đẳng thức này dễ dàng chứng minh được A 6 n , với n 2
10 Vậy trong mọi trường hợp, ta có điều phải chứng minh.
Bài toán 2.5.3 Giả sử X là một tập n phần tử Tìm số cặp không thứ tự
A, B là những tập con của X thỏa mãn A B , A B X , (
và trùng nhau và được đếm là một cặp).
Giả sử A có r phần tử, với 0 ≤ r ≤ n, thì có C(n, r) cách để chọn các tập A Tương ứng với tập A, tập B sẽ chứa n - r phần tử còn lại từ tập X cùng với một số phần tử khác.
A Khi đó B X \ A C ( C là tập con của A ) Như vậy số cách chọn B bằng số cách chọn tập con C của tập A gồm r phần tử bằng
Theo quy tắc nhân thì số cách chọn cặp
Suy ra số cặp phần tử phải tìm ( A có thể bằng B ) bằng n
Trong số cách chọn này chỉ có duy nhất một trường hợp A B X Suy ra số cặp thỏa mãn yêu cầu bài toán là 3 n 1
Bài toán 2.5.4 Xét một lưới ô vuông (n n) trên hệ trục tọa độ Xuất phát từ điểm n r r n n
(0, 0) ta đi trên các cạnh ô vuông sang phải và lên trên đến điểm (n,n) Hỏi có bao nhiêu đường đi từ (0, 0) đến điểm (n,n) ?
Để di chuyển từ điểm (0, 0) đến (n, n), ta cần thực hiện n bước đi ngang và n bước đi lên, mỗi bước có độ dài 1 Trong đó, mỗi bước đi ngang được ký hiệu bằng số 0 và mỗi bước đi lên bằng số 1 Mỗi lộ trình tương ứng với một dãy số gồm 2n phần tử, trong đó có n số 0 và n số 1 Để tạo ra một dãy số như vậy, ta chỉ cần chọn n vị trí trong tổng số 2n vị trí để đặt số 0, trong khi các vị trí còn lại sẽ là số 1 Số cách chọn n vị trí trong 2n vị trí được tính bằng hệ số C(n, n).
Vậy có tất cả C n đường đi từ (0, 0) đến điểm (n,n)
Sử dụng nguyên lý phân phối các đồ vật vào hộp
Chúng ta sẽ bắt đầu mục này bằng một định lí sau: Định lí 2.6.1 Giả sử có N đối tượng khác nhau và k hộp khác nhau T ,T , ,T
Ta xếp n 1 đối tượng vào hộp T 1 , n 2 đối tượng vào hộp T , , n đối tượng vào hộp
Số cách phân phối các phần tử vào hộp, với n đối tượng không quan tâm đến thứ tự trong từng hộp, được tính bằng công thức n ∩ n ∩ ∩ N.
Mỗi cách sắp xếp các đối tượng vào hộp được mô tả như sau(tương ứng 1-1): Xếp N đối tượng thành một hàng ngang.
Xếp n đối tượng đầu vào hộp T , xếp n đối tượng tiếp theo vào hộp
Số cách phân bố n đối tượng vào hộp T không phụ thuộc vào thứ tự của các đối tượng trong hộp Do đó, hoán vị của các đối tượng đầu, tiếp theo và cuối cùng trong dãy hàng ngang không tạo ra cách phân bố mới Kết luận, số cách phân bố các đối tượng vào hộp tương đương với số hoán vị có lặp của chúng.
, n phần tử giống nhau n n n N Ta có
Định lý 2.6.2 trình bày cách phân phối N đối tượng khác nhau vào k hộp theo quy tắc cụ thể Theo đó, mỗi hộp sẽ chứa m đối tượng, và quy tắc này áp dụng cho tất cả các hộp Sự phân phối không quan tâm đến thứ tự của các phần tử trong từng hộp hay vị trí của các hộp có số lượng phần tử bằng nhau Do đó, số cách phân phối N đối tượng vào k hộp được tính toán dựa trên các quy tắc đã nêu.
Ta mô tả một cách sắp xếp các đối tượng (phần tử) vào hộp thỏa mãn các yêu cầu của bài toán như sau:
Xếp N phần tử thành một hàng ngang và xếp vào hộp.
Việc thay đổi thứ tự giữa các đối tượng trong từng hộp hoặc thay đổi vị trí của các hộp có số phần tử bằng nhau không tạo ra phân bố mới, do đó số phân bố trong trường hợp này vẫn giữ nguyên.
Nhận xét 2.6.1 : Khi giữa các bài toán mà số phần tử của mỗi cặp hộp bằng nhau chúng ta phải phân biệt 2 trường hợp:
Trường hợp 1: n n n n Khi đó N k.n đối tượng được xếp vào k hộp khác nhau T ,T , T mà thứ tự giữa các đối tượng không quan tâm bằng
Trong trường hợp 2, khi không phân biệt hộp và không đánh số hay đặt tên trước, việc thay đổi vị trí giữa các bộ phần tử sẽ không tạo ra hoán vị mới, nhưng vẫn giữ nguyên cách xếp Do đó, số cách xếp các phần tử trong tình huống này được suy ra là không đổi.
Bài toán 2.6.1 yêu cầu tìm số cách phân phối 10 vật phân biệt vào 5 hộp phân biệt với điều kiện cụ thể: hộp 1 chứa 3 vật, hộp 2 chứa 2 vật, hộp 3 chứa 2 vật, hộp 4 chứa 3 vật và hộp 5 không chứa vật nào Để giải bài toán này, ta cần áp dụng quy tắc tổ hợp để xác định cách phân chia các vật vào các hộp theo đúng yêu cầu.
Xếp 10 vật thành một hàng ngang có 10 ! cách xếp.
Xếp 3 vật đầu tiên vào hộp 1, xếp 2 vật tiếp theo vào hộp 2, xếp 2 vật tiếp theo vào hộp 3, xếp 3 vật tiếp theo vào hộp 4.
Vì không chú trọng đến thứ tự của các vật trong từng hộp, nên hoán vị của 3 vật đầu tiên, 2 vật ở hộp 2, 2 vật ở hộp 3 và 3 vật ở hộp 4 không tạo ra cách phân phối mới.
Như vậy số cách phân phối 10 đồ vật đã cho vào 5 hộp phân biệt sẽ là
Chú ý : Ta hoàn toàn có thể giải bài toán bằng cách giải sau đây Cách giải này cũng là một hướng cho cách chứng minh các định lí 2.6.1 và 2.6.2.
Cách giải 2 Mỗi cách phân phối có thể tiến hành liên tiếp theo các bước sau:
Bước 1: Chọn 3 trong 10 vật cho vào hộp 1 Suy ra n C 3
Bước 2: Chọn 2trong 7 vật còn lại cho vào hộp 2 Suy ra n
Bước 3: Chọn 2 trong 5 vật còn lại cho vào hộp 3 Suy ra n
Bước 4: Chọn 3 vật còn lại cho vào hộp 4 Suy ra n C 3
Theo quy tắc nhân, số cách phân phối 10 vật phân biệt vào 5 hộp phân biệt thỏa mãn yêu cầu đề bài là n 1 n 2 n 3 n 4
Bài toán 2.6.2 Một xe chở 50 khách và dừng ở 10 điểm đỗ Có bao nhiêu trường hợp khác nhau sao cho ở mỗi điểm đỗ có đúng 5 người khách xuống xe?
Có 50! cách sắp xếp 50 khách thành một hàng ngang Các điểm dừng được đánh số từ T1 đến T10 Cụ thể, 5 khách đầu tiên sẽ xuống tại điểm T1, 5 khách tiếp theo sẽ xuống tại T2, và cứ tiếp tục như vậy cho đến khi 5 khách cuối cùng xuống tại điểm T10.
Số cách xuống xe của 50 khách tại 10 điểm đỗ khác nhau, mỗi điểm đỗ có 5 khách, được tính bằng 50! Việc thay đổi thứ tự của 5 khách khi xuống tại một điểm đỗ không làm thay đổi cách xếp mới, do đó, số cách xuống xe được xác định dựa trên quy tắc này.
Bài toán 2.6.3 yêu cầu tìm số cách sắp xếp 10 cặp vợ chồng đi du lịch trên 5 con thuyền nhỏ, mỗi thuyền chở 4 người với điều kiện mỗi thuyền phải có đúng 2 nam và 2 nữ Để giải bài toán này, ta cần xác định số cách phân chia các cặp vợ chồng thành nhóm sao cho mỗi nhóm đáp ứng yêu cầu giới tính.
Lời giải Đầu tiên ta xếp 10 nam vào 5 thuyền mỗi thuyền 2 nam Ta có 10! cách xếp
Trong bài toán này, chúng ta có 10 nam đứng thành một hàng ngang Hai nam đầu tiên được xếp vào một trong năm thuyền, hai nam tiếp theo vào một trong bốn thuyền còn lại, và tiếp tục như vậy cho đến hai nam cuối cùng được xếp vào thuyền thứ nhất.
5 Vì thay đổi thứ tự giữa hai nam trong cùng một thuyền không thu được cách xếp mới Vì thay đổi thứ tự giữa các thuyền cũng không thu được cách xếp mới Suy ra số cách xếp 10 nam vào 5 thuyền bằng P 1 10 !
5 !(2 !) 5 Sau khi xếp mỗi thuyền 2 nam thì mỗi thuyền được đánh số T ,T ,T ,T ,T , tương ứng với 2 nam cụ thể đã xếp Khi đó có thuyền T ,T ,T ,T ,T nêu trên.
Theo quy tắc nhân thì số cách sắp xếp bằng 10! 10! (10!) 2
Sử dụng công thức truy hồi
Phương pháp này rất hiệu quả trong việc giải quyết nhiều bài tập, nhưng để thiết lập quan hệ truy hồi, chúng ta cần xác định yếu tố đặc thù trong giả thiết của từng bài toán.
Trên mặt phẳng, với n đường thẳng không song song và không có ba đường thẳng đồng quy, số phần mà các đường thẳng này chia mặt phẳng thành là một bài toán thú vị Câu hỏi đặt ra là: Số phần này là bao nhiêu?
S(n) là số phần mà mặt phẳng được chia bởi n đường thẳng, với điều kiện không có hai đường thẳng nào song song và không có ba đường thẳng nào đồng quy Đường thẳng thứ n sẽ tạo ra nhiều phần hơn trong mặt phẳng.
1 theo giả thiết sẽ cắt n đường thẳng trước tại đúng n điểm và đường thẳng này được chia thành n
1 đoạn bởi n điểm chia đó Mỗi đoạn biến một miền cũ thành hai miền mới nên số miền tăng lên là n 1 Suy ra
Bài toán 2.7.2 yêu cầu xét đa giác đều 12 đỉnh A1, A2, , A12 với tâm O Chúng ta cần tô màu các miền của tam giác OAiAi+1 (1 ≤ i ≤ 12) bằng 4 màu: đỏ, xanh, vàng, đen, sao cho các miền tam giác kề nhau không được cùng màu Vấn đề đặt ra là tìm số cách tô màu hợp lệ cho các miền này.
Ta thấy có 4 cách tô màu tam giác thứ nhất, 3 cách tô màu tam giác thứ hai, , 3 cách tô màu tam giác thứ 12 Vậy có tất cả 4.3 11 cách tô.
Nếu tam giác cuối cùng có màu khác với tam giác đầu tiên, chúng ta có một cách tô đúng Ngược lại, nếu tam giác cuối cùng cùng màu với tam giác đầu tiên, ta sẽ nhận được một cách tô khác.
12 sai Đối với một cách tô sai ta bỏ đi đỉnh A được tam giác OA A cùng màu tam
1 giác OA A và nhận được một cách tô đúng của đa giác 11 đỉnh.
Suy ra công thức truy hồi
Bài toán 2.7.3 Cho tập hợp S 1, 2, 3, , n Tìm số cách chia tập S thành ba tập con khác rỗng sao cho trong mỗi tập con không chứa hai số nguyên liên tiếp.
Kí hiệu S(n) là số cách chia tập S thành ba tập con khác rỗng, với điều kiện rằng không tập con nào chứa hai phần tử liên tiếp Bài viết này sẽ hướng dẫn cách tính S(n + 1) dựa trên S(n).
Giả sử chúng ta đã chia thành ba tập con với tổng số phần tử là n Khi bổ sung phần tử thứ n + 1, sẽ có hai khả năng xảy ra.
Khả năng 1: Tập hợp n ∩ 1 không tạo thành tập mới, tức là tập n ∩ 1 chứa ít nhất một phần tử khác Trong trường hợp này, có hai cách để bổ sung n ∩ 1 vào một trong hai tập không chứa n Do đó, số cách xây dựng tập con trong tình huống này là 2S(n).
Khả năng 2 cho thấy n và 1 tạo thành một tập con mới, với n số từ 1 đến n nằm trong hai tập hợp còn lại Chỉ có một cách chia thỏa mãn, đó là một tập chứa số chẵn và tập còn lại chứa các số lẻ Vì vậy, số cách trong trường hợp này là một.
Vậy ta thu được công thức truy hồi
Mặt khác, kiểm tra trực tiếp có được công thức tổng quát của S(n) là
S(3) 1 Kết hợp với (*), ta dễ dàng tìm
Tiếp theo, ta sẽ sử dụng các dãy truy hồi lồng nhau để giải toán.
Bài toán 2.7.4 ( Romanian MO 2003 ) Cho n là một số nguyên dương Có bao nhiêu số có n chữ số từ tập hợp {2, 3, 7, 9} và chia hết cho 3?
Gọi A là tập hợp các số có n chữ số lập từ tập {2, 3, 7, 9} và chia hết cho 3.
B là tập hợp các số có n chữ số được lập từ tập {2, 3, 7, 9} và không chia hết cho
3 Ta cần tìm a n A n sau: Đặt b n B n Ta thấy mỗi số thuộc A chỉ có thể thu được bằng hai cách
Để tạo ra số mới từ tập A, bạn có thể thêm 3 hoặc 9 vào phía sau số đã chọn, với hai tùy chọn để thực hiện Đối với tập B, bạn chỉ có thể thêm 2 hoặc 7 vào phía sau số đã chọn, nhưng mỗi số trong tập này chỉ có một cách thêm duy nhất.
Sử dụng phương pháp đánh số
Khi lựa chọn vị trí để sắp xếp các phần tử theo yêu cầu của bài toán, việc đánh số các vị trí và thay thế bằng một bộ số tương ứng là rất quan trọng Điều này giúp đảm bảo tính chất của các bộ số phù hợp với yêu cầu bài toán Tìm kiếm các bộ số có tính chất cụ thể là một nhiệm vụ đơn giản.
Bài toán 2.8.1 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?
Chúng ta đánh số các vị trí từ 1 đến 11 và cần chọn 4 vị trí không kề nhau để sắp xếp các em nữ Việc này tương đương với việc chọn 4 số a, b, c, d sao cho chúng thỏa mãn điều kiện không nằm cạnh nhau.
1 a Để 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 C 4 Suy ra có
4 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à C 4 4 ! 7 ! 8467200
Bình luận : Ngoài cách giải bài toán theo cách trên, ta cũng có thể giải bài toán theo một cách khác như sau:
Khi xếp 7 học sinh nam thành hàng ngang, chúng ta tạo ra 8 vị trí để đặt 4 học sinh nữ, đảm bảo rằng không có hai học sinh nữ nào đứng cạnh nhau Có 7! cách xếp 7 học sinh nam Từ 8 vị trí này, ta có C(4) cách chọn ra 4 vị trí để xếp 4 học sinh nữ, và có 4! cách sắp xếp 4 học sinh nữ trong các vị trí đã chọn.
Vậy có tất cả C 4 4 ! 7 ! cách xếp thỏa mãn yêu cầu bài toán.
Bài toán 2.8.2 Xét đa giác đều n đỉnh ( n 12 ) Hỏi có tất cả bao nhiêu tứ giác có
4 cạnh là 4 đường chéo của đa giác?
Ta đánh số các đỉnh A , A , , A tương ứng với các chỉ số Ta đếm các tứ
1 2 n giác thỏa mãn yêu cầu bài toán có đỉnh là A Các đỉnh A , A sẽ không được chọn
1 2 n vì A A , A A là cạnh của đa giác Ta cần chọn thêm 3 đỉnh tương ứng với bộ 3 số
Số cách chọn 3 đỉnh trong một đa giác với n đỉnh bằng số cách chọn 3 số phân biệt từ 5 đến n Do đó, số tứ giác thỏa mãn yêu cầu bài toán là C(3) Với n đỉnh, mỗi tứ giác được đếm lặp lại nC(3) lần.
4 lần theo 4 đỉnh nên số tứ giác cần tìm bằng n5
Trong bài toán 2.8.3, có một nhóm gồm 5 cô gái (G1, G2, G3, G4, G5) và 12 chàng trai, tổng cộng là 17 người Nhiệm vụ là sắp xếp nhóm người này vào 17 ghế xếp thành hàng ngang, đồng thời phải đảm bảo các điều kiện đã cho được thỏa mãn Việc sắp xếp này không chỉ đòi hỏi tính toán mà còn cần sự sáng tạo trong cách bố trí để đạt được kết quả tối ưu.
(i) Mỗi ghế có đúng 1 người ngồi;
(ii) Thứ tự ngồi của các cô gái, xét từ trái qua phải là G ,G ,G ,G ,G ;
(iii) Giữa G và G có ít nhất 3 chàng trai;
(iv) Giữa G và G có ít nhất là 1 chàng trai và nhiều nhất là 4 chàng trai
Hỏi có tất cả bao nhiêu cách xếp như vậy?
(Hai cách xếp được coi là khác nhau nếu tồn tại một chiếc ghế mà người ngồi ở chiếc ghế đó trong hai cách xếp là khác nhau).
Lời giải Đánh số thứ tự của các ghế từ trái sang phải là 1, 2, ,17 Gọi x , x , x , x , x là vị trí chỗ ngồi của các cô gái G ,G ,G ,G ,G tương ứng Đặt
Vì x x 3 nên x 3 x Khi đó, ta có
1 x x 3 x 3 x 3 x 3 14 Đổi biến và 1 x x 6 y x , y x 3, y x 3, y x 3, y x 3 ta được
Ta xét các trường hợp sau: và y 4 y 3 2, 3, 4, 5
Trường hợp 1: Với y y 2 suy ra 1 y y y y 2 12 Ta chọn 4 số phân biệt y , y , y , y
2 trong 12 số từ 1 đến 12 có C 4 cách chọn.
Trường hợp 2: Với y y 3 suy ra 1 y y y y 3 11 Ta chọn 4 số phân biệt y , y , y , y 3 trong 11 số từ 1 đến 11 có C 4 cách chọn.
Trường hợp 3: Với y y 4 suy ra 1 y y y y 4 10 Ta chọn 4 số phân biệt y , y , y , y 4 trong 10 số từ 1 đến 10 có C 4 cách chọn.
Trường hợp 4: Với y y 5 suy ra 1 y y y y 5 9 Ta chọn 4 số phân biệt y , y , y , y
5 trong 9 số từ 1 đến 9 có C 4 cách chọn.
Từ các trường hợp trên ta được
Số cách xếp chỗ ngồi cho 5 cô gái là 1161 Với 12 chàng trai có thể hoán vị trên 12 chiếc ghế dành riêng cho họ, tổng số cách xếp chỗ ngồi sẽ là 12! nhân với 1161.
Phương pháp xây dựng song ánh
Nếu có một song ánh đi từ một tập hữu hạn X tới một tập hữu hạn Y thì
Nếu tồn tại một song ánh α: X ∩ Y, chúng ta có thể thay thế việc đếm các phần tử của tập X bằng việc đếm các phần tử của tập Y Trong các nội dung trước, song ánh đã được sử dụng hiệu quả, chẳng hạn như trong việc chứng minh định lý 1.5.3 Mục này sẽ phân tích sâu hơn thông qua các bài toán cụ thể.
Bài toán 2.9.1 (Trung Quốc - 1997) nghiên cứu các xâu nhị phân có độ dài n, trong đó a là số xâu không chứa quá ba số 0 liên tiếp, và b là số xâu không chứa bốn số 0 hoặc 1 liên tiếp theo các mẫu 0, 0, 1, 1 hoặc 1, 1, 0, 0 Cần chứng minh rằng b lớn hơn hoặc bằng 2a.
Một xâu thuộc loại A được định nghĩa là xâu không chứa ba số liên tiếp 0, 1, 0 Trong khi đó, xâu thuộc loại B là xâu không có bốn số hạng liên tiếp 0, 0, 1, 1 hoặc 1, 1, 0, 0.
Với mỗi xâu X x 1, x 2 , , x n , ta xây dựng f (X ) y 1, y 2 , , y n1 như y 0, y x x x (mod 2).
Rõ ràng X chứa ba số liên tiếp 0, 1, 0 khi và chỉ khi f (X) chứa bốn số hạng liên tiếp 0, 0, 1, 1 hoặc 1, 1, 0, 0, tức là X thuộc loại A khi và chỉ khi B
Vậy f là một song ánh đi từ tập các xâu loại A độ dài n đến tập các xâu loại
B là tập hợp các xâu có độ dài n ≥ 1 bắt đầu bằng số 0 Từ mỗi xâu X trong B, ta có thể tạo ra một xâu mới X' cũng thuộc B bằng cách hoán đổi các phần tử của X theo quy tắc 1 ↔ 0 và 0 ↔ 1 Do đó, số lượng xâu thuộc loại B có độ dài n + 1 gấp đôi số xâu loại B có độ dài n + 1 bắt đầu bằng số 0.
Từ đó ta có điều cần chứng minh.
Bài toán 2.9.2 Tìm bộ 3 số nguyên dương (x,y,z) thỏa mãn đẳng thức x y z 100
Mỗi bộ số nguyên dương (x,y,z) thỏa mãn x y z
Để tạo ra một bộ số gồm 100, chúng ta cần chọn 2 vị trí không kề nhau trong tổng số 102 vị trí để đặt 2 số 0, trong khi các vị trí còn lại sẽ được điền bằng số 1 Hai vị trí này sẽ được ký hiệu là a và b, với điều kiện a và b phải thỏa mãn yêu cầu không kề nhau.
Vì số 0 không thể đứng đầu và cuối trong dãy số, nên số bộ số thỏa mãn yêu cầu của bài toán được tính bằng cách chọn 2 số phân biệt trong 99 số từ 3 đến 101.
Bình luận : Ta có thể tổng quát hóa bài toán 2.9.2 như sau:
1,a 2 , a m ) trong đó a 1,a 2 , a m là các số nguyên dương thỏa mãn m điều kiện a i i1
Bằng cách làm tương tự bài toán 2.9.2 ta thu được kết quả là C m1
Để giải bài toán 2.9.3, ta cần xác định cách chọn 5 số từ tập hợp 18 số nguyên dương đầu tiên, sao cho hiệu số giữa bất kỳ cặp 2 số trong 5 số được chọn luôn lớn hơn hoặc bằng 2 Điều này đảm bảo rằng không có cặp số nào trong bộ 5 số có khoảng cách nhỏ hơn 2, từ đó tạo ra các lựa chọn số phù hợp.
Kí hiệu A đại diện cho tập hợp các bộ số gồm 5 số a1, a2, a3, a4, a5 thỏa mãn các yêu cầu của bài toán Trong khi đó, kí hiệu B là tập hợp các bộ 5 số phân biệt được chọn từ 14 số nguyên dương đầu tiên.
Ta xây dựng ánh xạ : A B theo quy tắc sau: trong đó
Như vậy, với mỗi phần tử của A được ứng với duy nhất một phần tử của B qua ánh xạ
Suy ra phép tương ứng 1-1 giữa A và B luôn tồn tại duy nhất
Vậy số phần tử của A bằng số phần tử của B bằng C 5
Bài toán 2.9.4 yêu cầu xác định số lượng tập con A của tập X = {1, 2, , n} có r phần tử, với điều kiện rằng các phần tử trong A không chứa hai số nguyên liên tiếp Để giải bài toán này, cần xem xét các số nguyên dương n và r sao cho r ≤ n Việc tìm ra số lượng tập con thỏa mãn điều kiện trên sẽ liên quan đến các phương pháp tổ hợp và phân tích đặc điểm của các tập con không liên tiếp.
Gọi là họ các tập con của X có tính chất đã nêu ở trên và là họ tất cả
1 2 các tập con có r phần tử của tập hợp Y 1, 2, , n (r 1) Ta thiết lập một ánh xạ f : như sau:
Giả sử A a 1,a 2 , ,a r 1 Ta có thể giả thiết a 1 a 2 a r Đặt b a (i 1) a i 1, i 1, 2, , r
Ta định nghĩa f (A) B Ta có B , do vậy f là một ánh xạ từ vào
Ta sẽ đi chứng minh f là một song ánh.
+ f là một đơn ánh: Từ công thức b a (i 1) a i 1 , suy ra a i i
+ f là toàn ánh: Giả sử
Xét tập A a 1,a 2 , ,a r , với a i b i i 1 Ta có a a a n r 1 r 1 n, a a b b 1 2
Vậy có tất cả C r các tập hợp con của X có tính chất đã nêu.
Phương pháp song ánh là một công cụ quan trọng trong việc thiết lập và chứng minh các công thức tổ hợp thông qua việc so sánh lực lượng các tập hợp Nguyên tắc cơ bản của phương pháp này là khi đếm số phần tử của một tập hợp bằng nhiều cách khác nhau, kết quả thu được phải đồng nhất.
Sử dụng phương pháp đếm bằng hai cách
Bài toán 2.10.1 Chứng minh rằng với n thì
Ta đếm số cách chọn n phần tử từ một tập gồm 2n phần tử theo hai cách.
Cách thứ nhất: Mỗi lần chọn ra n phần tử, số cách hiển nhiên là C n
Cách thứ hai để chọn k phần tử từ tập 2n phần tử là chia tập này thành hai tập con, mỗi tập gồm n phần tử Từ tập con thứ nhất, ta có C(n, k) cách chọn k phần tử, và từ tập con thứ hai, ta có C(n, n-k) cách chọn n-k phần tử Tổng số cách chọn sẽ được tính bằng công thức C(n, k) * C(n, n-k) cho k chạy từ 0 đến n.
Vậy ta có đẳng thức
Bài toán 2.10.2 Cho n và r là hai số nguyên dương Chứng minh rằng r
Ta xét các dãy x 1, x 2 , , x n r 1 gồm n
Trong một dãy số gồm 1 chữ số 1 và r chữ số 0, chúng ta chú ý đến vị trí của chữ số 1 cuối cùng, tức là vị trí mà bên phải nó không còn chữ số 1 nào khác Vị trí này có thể nằm ở một trong các vị trí n - 1, n - 2, , n - r.
Ta nói một dãy thuộc loại k nếu vị trí của chữ số 1 đứng cuối cùng là n 1 k k 0,1, 2, , r
Để xác định số lượng dãy loại k, ta cần xem xét cấu trúc của dãy số Sau chữ số 1 cuối cùng, sẽ có một dãy gồm r ∩ k chữ số 0, trong khi trước chữ số 1 này là một dãy chứa n ∩ k chữ số.
Có C k dãy gồm n chữ số, trong đó có k chữ số 0 và n chữ số 1 Theo quy tắc cộng, số các dãy gồm n + 1 chữ số 1 và r chữ số 0 là C k.
Mặt khác, dễ thấy có C r k 0 dãy gồm n 1 chữ số 1 và r chữ số 0 (bằng số cách chọn r vị trí cho số 0 trong n r 1 vị trí) Thành thử r
Bài toán 2.10.3 Cho n là số nguyên dương Tính
Tập X gồm n phần tử có thể tạo ra nhiều tập con khác nhau Để xác định số lượng tập con có số phần tử chẵn, ta cần tính toán số lượng các tập con này, tương tự cho số tập con có số phần tử lẻ Kết quả sẽ cho biết rõ ràng số lượng tập con chẵn và lẻ trong tập X.
Gọi là tập hợp các tập con của X với số lượng phần tử chẵn, và là tập hợp các tập con của X với số lượng phần tử lẻ Đầu tiên, khi n là số lẻ, ta xem xét ánh xạ f từ đến với định nghĩa f(A) = A ∩ (X \ A).
Vì X \ A X A n A nên A là chẵn khi và chỉ khi
A là lẻ Vậy f là một song ánh, do đó Mà bằng số các tập con của X và bằng 2 n , nên ta suy ra 2 n1
Tiếp theo, ta xét trường hợp n là số chẵn Lấy phần tử a X và xét tập hợp Y
X \ a Khi đó Y n 1 , do đó Y có một số lẻ các phần tử Mỗi tập con A có một số chẵn phần tử của X gồm hai loại: n n n
Loại 1: a A Khi đó A là tập con có số chẵn phần tử của Y
Loại 2:a A Khi đó A a B , ở đó B là tập con có số lẻ phần tử của
n 1 lẻ nên theo chứng minh trên ta có:
+ Số tập hợp loại 1 bằng số tập con có số chẵn phần tử của Y , do đó là 2 n2
+ Số tập hợp loại 2 bằng số tập con có số lẻ phần tử của Y , do đó là 2 n2 Vậy số tập con có số chẵn phần tử của X là 2n2 2n2 2n1.
Mặt khác, số các tập con của X có 2i phần tử là C n ,i 0,1, 2, , và
số tập con của X có 2i 1 phần tử là C 2i1
Phương pháp đếm bằng hai cách còn giúp ta xử lý được một số bài toán khó Hai bài toán sau là ví dụ minh họa.
Trong bài toán 2.10.4 (IMO – 1998), có m thí sinh và n giám khảo, với n là số nguyên lẻ lớn hơn hoặc bằng 3 Mỗi giám khảo sẽ đánh giá thí sinh là đỗ hoặc trượt Giả sử k là số nguyên biểu thị rằng hai giám khảo bất kỳ có thể đồng ý với nhau về kết quả của tối đa k thí sinh Nhiệm vụ là chứng minh một định lý liên quan đến sự đánh giá của các giám khảo trong kỳ thi này.
Trong bài toán này, chúng ta cần đếm số bộ ba (giám khảo, giám khảo, thí sinh) sao cho hai giám khảo là khác nhau và đều đánh giá thí sinh giống nhau Số lượng cặp giám khảo có thể được tính bằng công thức C(n, 2) và số thí sinh là n Do đó, tổng số bộ ba thỏa mãn điều kiện trên sẽ là C(n, 2) * n.
khảo và mỗi cặp giám khảo như vậy đánh giá trùng nhau tại không quá k thí sinh, do đó N kn(n 1)
Chúng ta sẽ xem xét một thí sinh X và đếm số cặp giám khảo đánh giá giống nhau cho thí sinh này Giả sử có x giám khảo đồng ý cho X đỗ, thì số cặp giám khảo đồng thuận là C(2, x) = x(x - 1)/2 Đồng thời, tổng số cặp giám khảo có thể là C(n, x) = n(n - 1)/2.
2 nx cặp cùng cho X trượt Như vậy sẽ có x(x 1) (n x)(n x
1) 2 cặp đánh giá X giống nhau Ta có x(x 1) (n x)(n x 1) 2x 2 2nx n 2 n n 2 n 2 n
Vì là số nguyên (do n lẻ) nên số cặp đánh giá X giống nhau sẽ ít nhất là
Kết hợp hai bất đẳng thức ta lại có kn(n 1) m(n 1) 2 k n 1
Vậy ta có điều phải chứng minh. m 2n
Bài toán 2.10.5.( IMO-1989 ) Cho n và k là các số nguyên dương, S là tập n điểm trong mặt phẳng thỏa mãn các điều kiện:
(i) Không có 3 điểm nào trong S thẳng hàng;
(ii) Với mọi điểm P thuộc S , tồn tại ít nhất k điểm trong S cách đều P
Lời giải Để thuận lợi, ta gọi một đoạn thẳng nối hai điểm bất kì của S là cạnh Gọi
N là số cạnh trong mặt phẳng được tạo thành từ n điểm của S
Trước hết, vì có n điểm phân biệt và bất kì hai điểm xác định được một cạnh nên ta có N C 2 cạnh.
Mỗi điểm P trong tập hợp S có thể xác định một đường tròn với tâm P, chứa ít nhất k điểm của S Mỗi điểm trên đường tròn này tạo ra ít nhất C2 cạnh Với n điểm P, tổng số cạnh tối thiểu sẽ là nC2, nhưng các cạnh này có thể bị đếm nhiều lần Một cạnh được tính nhiều lần khi nó là dây cung chung của ít nhất hai đường tròn, và do đó, số dây cung chung tối đa giữa n đường tròn chỉ là C2.
Do đó, N nC 2 C 2 Suy ra
2 Vậy ta có điều phải chứng minh.