Bài tập đề nghị
Nếu A = {1, 2} thì tương tự như trên ta cũng chứng minh được rằng không tồn tại tập B thỏa mãn các điều kiện của bài toán.
Như thế y ∈/ A Xét tập B = A ∪ {y} Ta có
Do đó tập B thỏa mãn yêu cầu bài toán. Σ x x∈B Σ x∈
Vậy tất cả các tập A thỏa mãn bài toán là A = {1} hoặc A là tập hữu hạn tùy ý mà phần tử lớn nhất của nó lớn hơn 2.
Bài 1 Cho A là tập con gồm 90 phần tử của {1, 2, , 100} và S là tổng các phần tử của A Tìm số các giá trị có thể có của S.
Cho tập hợp S = {a1, a2, , a12} với 12 phần tử khác nhau, chúng ta cần tạo ra các tập hợp con từ S với điều kiện rằng chỉ số dưới của mỗi phần tử trong tập con phải là bội nguyên của chỉ số dưới nhỏ nhất trong tập hợp đó Ví dụ, tập hợp {a2, a4, a8} và {a6} đều thỏa mãn điều kiện này Vậy có bao nhiêu tập hợp con có thể được tạo thành từ tập hợp S này?
Bài 3 (Toán học tuổi trẻ) Cho số nguyên dương n Tính số các số nguyên dương không lớn hơn n(n+1)(n+2) mà không chia hết cho các số n, n+1, n+2.
Bài 4 Xét tập hợp X = {1, 2, , 2012} Đặt A = {x ∈ X| x − 2 | 29}. a) Tính |A|. b) Tìm số tập con B của X sao cho B ∩ A ƒ= ∅. n
HD b) Kí hiệu P (X) là họ tất cả các tập con của X M = {B ⊂ X| B ∩A ƒ∅} Khi đó
Để xác định số thẻ tối thiểu cần rút ra từ hộp chứa 9 thẻ được đánh số từ 1 đến 9, nhằm đảm bảo xác suất có ít nhất một thẻ ghi số chia hết cho 4 không nhỏ hơn 5, ta cần phân tích các số chia hết cho 4 trong dãy số này Các số chia hết cho 4 trong khoảng từ 1 đến 9 là 4 và 8 Từ đó, ta có thể tính toán để tìm ra số thẻ cần rút tối thiểu để đạt được xác suất mong muốn.
Bài 6 (Toán học tuổi trẻ) Cho 167 tập hợp A 1 , A 2 , , A 167 thỏa mãn các điều kiện
Các bài toán về phép đếm
Một số ví dụ
C k không cần có điều kiện k ≤ n. n n
Trong bài toán này, có ba tổ với số lượng thành viên khác nhau: tổ một có 10 người, tổ hai có 12 người và tổ ba có 15 người Cần tìm số cách chọn ra một nhóm gồm 10 người, trong đó số người từ tổ một không ít hơn 2, số người từ tổ hai cũng không ít hơn 2, và số người từ tổ ba không vượt quá 3.
Để giải bài toán, đầu tiên, chúng ta chọn 2 người từ tổ một với C(2) cách, và 2 người từ tổ hai cũng với C(2) cách Tiếp theo, từ tổ ba, chúng ta lấy ra k người (0 ≤ k ≤ 3) với C(k) cách Sau đó, số người còn lại từ tổ một và tổ hai được gộp lại thành một nhóm 18 người Từ nhóm này, chúng ta sẽ chọn ra 6 - k người.
C 6−k Theo quy tắc nhân, số cách chọn ra 10 người là C 2 C 2 C k C 6−k Cho k chạy từ 10 12 15 18
0 tới 3 và lấy tổng ta thu được số cách chọn thỏa mãn yêu cầu của đề bài là
Ví dụ 14 Giả sử số nguyên dương n có phân tích ra thừa số nguyên tố là n = p n 1 p n 2 ã ã ã p n k
Ta dùng kí hiệu τ n để chỉ số ước nguyên dương của n Chứng minh rằng τ n = (n 1 + 1)(n 2 + 1) ã ã ã (n k + 1).
Mọi ước nguyên dương của một số n đều có dạng p^m1 * p^m2 * * p^mk, trong đó m1, m2, , mk là các số nguyên không âm và 0 ≤ m1 ≤ n1, 0 ≤ m2 ≤ n2, , 0 ≤ mk ≤ nk Số ước nguyên dương của n được xác định bằng số cách chọn bộ (m1, m2, , mk) thỏa mãn các điều kiện này Mỗi mi (i = 1, 2, , k) có n i + 1 cách chọn, do đó số ước nguyên dương của n được tính bằng công thức τ(n) = (n1 + 1)(n2 + 1) (nk + 1).
Trong một hộp chứa 2n viên bi, với n viên bi đỏ giống hệt nhau và n viên bi xanh khác nhau, câu hỏi đặt ra là có bao nhiêu cách khác nhau để lấy ra n viên bi từ hộp.
LỜI GIẢI Công đoạn 1 Ta lấy k (0 ≤ k ≤ n) viên bi từ n viên bi xanh thì có C k cách.
Công đoạn 2 Ta lấy n − k viên bi từ n viên bi đỏ thì chỉ có đúng một cách vì các viên bi này là hoàn toàn giống nhau.
Cho k chạy từ 0 tới n và lấy tổng ta sẽ được số cách lấy thỏa mãn bài toán là Σ n k= 0
Để giải quyết bài toán xếp chỗ cho 10 học sinh nam và 6 học sinh nữ sao cho không có hai em nữ nào ngồi cạnh nhau, ta cần phân tích từng trường hợp cụ thể a) Đối với việc xếp hàng ngang, ta có thể sắp xếp 10 học sinh nam trước, tạo ra 11 khoảng trống cho các em nữ Ta sẽ chọn 6 trong 11 khoảng trống này để đặt các em nữ vào b) Khi xếp quanh bàn tròn, ta cần lưu ý rằng các cách xếp khác nhau chỉ khác nhau về vị trí, không về thứ tự Ta cũng sẽ sắp xếp 10 học sinh nam trước và tính toán số cách đặt 6 học sinh nữ vào các khoảng trống c) Nếu yêu cầu thêm rằng ba bạn Hùng, Hoa và Huệ phải ngồi cạnh nhau, ta sẽ coi ba bạn này là một nhóm và tính toán lại số cách xếp dựa trên nhóm này cùng với các học sinh còn lại.
Để sắp xếp 10 bạn nam, có 10! cách thực hiện Trong số 11 vị trí, cần chọn 6 vị trí cho 6 bạn nữ, có C(6) cách chọn Sau đó, có 6! cách sắp xếp các bạn nữ vào các vị trí đã chọn Theo quy tắc nhân, tổng số cách sắp xếp là 10! * C(6) * 6! Đối với trường hợp hoán vị vòng quanh, 10 bạn nam có 9! cách sắp xếp, và từ 10 vị trí xen kẽ, cần chọn 6 vị trí cho các bạn nữ.
Trong bài toán này, chúng ta có 10 vị trí, trong đó 6 vị trí dành cho 6 bạn nữ, do đó có C(6) cách chọn vị trí cho các bạn nữ Sau đó, có 6! cách để sắp xếp các bạn nữ vào những vị trí đã chọn Tổng số cách xếp thỏa mãn yêu cầu là 9! * C(6) * 6! Để đơn giản hóa, chúng ta "buộc" ba người Hùng, Hoa, Huệ lại với nhau (Hùng phải ở giữa hai người kia) và xem họ như một đơn vị Có 2 cách "buộc" như vậy Khi đó, chúng ta có 9 người nam và 5 người nữ, và áp dụng lý luận tương tự, số cách xếp thỏa mãn yêu cầu sẽ là 2 * 8! * C(5) * 5!.
Một nhóm 9 người, bao gồm 3 đàn ông, 4 phụ nữ và 2 trẻ em, đi xem phim Câu hỏi đặt ra là có bao nhiêu cách sắp xếp họ ngồi trên một hàng ghế, với điều kiện mỗi trẻ em phải ngồi giữa hai phụ nữ và không có hai đàn ông nào ngồi cạnh nhau.
Để sắp xếp 4 người phụ nữ, có 4! cách thực hiện Giữa họ có 3 vị trí xen kẽ và 2 vị trí đầu cuối Từ 3 vị trí xen kẽ, ta chọn 2 vị trí cho 2 đứa trẻ, có C 2 cách Sau đó, có 2! cách để đặt 2 đứa trẻ vào 2 vị trí đã chọn Cuối cùng, 3 vị trí còn lại sẽ được dành cho 3 người đàn ông, với 3! cách sắp xếp Theo quy tắc nhân, tổng số cách sắp xếp thỏa mãn yêu cầu đề bài là tích của các cách trên.
Cho tập hợp S = {1, 2, , 2n}, tập con A của S được gọi là tập cân nếu số lượng số chẵn bằng số lượng số lẻ trong đó, bao gồm cả tập rỗng Vậy, câu hỏi đặt ra là S chứa bao nhiêu tập cân?
LỜI GIẢI Với mỗi k (0 ≤ k ≤ n) ta đếm số tập cân gồm 2k phần tử của S.
Trong tập S có n số chẵn và n số lẻ, nên có C(k) cách chọn k số chẵn và C(k) cách chọn k số lẻ Theo quy tắc nhân, số tập cân gồm 2k phần tử của S được tính là (C(k))^2 Khi k chạy từ 0 đến n và tổng hợp lại, ta sẽ có tổng số tập cân của tập S.
Trong một giải thi đấu bóng bàn với 2n vận động viên, ban tổ chức cần phân chia thành n cặp đấu trong vòng đầu Câu hỏi đặt ra là có bao nhiêu cách để ghép thành n cặp đấu Từ kết quả này, ta cần chứng minh rằng biểu thức (n + 1)(n + 2) (2n − 1)(2n) chia hết cho 2^n với mọi số nguyên dương n.
LỜI GIẢI Công đoạn 1: Chọn 2 người trong 2n người để làm thành cặp đấu thứ nhất thì có C n cách chọn.
Công đoạn 2: Chọn 2 người trong 2n − 2 người còn lại để làm thành cặp đấu thứ hai thì có C n cách chọn.
Công đoạn 3: Chọn 2 người trong 2n − 4 người còn lại để làm thành cặp đấu thứ ba thì có C 2 cách chọn.
Cuối cùng, chúng ta có C(2, 2) cách để chọn 2 người cho cặp đấu thứ n Theo quy tắc nhân, số cách chọn này sẽ được tính toán để đưa ra kết quả chính xác.
C 2 cách chọn n cặp đấu Nhưng vì thứ tự giữa các cặp đấu không được xét đến nên số cách ghép thành n cặp đấu thực sự là
Bằng biến đổi đơn giản ta có
2 n n!2 n phải là một số nguyên.
Ví dụ 20 Cho a = 122233456 Thay đổi thứ tự các chữ số của a thì nhận được bao nhiêu số mà không có hai chữ số 2 đứng cạnh nhau.
LỜI GIẢI Trước tiên ta xếp vị trí cho các chữ số: 1, 3, 3, 4, 5, 6 thì có
Có 5 vị trí xen kẽ và 2 vị trí đầu cuối giữa hai chữ số 2 Do hai chữ số 2 không thể đứng cạnh nhau, ta có C(3, 7) cách chọn 3 trong 7 vị trí để đặt ba chữ số 2 Do đó, số cách sắp xếp cần tìm là 6!.
Ví dụ 21 Cho tập A = {1, 2, 3, 4, 5} Tìm số các số gồm 3 chữ số a, 2 chữ số b và 1 chữ số c sao cho a, b, c ∈ A và khác nhau đôi một.
LỜI GIẢI a có 5 cách chọn, b có 4 cách chọn, c có 3 cách chọn Sau khi chọn xong các số a, b, c thì có 6!
Vậy số số phải tìm là 5.4.3 6!
Bài toán sẽ trở nên phức tạp hơn khi tập A chứa số 0 Để giải quyết, ta áp dụng phương pháp "loại trừ": đầu tiên, xử lý như trường hợp bình thường, coi số 0 như các số khác Sau đó, xem xét riêng trường hợp số 0 đứng ở vị trí đầu tiên, với 3 khả năng: số 0 có thể là a, b, hoặc c Cuối cùng, lấy tổng số đã tính trừ đi trường hợp riêng để có được kết quả cần tìm.
Sử dụng phép đếm để chứng minh các đẳng thức về tổ hợp
2.3 Sử dụng phép đếm để chứng minh các đẳng thức về tổ hợp
Cơ sở lý thuyết của phương pháp này cho rằng nếu một số lượng được đếm theo hai cách khác nhau, thì kết quả thu được từ hai phương pháp đó phải giống nhau.
Ví dụ 23 Với n, k là các số nguyên dương, n ≥ k Chứng minh đẳng thức
LỜI GIẢI Xét một tập hợp X có n phần tử Ta sẽ đếm số tập con gồm k phần tử của X theo hai cách như sau:
• Cách 1 Mỗi cách lấy ra k phần tử từ tập X ta có một tập con gồm k phần tử của X Số tập con như thế là C k
Cách 2 là loại bỏ n − k phần tử từ tập X, từ đó ta sẽ có được k phần tử còn lại, tạo thành một tập con gồm k phần tử.
X Số tập con như vậy sẽ là C n−k
Rõ ràng hai cách đếm khác nhau đều phải cho cùng một kết quả Do đó ta có
C k = C n−k Bài toán được chứng minh. n n
Ví dụ 24 (Đẳng thức Pascal) Với n, k là các số nguyên dương, n > k ≥ 1.
LỜI GIẢI Ta đếm số tập con A gồm k phần tử của tập X = {x 1 , x 2 , , x n } theo hai cách như sau:
• Cách 2 Số tập A được phân làm hai loại:
Loại 1 Gồm những tập chứa phần tử x n Mỗi tập A thuộc loại này cho ta một tập A ′ = A\{x n } là tập con gồm k − 1 phần tử của tập X\{x n }.
Và ngược lại mỗi tập A ′ cho ta một tập A Do đó số tập A thuộc loại này chính bằng số tập A ′ và bằng C k−1 n n n n− 1
Loại 2 bao gồm các tập không chứa phần tử x_n, tức là các phần tử của tập A được chọn từ tập X\{x_n}, với n - 1 phần tử Số lượng tập A thuộc loại này được tính bằng C_k Vì vậy, theo cách 2, tổng số tập A sẽ là C_{k-1} + C_k.
Như vậy ta phải có C k = C k−1 + C k n−1 n−1 n n−1 n−1
Ví dụ 25 (Đẳng thức Vandermonde) Chứng minh rằng
LỜI GIẢI Ta đếm số cách chọn k phần tử từ một tập hợp gồm m + n phần tử theo hai cách.
• Cách 1 Mỗi lần chọn ra k phần tử, số cách chọn như thế hiển nhiên là m+n
Để giải bài toán, trước tiên chúng ta chia tập hợp gồm m + n phần tử thành hai tập con rời nhau: một tập con với m phần tử và một tập con với n phần tử Tiếp theo, từ tập con đầu tiên, ta chọn ra i phần tử với số cách chọn là C(i), và từ tập con thứ hai, ta chọn ra k - i phần tử với số cách chọn là C(k-i) Cuối cùng, khi cho i chạy từ 0 đến m, ta sẽ có tổng số cách chọn cần tìm.
Rõ ràng tất cả các cách đếm khác nhau đều phải cho cùng một kết quả Từ đó suy ra điều phải chứng minh.
Nhận xét 6 Trong đẳng thức Vandermonde, ta cho m = k = n thì thu được
Ví dụ 26 (China 1994) Chứng minh đẳng thức Σ n k=
LỜI GIẢI Ta sẽ đếm số cách chọn n phần tử từ tập hợp X gồm 2n + 1 phần tử. m n n
2.3 Sử dụng phép đếm để chứng minh các đẳng thức 21
• Cách 1 Số cách chọn chính bằng C n
• Cách 2 Chia X thành n cặp và phần tử x Để chọn n phần tử từ X, ta thực hiện theo các bước sau:
Bước 1: Từ n cặp đã chia, ta chọn ra k cặp (0 ≤ k ≤ n) với số cách chọn là C(k) Tiếp theo, từ mỗi cặp, ta chọn một phần tử, dẫn đến tổng số cách chọn là 2^k * C(k).
Bước 2 Trong n − k cặp còn lại, ta chọn ra Σ n − Σ k cặp Chú ý rằng Σ n − Σ k
Do đó ta sẽ chọn x nếu n − k lẻ và không chọn x nếu n − k chẵn Suy ra số cách chọn ở bước này là C n−k [ n − k ]
Sau khi hoàn thành hai bước trên và cho k chạy từ 0 đến n, ta có thể tính số cách chọn n phần tử từ tập X theo cách 2 là đếm, điều này cần được chứng minh Σ n k= 0.
So sánh kết quả ở hai cách
Ví dụ 27 (Định lý khai triển nhị thức) Chứng minh rằng với mọi số nguyên dương n ta có
LỜI GIẢI Ta có biểu diễn hình thức
Khi thực hiện phép khai triển biểu thức (x + y) n, ta có thể biểu diễn nó dưới dạng tổng hợp các số hạng c 1, c 2, , c n, trong đó có tất cả 2 n số hạng với c i ∈ {x, y} Để rút gọn biểu thức, cần nhóm tất cả các số hạng có cùng số mũ của x và y lại với nhau Đối với mỗi k (0 ≤ k ≤ n), số lượng các số hạng x n−k y k tương ứng với số cách chọn k thừa số (x + y) từ n thừa số (x + y).
2.3 Sử dụng phép đếm để chứng minh các đẳng thức 22 Σ n k=0 C k n x n−k y k
Ví dụ 28 Chứng minh đẳng thức sau với mọi số nguyên dương n,
Để đếm số cặp (x, A) với x ∈ X và A là một tập con của X\{x}, ta nhận thấy rằng n là số cách chọn một phần tử từ tập n phần tử, trong khi 2^(n−1) là số tập con của tập gồm n−1 phần tử.
• Cách 1 Ta có n cách chọn x, với mỗi cách chọn x thì có 2 n−1 cách chọn
A Theo quy tắc nhân ta có n2 n−1 cặp (x, A).
Cách 2 để chọn tập con A gồm k (0 ≤ k ≤ n − 1) phần tử từ X được tính bằng số cách C k = C n−k Đối với mỗi cách chọn A, có n − k cách chọn x ∈ X\A Khi k chạy từ 0 đến n − 1, tổng số cách chọn cặp (x, A) theo cách 2 được tính bằng công thức Σ(n − k)C n−1 n−k = C 1 + 2C 2 + 3C 3 + + nC n.
So sách kết quả của hai cách đếm ta có điều phải chứng minh.
Ví dụ 29 Chứng minh đẳng thức sau với n ≥ k ≥ 0 là các số nguyên
Để chứng minh đẳng thức, ta nhận thấy rằng C(k, n) là số tập con gồm k phần tử từ một tập n phần tử, trong khi 2^k là số tập con của một tập k phần tử Vì vậy, ta sẽ xem xét tập X với |X| = n và đếm số cặp (A, M), trong đó A là tập con gồm k phần tử của X và M là một tập con của A.
• Cách 1 Ta có C k cách chọn tập A, với mỗi cách chọn A thì có 2 k cách chọn M nên có tất cả là 2 k C k cặp (A, M ).
Để tính số cặp (A, M), trước tiên chọn tập M, sau đó chọn k - i phần tử từ n - i phần tử còn lại Với mỗi giá trị i từ 0 đến k, số cách chọn cặp được tính bằng C(i) * C(k - i) Tổng số cặp là Σ(k, i) C(i) * C(k - i).
2.3 Sử dụng phép đếm để chứng minh các đẳng thức 23
Như vậy ta có đẳng thức Σ k i k−i k k i=0 C2 k C n−i = C n
Ví dụ 30 Chứng minh rằng với mọi số nguyên dương n ta có đẳng thức
LỜI GIẢI Ta xét hai tập rời nhau X 1 , X 2 với |X 1| = |X 2| = n và hãy đếm số cặp (x, A), trong đó x ∈ X 1 , còn A là một tập con bất kì gồm n − 1 phần tử của tập X = X 1 ∪ X 2\{x}.
• Cách 1 Để chọn x ta có n cách, với mỗi cách chọn x thì có C n−1 cách chọn A Do đó theo quy tắc nhân thì có tất cả là nC n−1 cách chọn cặp (x, A).
Để chọn cặp (x, A) theo cách 2, ta lấy k phần tử từ tập X1 với C(k) cách, sau đó chọn x từ k phần tử này, có k cách Sau khi chọn x, còn lại k - 1 phần tử Tiếp theo, chọn n - k phần tử từ tập X2, có C(n-k) cách Kết hợp với k - 1 phần tử đã chọn, ta có tập con A gồm n - 1 phần tử của X Do đó, với mỗi giá trị k, số cách chọn cặp (x, A) là k * C(k) * C(n-k) Khi k chạy từ 1 đến n, tổng số cách chọn cặp (x, A) được tính bằng công thức trên.
Từ hai kết quả của hai cách đếm ta suy ra điều phải chứng minh.
Hoán vị bảo tồn i ∈ S là hoán vị mà phần tử i giữ nguyên vị trí trong tập S = {1, 2, , n} Số lượng hoán vị bảo tồn đúng k phần tử của S được ký hiệu là P n (k) Chứng minh rằng P n (k) có những tính chất đặc biệt trong lý thuyết tổ hợp.
LỜI GIẢI (i) Với mỗi k (1 ≤ k ≤ n) ta đi đếm số cặp (i, f ) trong đó f bảo tồn đúng k vị trí và f (i) = i.
Bài tập đề nghị
Cách 1 Ta có số cách chọn i là k và số cách chọn f là P n (k) nên số cặp (i, f ) là kP n (k).
Khi xét i là một phần tử cố định (tức là f(i) = i), ta có một hoán vị bảo tồn k − 1 phần tử của tập S' = S\{i} Mỗi hoán vị bảo tồn k − 1 phần tử của S' khi bổ sung thêm i sẽ tạo ra một hoán vị bảo tồn k phần tử của tập S Với n cách chọn i và P(n−1)(k − 1) hoán vị bảo tồn k − 1 phần tử của S', số cặp (i, f) sẽ là nP(n−1)(k − 1).
Từ kết quả của hai cách đếm trên ta suy ra kP n (k) = nP n−1(k − 1).
(ii) Theo kết quả trên ta có Σ n k=
Số hoán vị của tập B gồm n − 1 phần tử, trong đó bảo tồn các phần tử 0, 1, , n − 1, được tính bằng Mà P n−1(0) + P n−1(1) + + P n−1(n − 1) Tổng này chính là số hoán vị của tập B và bằng (n − 1)! Do đó, ta có Σ n k =
Bài 7 Tổ một có 10 người, tổ hai có 9 người Hỏi có bao nhiêu cách chọn một nhóm gồm 8 người sao cho mỗi tổ có ít nhất 2 người.
Trong một buổi liên hoan có 6 cặp nam nữ, bao gồm 3 cặp vợ chồng Để tổ chức buổi liên hoan, cần chọn 3 người sao cho không có cặp vợ chồng nào trong số những người được chọn Câu hỏi đặt ra là có bao nhiêu cách chọn 3 người đáp ứng điều kiện này.
Bài 9 Có bao nhiêu cách chia 100 đồ vật giống nhau cho 4 người sao cho mỗi người được ít nhất một đồ vật.
Bài 10 Cho tập hợp S = {a 1 , a 2 , , a 20} Có bao nhiêu tập con của S gồm 3 phần tử mà trong đó không có hai phần tử nào cạnh nhau? ĐS: C 3 − 18 2
Bài 11 Cho phương trình x 1 + x 2 + x 3 + x 4 = 15 (1) a) Tìm số nghiệm nguyên không âm của của (1) thỏa mãn điều kiện x 1 ≤ 3. b) Tìm số nghiệm nguyên không âm của của (1) thỏa mãn điều kiện x 1 ≤
Bài 12 Tìm số nghiệm nguyên của phương trình x + y + z = 10 thỏa mãn điều kiện 1 ≤ x ≤ 3, 2 ≤ y ≤ 7, 4 ≤ y ≤ 8.
Bài 13 Tìm số nghiệm nguyên không âm của bất phương trình x 1 + x 2 + x 3 + x 4 ≤ 11.
Bài 14 Tìm số nghiệm nguyên không âm của hệ
.x 1 + x 2 + x 3 + x 4 ≤ 12 x 1 ≤ 4 Bài 15 Có tất cả bao nhiêu bộ bốn số nguyên (a, b, c, d) thỏa mãn a + b + c + d = 100, a ≥ 30, b > 21, c ≥ 1, d ≥ 1.
Bài 16 (Toán học tuổi trẻ) Cho các số nguyên dương m, n, k với n > m.
Chứng minh rằng số các nghiệm nguyên dương của hệ
Bài 17 Có bao nhiêu số nguyên dương nhỏ hơn 1000.000 mà tổng các chữ số của nó bằng 19.
Bài 18 đề cập đến các bài toán về xâu nhị phân với các điều kiện cụ thể a) Có bao nhiêu xâu nhị phân chứa đúng tám số 0 và mười số 1, trong đó mỗi số 0 phải ngay sau là một số 1 b) Có bao nhiêu xâu nhị phân chứa đúng năm số 0 và mười bốn số 1, với điều kiện mỗi số 0 phải ngay sau là hai số 1 liên tiếp c) Có bao nhiêu xâu nhị phân độ dài 10 chứa ít nhất ba số 0 và ba số 1.
Bài 19 Cho tam giác ABC Xét tập hợp gồm 5 đường thẳng song song với
Trong bài toán này, có 6 đường thẳng song song với BC và 7 đường thẳng song song với CA Các đường thẳng này tạo ra tổng cộng 675 hình bình hành và 1575 hình thang.
Bài 20 Cho A = {1, 2, 3, 4, 5, 6} Tìm số các số gồm 4 chữ số của A sao cho có đúng 2 chữ số bằng nhau.
Bài 21 Có bao nhiêu cách đảo chữ MATHEMATICAL sao cho 2 nguyên âm không đứng cạnh nhau.
Bài 22 (Toán học tuổi trẻ) Co bao nhiêu số tự nhiên gồm 6 chữ số khác nhau trong đó hai chữ số kề nhau không cùng là số lẻ. ĐS: 37800.
Bài 23 Cho a = 102011333557799 Thay đổi vị trí các chữ số của a thì nhận được bao nhiêu số mà 2 chữ số chẵn không đứng cạnh nhau.
Bài 24 Cho A = {0, 1, 2, 3, 4, 5} Có bao nhiêu số gồm 3 chữ số a, 2 chữ số b với a, b ∈ A và a ƒ= b.
Bài 25 yêu cầu tìm số cách thay đổi vị trí các chữ số của a = 11223334444 sao cho hai chữ số 1 và hai chữ số 2 không đứng cạnh nhau Bài 26 có hai phần: a) Tính số ngũ giác có 5 cạnh là 5 đường chéo trong một đa giác đều 16 đỉnh; b) Tính số tam giác có 3 đỉnh không kề nhau trong một đa giác đều n (n ≥ 6) đỉnh.
Bài 27 (Toán học tuổi trẻ) Có bao nhiêu số tự nhiên có 9 chữ số, trong đó có
3 chữ số lẻ khác nhau và 3 chữ số chẵn khác nhau mà mỗi chữ số chẵn có mặt đúng hai lần. ĐS: 3931200.
Bài 28 đề cập đến việc sắp xếp chỗ ngồi cho n học sinh trường A và n học sinh trường B trên một bàn dài với hai dãy ghế đối diện nhau Trong trường hợp a), yêu cầu là hai học sinh bất kỳ ngồi cạnh nhau hoặc đối diện nhau phải thuộc khác trường, dẫn đến tổng số cách sắp xếp là 2(n!)^2 Trong trường hợp b), khi hai học sinh ngồi đối diện phải khác trường, số cách sắp xếp được tính bằng công thức [(2n).n][(2n−2)(n−1)][(2n−4)(n−2)] [2.1] (2n)!!.n!.
Các bài toán về số tổ hợp, chỉnh hợp và hoán vị
Chứng minh các hệ thức về số tổ hợp, chỉnh hợp và hoán vị
Ví dụ 32 a) Chứng minh rằng
C k = C k−1 + C k−1 + ã ã ã + C k−1 b) Áp dụng kết quả trên hãy tính các tổng quen thuộc sau
LỜI GIẢI a) Chỉ cần áp dụng liên tiếp công thức C k = C k−1 + C k b) Ta có S 1 =Σ n C 1 = C 2 n n(n + 1)
3.1 Chứng minh các hệ thức về số tổ hợp, chỉnh hợp 2 9
Nhận xét 7 Bằng phương pháp tương tự ta thu được các đẳng thức sau
Ví dụ 33 Tìm giá trị lớn nhất trong các giá trị C 0 , C 1 , C 2 , , C n n n n n
LỜI GIẢI Đặt a k = C k , k = 0, n Xét bất phương trình (ẩn số k) sau k k+1 n − 1 a ≤ a ⇔ C ≤ C ⇔ k ≤
Nếu n là số chẵn thì ta có
a0 < a1 < ã ã ã < a 2[ n − 1 ] < a 2 [ n − 1 ] +1 (do đẳng thức khụng xảy ra).
Nếu n là số lẻ thì ta có
Vậy trong trường hợp này thì a n +1 2 > ã ã ã > a n−1 > a n max.
3.1 Chứng minh các hệ thức về số tổ hợp, chỉnh hợp 3 9
3.1 Chứng minh các hệ thức về số tổ hợp, chỉnh hợp 30
Ví dụ 34 Chứng minh rằng Σ n C k 1
LỜI GIẢI Bằng tính toán trực tiếp ta có
Ví dụ 35 Chứng minh rằng với n 1 , n 2 , , n k và n là các số nguyên không âm thỏa món n 1 + n 2 + ã ã ã + n k ≤ n thỡ n! n 1! n 2! n k ! là một số nguyên dương.
LỜI GIẢI Ta biến đổi như sau n !
Ví dụ 36 Tìm giới hạn lim 1 Σ n
3.1 Chứng minh các hệ thức về số tổ hợp, chỉnh hợp 30 k=0
3.1 Chứng minh các hệ thức về số tổ hợp, chỉnh hợp 31
Sử dụng nguyên lý "kẹp" ta có
Ví dụ 37 Cho dãy số (u n ) xác định như sau: u 4 = 1, u n+1 = u n + 1.(n − 2) + 2(n − 3) + ã ã ã + (n − 2).1 ∀n ≥ 4.
LỜI GIẢI Không khó để thấy rằng
Do đó dãy số đã cho có thể viết lại thành u n+1 = u n + C 3 u n = u n−1 +
Cộng tất cả các đẳng thức trên vế theo vế ta thu được u n+1 = 1 + C 3 + ã ã ã +
(theo kết quả của ví dụ (32)).
Ví dụ 38 Chứng minh rằng C 500 không chia hết cho 7.
Chỉ số mũ lớn nhất của thừa số nguyên tố p trong phân tích chính tắc của số nguyên dương a được ký hiệu là v p (a), với α là số lớn nhất sao cho p α chia hết cho a Theo công thức, v p (n!) có thể được tính bằng tổng các giá trị n chia cho các lũy thừa của p, cụ thể là Σ (n/p) + Σ (n/p²) + cho đến khi n/p^k không còn lớn hơn 0.
= 164. v 7(C 500 ) = v 7(1000!) − v 7((500!) 2 ) = 0 Điều này có nghĩa là khi phân tích C 500 ra thừa số nguyên tố thì không chứa
7 Vì vậy C 500 không chia hết cho 7.
Ví dụ 39.ΣChΣo p là số nguyên tố và n là số nguyên dương, n ≥ p Chứng minh n rằng C p p chia hết cho p.
1.2.3 ã ã ã p tiếp n, n − 1, n − 2, , n − p + 1 chỉ có đúng một số chia hết cho p, ta kí hiệu số đó là m Thế thì n − p + 1 ≤ m ≤ n hay n
Chú ý rằng, khi chia các số n, n − 1, , m + 1, m − 1, , n − p + 1 cho p chúng ta nhận được tất cả các số dư là 1, 2, , p − 1 Từ đó suy ra n(n − 1) ã ã ã (m + 1)(m − 1) ã ã ã (n − p + 1) ≡ (p − 1)! (mod p)
Vì m p là số nguyên nên đẳng thức trên kéo theo n ( n − 1) ã ã ã ( m + 1) m ( m − 1) ã ã ã ( n − p + 1)
Lại do (p − 1)! và p nguyên tố cùng nhau nên giản ước (p − 1)! ở hai vế của đẳng thức trên ta được n ( n − 1) ã ã ã ( m + 1) 1) m ( m − 1) ã ã ã ( n − p +
(mod p) và đó chính là điều chúng ta cần chứng minh.
Ví dụ 40 Chứng minh rằng p là số nguyên tố khi và chỉ khi p |C k ∀k ∈ {1, 2, , p − 1}.
LỜI GIẢI a) Điều kiện cần: Giả sử p là số nguyên tố Ta có
Đối với số nguyên tố p, ta có thể suy ra rằng (p - 1)! chia hết cho k!(p - k)! Điều này dẫn đến việc khẳng định rằng (p - 1)!/(k!(p - k)!) là một số nguyên.
! p p p p p p b) Điều kiện đủ: Giả sử p là số nguyên > 1 và thỏa mãn p |C k ∀k ∈
Để chứng minh rằng p là số nguyên tố, ta giả sử p là hợp số, nghĩa là p có một ước số nguyên tố q Dựa vào giả thiết này, ta có thể rút ra những kết luận quan trọng về tính chất của p.
Nhưng do q nguyên tố nên phải tồn tại i (1 ≤ i ≤ q − 1) sao cho p − i q Mà lại có p q Suy ra i q Đó là điều vô lý Vậy p không thể là hợp số.
Bài toán được chứng minh hoàn toàn.
Ví dụ 41 Cho n ≥ k là các số nguyên dương Chứng minh rằng
C k ) là ước số chung lớn nhất của C k ,
Như thế chứng tỏ d là một ước chung của C k−1 , C k−1 , , C k−1 Do đó n
Lại tiến hành lập luận tương tự như trên chúng ta có p k k n n+
Nhị thức Newton và bài toán tổng tổ hợp
3.2 Nhị thức Newton và bài toán tổng tổ hợp
Trong phần này, ngoài các công thức đã có trong SGK thì các công thức sau đây (xem như các bổ đề) rất hay được sử dụng
Công thức tiếp theo là sự mở rộng thực sự của khai triển nhị thức Newton
1 2 k n 1 +n 2 +ããã+n k =n n 1!n 2! n k ! 1 2 k (ở đây tổng lấy theo mọi cách chọn bộ k số nguyên không âm có tổng bằng n).
Nhận xét 8 C k chính là hệ số của x k trong khai triển nhị thức (1 + x) n còn
(−1) k C k là hệ số của x k trong khai triển nhị thức (1 − x) n Nhận xét này tuy đơn giản nhưng có ích trong một số bài toán. n n
3.2 Nhị thức Newton và bài toán tổng 36
Vớ dụ 43 Tớnh tổng S = 1C 1 + 2C 2 + ã ã ã + nC n (1).
LỜI GIẢI 1 Áp dụng công thức C k = C n−k , ta viết lại tổng đã cho như sau n n
Cộng (1) với (2) vế theo vế ta thu được
LỜI GIẢI 2 Áp dụng công thức kC k = nC k−1 ta có Σ n
C n LỜI GIẢI Áp dụng công thức
Vớ dụ 45 Tớnh tổng S = 1.2C 2 + 2.3C 3 + ã ã ã + (n − 1)nC n n n n
Ví dụ 47 Chứng minh rằng
Ví dụ 49 Tìm hệ số của x 8 trong khai triển thành đa thức của [1 + x 2 (1 − x)] 8 LỜI GIẢI 1 Theo công thức khai triển nhị thúc Newton ta có
Ta phải tìm các số nguyên không âm m và k thỏa mãn
Vậy hệ số của x 8 cần tìm bằng C 4 C 0 + C 3 C 2 = 238.
LỜI GIẢI 2 Theo công thức mở rộng của khai triển nhị thức Newton ta có Σ
Cho 2m + 3k = 8 với m, k là các số nguyên không âm ta tìm được
Vậy hệ số của x 8 cần tìm bằng 8!
Ví dụ 50 Chứng minh đồng nhất thức Vandermonde
Từ đó suy ra hệ số của x k trong khai triển này là
Hệ số x k trong khai triển này là C k
Rõ ràng hệ số của x k trong khai triển của (1 + x) m+n theo hai cách như trên phải bằng nhau Nghĩa là ta có
3.2 Nhị thức Newton và bài toán tổng 40
2n (theo đồng nhất thức Vandermonde).
Ví dụ 52 Chứng minh rằng
LỜI GIẢI Áp dụng đồng nhất thức Newton ta có Σ k Σ k
Ví dụ 53 Tìm hệ số của x 50 trong khai triển thành đa thức của a) (1 + x) + 2(1 + x) 2 + 3(1 + x) 3 + ã ã ã + 1000(1 + x) 1000 b) (1 + x) 1000 + x(1 + x) 999 + x 2 (1 + x) 998 + ã ã ã + x 1000
LỜI GIẢI a) Hệ số của x 50 là Σ100 0 k kC 5
3.2 Nhị thức Newton và bài toán tổng 40 Σ 1000 50 k kP Σ100 0 k=5
Nhị thức Newton và số phức
Nhận xét 9 Sử dụng đẳng thức với a n−
2 + b n−1 a n − b n a − b a = 1 + x, b = x thì ở ý b), biểu thức đã cho chính là (1 + x) 1001 − x 1001 Từ đó ta có cách làm đơn giản hơn lời giải trên.
3.3 Nhị thức Newton và số phức
Trong phần này ta có một kết quả đáng chú sau đây
2 kπ + i sin n , k = 0, 1, , n − 1 S m ε m + ε m + ã ã ã + ε m Khi đó ta có
S m 0 nếu m không là bội của n.
= 1 khi và chỉ khi m chia hết cho n nên ta có hai khả năng sau
• Nếu m là bội của n thì ε m = (α k ) m = (α m ) k = 1 Do đó S m = n.
• Nếu m không là bội của n thì
Từ đó ta có kết luận như trên.
Ví dụ 55 Tính (thu gọn) các tổng sau
3.3 Nhị thức Newton và số 42
LỜI GIẢI A và B có thể viết lại như sau
4 si n π nπ) 4) 4n = 2 2n (cos nπ + i sin Đồng nhất phần thực và phần ảo ta được
Ví dụ 56 Tính (thu gọn) các tổng sau
Theo kết quả của ví dụ (54) ta có ε k = 1
3 3 khi và chỉ khi k chia hết cho 3, và 1 + ε k + ε 2k = 0 với mọi k không là bội của
3 Ta xét các khai triển sau đây
Không khó khăn để thấy rằng
Mặt khác ta cũng có
Chúng ta xét thêm một ví dụ nữa để hiểu rõ hơn về dạng toán này
LỜI GIẢI Xét số phức ε = cos 2π
3 ε k = 1 khi và chỉ khi k là bội của 6, và với mọi k không chia hết cho 6 thì
Sau khi tính toán, thu gọn ta được
Sử dụng đạo hàm, tích phân và nhị thức Newton để xây dựng các đẳng thức tổ hợp
3.4 Sử dụng đạo hàm, tích phân và nhị thức New- ton để xây dựng các đẳng thức tổ hợp
Xuất phát từ đẳng thức
Lấy đạo hàm (theo x) hai vế của (3.4.1) ta được n(1 + x) n−1 = C 1 + 2xC 2 + 3x 2 C 3 + ã ã ã + nx n−1 C n
Từ (3.4.2) ta cho x nhận những giá trị cụ thể sẽ thu được một số đẳng thức
Chẳng hạn, cho x = 1 thì nhận được
Nếu cho x = −1 thì lại được
Trong (3.4.2) ta thay x bởi x − 1 thì có đẳng thức sau
C 1 + 2(x − 1)C 2 + 3(x − 1) 2 C 3 + ã ã ã + n(x − 1) n−1 C n = n.x n−1 Đến đây, ta thay x bởi cos 2x thì được
Từ (3.4.2) lại tiếp tục lấy đạo hàm hai vế ta có n(n − 1)(1 + x) n−2 = 2C 2 + 2.3xC 3 + 3.4x 2 C 4 + ã ã ã + (n −
Trong (3.4.3), lần lượt cho x nhận các giá trị 1, −1, − 1
, chúng ta thu được các đẳng thức sau
3.4 Sử dụng đạo hàm, tích phân và nhị thức Newton để xây dựng các đẳng thức tổ hợ 45
3.4 Sử dụng đạo hàm, tích phân và nhị thức Newton để xây dựng các đẳng thức tổ hợ 45
Lại xuất phát từ (3.4.1),(3.4.2), ta thay x bởi tan 2 x thì thu được
C 1 + 2C 2 tan 2 x + 3C 3 tan 4 x + ã ã ã + nC n ta x = n n n n n sin 2n−2 x
Còn nếu thay x bởi cot 2 x thì thu được
Mặt khác, nếu lấy tích phân từ a đến b hai vế của (3.4.1) ta có
Trong (3.4.4), thay a, b bằng các giá trị cụ thể sẽ thu được một số đẳng thức Chẳng hạn, khi cho a = 0, b = 1 thì được
C n Còn nếu cho a = 1, b = 2 thì được n + 1.
3.4 Sử dụng đạo hàm, tích phân và nhị thức Newton để xây dựng các đẳng thức tổ hợ 46
Nhân cả hai vế của (3.4.1) với x sau đó lấy tích phân hai vế ta có
− n + 1 Đến đây, cho a = 0, b = 1 ta nhận được Σ n k= 0
Còn nếu cho a = 1, b = 2 thì được Σ n k=
Tương tự như trên, cũng nhân cả hai vế của (3.4.2) với x rồi lấy tích phân hai vế ta có
Trong (3.4.6), ta cho a = 0, b = 1 thì được Σ n k=
Lại từ (3.4.1), lấy tích phân lần thứ nhất ta có hay
Tiếp tục lấy tích phân hai vế của đẳng thức này, ta có
Còn nếu tiếp tục lấy tích phân hai vế của đẳng thức trên, ta lại có Σ n
Trong (3.4.1), ta thay x bởi 1 x thì có
Lấy tích phân hai vế ta được hay
Trong (3.4.7) cho a = −1, b = 1 chúng ta có hay viết tường minh là Σ n k=
Xuất phát từ đẳng thức
Mặt khác, theo công thức khai triển nhị thức Newton ta lại có
Từ hai điều trên suy ra
Chú ý rằng đẳng thức này đúng với mọi giá trị của x (kể cả trường hợp x 0) Lấy tích phân hai vế ta có Σ n−1 ∫ b Σ n
Từ đây cho a = 0, b = 1 thì thu được hay viết tường minh là Σ n k=
Bài tập đề nghị
Bài 29 Chứng minh các đẳng thức sau a) C k + 4C k−1 + 6C k−2 + 4C k−3 + C k−4 = C k ; n b) 1
Bài 31 Tìm hệ số của x 9 trong khai triển thành đa thức của [1 + x 2 (1 − x)] 10
Bài 32 Tìm số hạng không phụ thuộc x trong khai triển thành đa thức của
Bài 33 Tìm hệ số có giá trị lớn nhất trong khai triển đa thức
Bài 34 a) Tìm hệ số của số hạng chứa x 3 y 2 z 2 trong khai triển thành đa thức của
(x + 2y − 3z) 7 b) Tìm số hạng không chứa x trong khai triển của
Bài 35 Tìm số nguyên dương n để hệ số có giá trị lớn nhất trong khai triển
Bài 36 (ĐHQGHN khối A, 2000) Chứng minh rằng với mọi số nguyên
3.5 Bài tập đề 51 Bài 37 Chứng minh rằng với mọi số nguyên 0 ≤ k ≤ n, n
Bài 38 Tìm số hạng chứa a, b có số mũ bằng nhau trong khai triển của
Bài 39 Giả sử (1 + x + x 3 + x 4 ) 4 = a 0 + a 1 x + a 2 x 2 + ã ã ã + a 16 x 16 Tỡm giá trị của a 10
Bài 40 a) Tìm các số hạng nguyên trong khai triển của (√
4 3) 128 có bao nhiêu số hạng là số nguyên.
Bài 41 Chứng minh rằng tổng các hệ số của các lũy thừa bậc nguyên dương
1 Σ 23 x thành đa thức là một số chính phương.
Bài 42 Tìm số nguyên dương n sao cho
Bài 44 Chứng minh đẳng thức
HD: Xuất phát từ đẳng thức (1 + x) 2n (1 − x) 2n = (1 − x 2 ) 2n sau đó đồng nhất hệ số của x 2n ở hai vế.
Bài 45 Thu gọn các tổng sau đây n 2
Bài 46 Tìm số nguyên dương n thỏa mãn
Bài 47 Chứng minh đẳng thức Σ n k=
Bài 48 Với n là số nguyên lẻ, n ≥ 5 Chứng minh rằng
5 n−1 C 0 n − 5 n−2 C 1 n + 5 n−3 C 2 n − ã ã ã + C n n−1 không là một số nguyên tố.
Bài 49 Chứng minh các đẳng thức sau a) Σ n (−1) k−1 k k−1 k=1 2k − 1 C n C n+k−1 = 1. b) Σ n (−1) k−1 k n k
Bài 52 Chứng minh các hệ thức sau
Chú ý Từ các đẳng thức trên suy ra
Bài 56 (Toán học tuổi trẻ) Chứng minh rằng với mọi số tự nhiên n ≥ 2 ta luôn có Σ n−1 2(n−k)
Bài 57 Cho hàm số f xác định trên tập các số nguyên dương thỏa mãn f (4) = 1 và f (n + 1) = f
1 k(n − k − 1) với mọi n ≥ 4. a) Tìm tất cả các số nguyên dương n để 24f (n) là một số chính phương. b) Tìm giới hạn lim n→∞ f (n) n 4
HD: Sử dụng bất đẳng thức
Bài 60 (Mathematical Reflections) Với số nguyên dương n, chứng minh rằng mỗi ước số chung lẻ của các số
Một số bài toán tổ hợp nâng cao
Các bài toán sử dụng quan hệ truy hồi
Trong mặt phẳng, nếu có n đường thẳng cắt nhau đôi một và không có ba đường thẳng nào đồng quy, thì số miền mà chúng tạo ra được tính theo công thức: S(n) = n(n + 1)/2 + 1 Công thức này cho thấy rằng mỗi đường thẳng mới sẽ cắt tất cả các đường thẳng trước đó, tạo ra thêm nhiều miền mới trong mặt phẳng.
Số miền F(n) do n đường thẳng tạo ra được xác định dựa trên việc xét n + 1 đường thẳng bất kỳ Khi có một đường thẳng d cắt n đường thẳng còn lại tại n điểm phân biệt, đường thẳng d sẽ được chia thành n + 1 phần Kết quả là, đường thẳng d đi qua n + 1 miền, và mỗi miền này lại được chia làm đôi, tạo ra thêm n + 1 miền mới.
Từ công thức truy hồi này, với chú ý rằng F (1) = 2, ta dễ dàng tìm được (công thức tổng quát)
Bài toán tháp Hà Nội là một bài toán thú vị với ba chiếc cọc và n đĩa có đường kính khác nhau Mục tiêu là chuyển tất cả các đĩa từ cọc thứ nhất sang cọc thứ hai, đảm bảo rằng các đĩa luôn được xếp theo thứ tự từ lớn đến nhỏ Trong quá trình di chuyển, cần lưu ý rằng không được phép đặt đĩa lớn lên trên đĩa nhỏ, điều này nhấn mạnh tầm quan trọng của việc tuân thủ quy tắc trong bài toán.
Để chuyển toàn bộ đĩa từ cọc thứ nhất sang cọc thứ hai với sự hỗ trợ của cọc thứ ba, bài toán yêu cầu xác định số lần ít nhất cần thực hiện.
Để chuyển n chiếc đĩa từ cọc một sang cọc hai, ký hiệu M n là số lần tối thiểu cần thiết Để di chuyển chiếc đĩa dưới cùng sang cọc hai, ta cần chuyển n − 1 đĩa ở trên sang cọc ba, với số lần chuyển tối thiểu là M n−1 Sau đó, cần thực hiện thêm một lần chuyển chiếc đĩa lớn nhất sang cọc hai.
M n−1 lần chuyển n − 1 đĩa từ cọc ba về cọc hai Như vậy ta có
Từ công thức truy hồi này, ta dễ dàng tìm được
Ví dụ 60 (Bài toán chia kẹo Euler) Cho m và n là các số nguyên dương Xét phương trình nghiệm nguyên x 1 + x 2 + ã ã ã + x n = m.
Phương trình trên có bao nhiêu nghiệm nguyên không âm?
LỜI GIẢI Kí hiệu S(n, m) là số nghiệm nguyên không âm của phương trình đã cho Phương trình tương đương với x 1 + x 2 + ã ã ã + x n−1 = m − x n
Từ công thức truy hồi này và bằng quy nạp, ta chứng minh được rằng
Trong bài toán này, chúng ta cần xác định số lượng xâu kí tự có độ dài n, được tạo thành từ các ký tự a_i thuộc tập hợp {0, 1, , 9}, sao cho số lần xuất hiện của ký tự '0' trong xâu là một số chẵn Việc này liên quan đến việc tính toán các tổ hợp và xác suất, đồng thời áp dụng các quy tắc trong lý thuyết số.
LỜI GIẢI Gọi S(n) là tổng số xâu kí tự độ dài n mà số lần xuất hiện của số
0 là một số chẵn Dễ thấy S(1) = 9 Xét xâu kí tự a 1 a 2 a n thỏa mãn yêu cầu đề bài Có hai khả năng sau:
Nếu a1 = 0, thì a2, a3, , an phải tạo thành một xâu kí tự có độ dài n - 1, trong đó số lần xuất hiện của 0 là một số lẻ Các số ai thuộc tập {0, 1, , 9} với i từ 2 đến 9, dẫn đến tổng số có 10^(n-1) xâu kí tự khác nhau có độ dài n - 1 Do đó, ta có S(n).
Có tổng cộng 10^(n−1) xâu ký tự độ dài n−1 mà số lần xuất hiện của ký tự '0' là số chẵn Ngược lại, số xâu ký tự độ dài n−1 mà số lần xuất hiện của ký tự '0' là số lẻ là S(n−1).
Trong trường hợp 2, nếu a1 thuộc tập {1, 2, , 9}, thì a1 có 9 lựa chọn Đồng thời, xâu kí tự có độ dài n - 1, tức là a2 a3 an, phải đảm bảo rằng số lần xuất hiện của số 0 là số chẵn Do đó, số xâu kí tự có độ dài n thỏa mãn điều kiện này sẽ bằng với số xâu kí tự có độ dài n - 1 cũng thỏa mãn yêu cầu.
Do vậy ta có quan hệ
Giải phương trình truy hồi này với chú ý S(1) = 9 ta tìm được
Ví dụ 62 (Bungari, 1995) Cho số nguyên dương n ≥ 2 Hãy tìm số các hoán vị (a 1 , a 2 , , a n ) của 1, 2, , n sao cho tồn tại duy nhất một chỉ số i ∈ {1, 2, , n − 1} thỏa mãn a i > a i+1
Số các hoán vị thỏa mãn yêu cầu được ký hiệu là S n Trong đó, số hoán vị với a n = n là S n−1, và số hoán vị (a 1, a 2, , a n) với a i = n (1 ≤ i ≤ n−1) là C i−1.
Từ đây và chú ý rằng S 2 = 1, ta suy ra S n = 2 n − n − 1.
Ví dụ 63 Tìm số tập con của tập {1, 2, , n} sao cho trong mỗi tập con chứa ít nhất hai phần tử là hai số nguyên liên tiếp.
Lời giải cho bài toán này là xác định tập hợp S n, bao gồm các tập con không rỗng của {1, 2, , n}, trong đó không có hai phần tử nào là số nguyên liên tiếp Để giải quyết vấn đề này, chúng ta cần phân chia các phần tử trong S n thành hai nhóm khác nhau.
Nhóm không chứa {n} : số các tập con như vậy bằng |S n−1|.
Nhóm chứa phần tử n : {n} hoặc {a 1 , a 2 , , a n , n} Rõ ràng a i n − 1 (i 1, 2, , n) nên số các tập con như vậy bằng |S n−2| + 1 Như vậy ta có
Từ quan hệ truy hồi này với chú ý rằng |S 2| = 2, |S 3| = 4, chúng ta có
Mặt khác, số tập con không rỗng của {1, 2, , n} là 2 n − 1 Do đó số tập con thỏa mãn yêu cầu đề bài là n 1 1 .
Các bài toán sử dụng song ánh
Có n thí sinh (n > 1) ngồi quanh một bàn tròn, và cần tìm số cách phát đề sao cho hai thí sinh ngồi cạnh nhau luôn nhận được đề khác nhau Trong ngân hàng đề có m đề (m > 1) với nhiều bản sao cho mỗi đề.
LỜI GIẢI Bài toán tương đương với việc đếm số các dãy (a 1 , a 2 , , a n ) thỏa mãn điều kiện a i ∈ {1, 2, , m}(i = 1, 2, , n) và a 1 ƒ= a 2 , a 2 ƒ= a 3 , , a n ƒ= a 1
Trong tập hợp các dãy nói trên, ta gọi A n , B n lần lượt là tập các dãy mà a 1 a n và a 1 = a n
Với mỗi dãy thuộc B n , nếu bỏ đi a n thì ta được một dãy thuộc A n−1 nên
|B n | = |A n | Mặt khác, dễ thấy |A n | + |B n | = m(m − 1) n−1 (do a 1 có m cách chọn, a i+1 có m − 1 cách chọn khác a i với mọi i = 1, 2, , n − 1).
Vậy |A n | = m(m − 1) n−1 − |A n−1| Từ đây và kết hợp với |A 2| = m(m − 1), ta được
|A n | = (m − 1) + (m − 1)(−1) và đó chính là đáp số cần tìm.
4.2 Các bài toán sử dụng song ánh
Ví dụ 65 (Bài toán chia kẹo Euler) Cho m và n là các số nguyên dương Xét phương trình nghiệm nguyên x 1 + x 2 + ã ã ã + x n = m.
Phương trình trên có bao nhiêu nghiệm nguyên không âm?
Gọi X là tập hợp các nghiệm nguyên không âm của phương trình đã cho và Y là tập hợp các chuỗi nhị phân có độ dài m + n − 1, với m ký tự 1 và n − 1 ký tự 0 Xét ánh xạ f: X → Y, được xác định như sau: với mỗi x = (x1, x2, , xn) thuộc X, ánh xạ f(x) sẽ cho ra chuỗi nhị phân s11 1x0 1s1 1x0 0 1s1 1x, trong đó các ký tự 1 và 0 được sắp xếp theo quy tắc cụ thể.
4.2 Các bài toán sử dụng 61
Dễ thấy f là một song ánh Do đó
Ví dụ 66 Hãy tính trung bình cộng của tất cả các số N gồm n chữ số (n ≥ 2) thỏa mãn N chia hết cho 99 và các chữ số của N thuộc tập {1, 2, 8}
Gọi M là tập hợp các số N thỏa mãn điều kiện đề bài Chúng ta định nghĩa ánh xạ f: M → M sao cho nếu N = a1a2 an ∈ M, thì f(N) = b1b2 bn, trong đó bi = 9 - ai Dễ nhận thấy f(N) cũng thuộc M và f là một ánh xạ song ánh Rõ ràng, ta có N + f(N) = 9s9 9x, cho thấy tổng của N và f(N) luôn có dạng nhất định.
Vậy trung bình cộng của các số N là
Ví dụ 67 Gọi F là họ tất cả các tập con không rỗng của tập {1, 2, , n}. Với mỗi tập X thuộc họ , kí hiệu m(X) là trung bình cộng các phần tử của
2 nếu n chẵn, trong đó kí hiệu [m] là số nguyên lớn nhất không vượt quá m. n− 1
Phương pháp quỹ đạo
LỜI GIẢI Ta xây dựng ánh xạ f : F → F như sau f (X) = {n + 1 − x |x ∈ X}với mỗi X ∈ F
Dễ dàng kiểm tra được f là một song ánh Do đó ta có
Mặt khác, rõ ràng là Σ
Từ đây suy ra m(X) + m(f (X)) = n + 1 với mọi X ∈ F Σ
1 [m(X) + m(f (X))] 2|F|(n + 1), trong đó |F| = 2 n − 1 là số các tập con không rỗng của tập {1, 2, , n}.
Như vậy ta đã chứng minh được rằng
Từ đó ta có điều phải chứng minh.
Trong hệ tọa độ Oxy, điểm A(m, n) có thể được tiếp cận từ điểm O(0, 0) bằng đường đi ngắn nhất Đường đi này tuân theo quy tắc chỉ di chuyển theo hướng dương của các trục tọa độ và cho phép thay đổi hướng di chuyển.
− dương của trục tọa độ này sang hướng dương của trục tọa độ kia) tại các điểm có tọa độ nguyên. y n
Trước hết ta chứng minh một khẳng định sau
Mệnh đề 1 Số đường đi ngắn nhất từ điểm O(0, 0) đến điểm A(m, n) là C m
Mỗi đường đi ngắn nhất từ điểm O(0, 0) đến điểm A(m, n) đều bao gồm m + n đoạn thẳng, trong đó có m đoạn nằm ngang và n đoạn thẳng đứng, mỗi đoạn dài 1 đơn vị Các đường đi này chỉ khác nhau ở thứ tự của các đoạn nằm ngang và đoạn thẳng đứng Do đó, số đường đi ngắn nhất từ O(0, 0) đến A(m, n) bằng số cách chọn m đoạn nằm ngang từ tổng số m + n đoạn, được tính bằng công thức C(m+n, m).
Nhận xét 10 Ta có thể xét n đoạn thẳng đứng thay cho m đoạn nằm ngang và khi đó số đường đi ngắn nhất từ điểm O(0, 0) đến điểm A(m, n) sẽ là C n
Như vậy ta đã chứng minh được C m m+n
Từ mệnh đề trên, dễ dàng suy ra hai hệ quả sau
Hệ quả 1 Số đường đi ngắn nhất từ điểm M(p, q) đến điểm A(m, n) (với
Hệ quả 2 Số đường đi ngắn nhất từ điểm O(0, 0) đến điểm A(m, n) đi qua điểm M(p, q) là C p m−p
Bây giờ sẽ là một số bài toán áp dụng m+ n m+ n m+ n m+ n
Ví dụ 68 Chứng minh đồng nhất thức Pascal
Số đường đi ngắn nhất từ điểm O(0, 0) đến điểm A(k, n − k) là C k = C k
Ta chia các đường đi đó thành hai loại như sau:
• Loại 1 gồm các đường đi từ O đến A phải qua điểm A 1(k, n − k − 1) Số đường thuộc loại này là C k n−1
• Loại 2 gồm các đường đi từ O đến A phải qua điểm A 2(k − 1, n − k) Số đường thuộc loại này là C k−1 1 k− n− 1
Theo quy tắc cộng, ta suy ra C k = C k−1 + C k n
Ví dụ 69 Chứng minh đẳng thức n−1 n−1
Số đường đi ngắn nhất từ điểm O(0, 0) đến điểm A(k, n − k) được tính bằng C(k, n - k) Các đường đi này được phân chia thành n - k + 1 loại, với loại thứ i (i = 0, 1, 2, , n - k) là những đường đi từ O đến A cắt đường thẳng đứng x = 1 tại điểm (1, i) Số lượng đường đi thuộc loại này tương đương với số đường đi từ điểm (1, i) đến điểm (k, n - k).
Từ quy tắc cộng suy ra k−1 (k−1)+
Ví dụ 70 Chứng minh đẳng thức
Số đường đi ngắn nhất từ điểm O(0, 0) đến điểm A(n, n) là C n Chúng ta có thể chia các đường đi này thành n + 1 họ không giao nhau, trong đó mỗi họ thứ i (0 ≤ i ≤ n) bao gồm các đường đi từ O đến A đi qua điểm A i (i, n − i) Số lượng đường đi trong mỗi họ này được xác định rõ ràng.
C i C n−i = (C i ) 2 Theo quy tắc cộng suy ra n n Σ n n
Trong bài toán này, cho các số nguyên dương m, n, p, q với điều kiện m > p và n > q, ta xét bốn điểm A(0, 0), B(p, 0), C(m, q) và D(m, n) trên mặt phẳng tọa độ Mục tiêu là tìm các đường đi ngắn nhất từ điểm A đến điểm D, cũng như các đường đi ngắn nhất từ điểm B đến điểm C.
B đến C Gọi S là số cặp đường đi (f, g) mà f và g không có điểm chung.
Số cặp đường đi (f, g) tùy ý là m+ n n m+q−p
Gọi N là số cặp đường đi (f ′ , g ′ ) với f ′ là số đường đi ngắn nhất từ A đến C, g ′ là đường đi ngắn nhất từ B đến D Số cặp đường đi (f ′ , g ′ ) tùy ý là m+ q q n m+n− p (1)
Vì f ′ và g ′ luôn có ít nhất một điểm chung K(i, j) với p ≤ i ≤ m và 0 ≤ j ≤ q, nên số đường đi f ′ phải qua K là i+ i j q−j
(m+i)−(q−j) và số đường đi g ′ phải qua K là
Một số dạng bài toán khác
Điểm K là điểm chung của cặp đường đi (f, g), với f và g có điểm giao nhau Nếu T được định nghĩa là số cặp đường đi (f, g) có điểm chung K, thì có thể diễn đạt mối quan hệ này bằng công thức i + j = n - j.
Sử dụng phương pháp quỹ đạo như ở trên, chúng ta có thể chứng minh các đẳng thức sau
4.4 Một số dạng bài toán khác
Ví dụ 72 (Austrian-Polish 1980) Chứng minh rằng Σ 1 i 1 i 2 ã ã ã i k = n, ởđó tổng chạy trên tất cả các tập con không rỗng {i 1 , i 2 , , i k } của {1, 2, , n}.
LỜI GIẢI Ta sẽ chứng minh bằng quy nạp theo n.
• Bước cơ sở: Với n = 1 hiển nhiên đẳng thức trên là đúng Với n = 2 thì các tập con không rỗng của tập {1, 2} là {1}, {2} và {1, 2} Khi đó
• Bước quy nạp: Giả sử đẳng thức đúng đến n Ta cần chứng minh đẳng thức cũng đúng với n + 1 Gọi F là họ tất cả các tập con không rỗng của
{1, 2, , n, n + 1} Ta phân hoạch F thành hai họ F1: gồm những tập m+ n q n k n−
C con không chứa phần tử n + 1 và F2: gồm những tập con chứa phần tử n + 1 Do đó trong đó Σ 1
= n + 1 và đó chính là điều ta cần chứng minh.
Nhận xét 11 Bài toán trên còn có thể phát biểu dưới dạng Σ
Ví dụ 73 Cho m, n là các số nguyên dương thỏa mãn m + n = 100 Tìm giá trị nhỏ nhất của biểu thức a) A = m! + n!. b) B = m!n!.
Giả sử m ≥ n và chứng minh rằng nếu m − n ≥ 2 thì m!n! và m! + n! không phải là giá trị nhỏ nhất Đặt a = m − 1 và b = n + 1, ta có a + b < 100 và a!b! < m!n! khi và chỉ khi (m − 1)!(n + 1)! < m!n! với điều kiện n + 1 < m Hơn nữa, a! + b! < m! + n! tương đương với (m−1)! + (n+1)! < m! + n! và cũng dẫn đến (m−1)!(m−1) > n!n.
Vậy để A, B đạt giá trị nhỏ nhất thì m − n ∈ {0, 1} Từ đó suy ra min A = 50! + 50!, min B = (50!) 2
Ví dụ 74 Cho số nguyên dương n ≥ 2 Chứng minh rằng tổng sau không thể là số nguyên
Xét tập M = {m ∈ N | 2m ≤ n}, tập này bị chặn và có phần tử lớn nhất là k Gọi a là tích của tất cả các số lẻ không vượt quá n Đặt b = 2^(k−1) * a, thì b chia hết cho tất cả các phần tử của tập M.
Vậy A không thể là số nguyên.
Trong bài toán này, chúng ta đã áp dụng nguyên tắc cực hạn, cho thấy rằng trong một tập hợp các số thực có hữu hạn phần tử, luôn tồn tại phần tử lớn nhất và phần tử nhỏ nhất.
Ta đến với bài toán tiếp theo để thấy được tầm quan trọng của nguyên tắc này.
Ví dụ 75 Cho n, p là các số nguyên dương, n ≥ 3 Hãy tìm tất cả các nghiệm dương của hệ phương trình
LỜI GIẢI Đặt M = max{x 1 , x 2 , , x n } và m = min{x 1 , x 2 , , x n } Từ hệ đã cho ta suy ra tồn tại các chỉ số r, s ∈ {1, 2, , n − 1} sao cho x r + x r+1 = M p , x s + x s+1 = m p
Rõ ràng x r , x r+1 ≤ M và x s , x s+1 ≥ m nên ta có
4.4 Một số dạng bài toán 70
Mặt khác lại do M ≥ m nên M = m p−√ 1
Như vậy hệ đã cho có nghiệm duy nhất x 1 x 2
Ví dụ 76 Cho a, b là các số nguyên dương và a ≥ b Giả sử tồn tại cặp số nguyên dương (x, y) sao cho x 2 + y 2 − axy = b Chứng minh rằng b là số chính phương.
Để chọn cặp (x, y) sao cho tổng x + y nhỏ nhất, ta giả sử x ≥ y Xét phương trình bậc hai x^2 + y^2 - axy = b, với x' là nghiệm thứ hai Khi đó, tổng x + x' = ay, dẫn đến x' thuộc tập số nguyên Z.
• Nếu x ′ = 0 thì b = y 2 là số chính phương.
• Nếu x ′ > 0 thì từ đẳng thức x.x ′ = y 2 − b suy ra x ′ < y ≤ x Kéo theo x ′ + y < x + y, vô lý.
Ví dụ 77 Cho x, y là các số nguyên sao cho A x 2 + y
2 + 6 là một số nguyên xy dương Chứng minh A là số lập phương đúng.
Giả sử x, y > 0, ta cố định A và chọn cặp (x, y) sao cho tổng x + y là nhỏ nhất với điều kiện x ≥ y Xét phương trình bậc hai x^2 + y^2 + 6 - Axy = 0, với x' là nghiệm còn lại, ta có x' + x = Ay và x' * x = y^2 + 6 Từ đó suy ra x' ∈ Z và x' > 0, đồng thời x' ≥ x và x^2 ≤ y^2 + 6 Kết quả là x^2 - y^2 thuộc tập hợp {0, 1, 2, 3, 4, 5, 6}.
Nếu x = y thì do A là số nguyên nên x 2 |6 hay x = 1 Khi đó A = 8 là số lập phương đúng.
Nếu x > y thì bằng cách giải trực tiếp các phương trình nghiệm nguyên ta suy ra không tồn tại x, y.
Trò chơi bắt đầu với 10 dấu (+) và 15 dấu (−) trên bảng Mỗi lượt, người chơi sẽ chọn hai dấu bất kỳ và nếu cả hai dấu đó là dấu (−), chúng sẽ được thay thế bằng một dấu (+).
Trong bài toán này, nếu các dấu được lấy ra đều là dấu (+) hoặc đều là dấu (−), thì không có vấn đề gì Tuy nhiên, nếu có một dấu (+) và một dấu (−) được lấy ra, chúng sẽ được thay thế bằng một dấu (−) Câu hỏi đặt ra là liệu sau một số lần thực hiện như vậy, trên bảng có thể chỉ còn lại một dấu (+) hay không?
Khi thay thế các số có tích bằng 1 bằng số 1 và các số có tích bằng -1 bằng số -1, tích của tất cả các số trên bảng sẽ không thay đổi Ban đầu, với 10 số 1 và 15 số -1, tích là -1 Do đó, dù thực hiện bao nhiêu lần thay thế, không thể có kết quả chỉ còn lại một dấu (+) trên bảng.
Chúng ta đã áp dụng nguyên lý bất biến để giải quyết bài toán, trong đó việc nhận diện tính bất biến là yếu tố quan trọng Trong trường hợp này, tính bất biến được xác định là tích của các số.
Chúng ta xét thêm một số ví dụ nữa.
Trong trò chơi cờ giữa hai người, mỗi ván đấu sẽ mang lại 2 điểm cho người thắng, 0 điểm cho người thua, và 1 điểm cho mỗi người nếu kết quả là hòa Đặt ra câu hỏi liệu có thể xảy ra trường hợp một người đạt 10 điểm trong khi người kia có 15 điểm sau một số ván chơi hay không.
Sau mỗi ván chơi, tổng số điểm của hai người chơi luôn là 2, cho thấy tổng điểm sau bất kỳ số ván nào cũng luôn là số chẵn Điều này giải thích tại sao không thể có trường hợp một người chơi đạt 10 điểm trong khi người còn lại có 15 điểm.
Trong bài toán này, chúng ta xem xét một bàn cờ vua 8 × 8, nơi một con mã bắt đầu từ góc trên bên trái và phải di chuyển qua tất cả các ô một lần duy nhất Câu hỏi đặt ra là liệu con mã có thể kết thúc hành trình của mình tại ô góc dưới bên phải của bàn cờ hay không.
Mỗi lần quân mã di chuyển, nó sẽ chuyển sang ô khác màu Để hoàn thành hành trình trên bàn cờ mà mỗi ô chỉ được ghé thăm một lần, quân mã cần thực hiện 63 lần di chuyển Kết thúc hành trình, quân mã sẽ đứng ở ô khác màu so với ô đầu tiên Do hai ô góc đối diện của bàn cờ có cùng màu, quân mã không thể kết thúc tại ô góc dưới bên phải của bàn cờ.
Ví dụ 81 (Thi vào lớp 10 chuyên ĐHSP HN, 2010) Ban đầu trên bảng có ba
Trong trò chơi này, người chơi sẽ xóa hai số bất kỳ, gọi là a và b, và thay thế chúng bằng hai số mới Cụ thể, hai số mới được tính toán là trung bình cộng của a và b, được biểu diễn dưới dạng √(a + b)/2.
