Một số phương pháp giải bài toán tổ hợp

Các kiến thức cơ bản về giải tích – tổ hợp

Trong chương này, chúng tôi giới thiệu kiến thức về tổ hợp, hoán vị, chỉnh hợp, công thức nhị thức Newton và nguyên lý bù trừ tổng quát Những kiến thức này sẽ hỗ trợ việc giải quyết các bài toán trong chương 2.

Một số phương pháp giải bài toán tổ hợp

Phương pháp phân tích

Phương pháp song ánh

Phương pháp truy hồi

2.3.2 Các bài toán vận dụng

Phương pháp đồ thị

2.4.2 Các bài toán vận dụng

Phương pháp hàm sinh

Phương pháp tổng hợp

Luận văn này được thực hiện tại Trường Đại học Vinh, và tôi xin gửi lời cảm ơn chân thành đến TS Mai Văn Tư, người đã đưa ra vấn đề nghiên cứu, định hướng và trực tiếp hướng dẫn tôi hoàn thành luận văn.

Em xin gửi lời cảm ơn chân thành đến Ban chủ nhiệm Khoa Toán, Khoa Đào tạo sau đại học, cùng các thầy cô giáo tại Khoa Toán và Bộ môn Đại số, Trường Đại học Vinh.

Tác giả xin chân thành cảm ơn Ban giám hiệu cùng toàn thể giáo viên trường THPT Cù Huy Cận, Vũ Quang, Hà Tĩnh đã hỗ trợ và tạo điều kiện thuận lợi cho tác giả trong suốt quá trình học tập và hoàn thành luận văn này.

Mặc dù đã nỗ lực hết mình, luận văn vẫn không thể tránh khỏi những thiếu sót Chúng tôi rất mong nhận được sự đóng góp quý báu từ các thầy cô giáo và đồng nghiệp để hoàn thiện hơn.

CÁC KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP

QUY TẮC CỘNG

Cho A B, là hai tập hữu hạn và A  B thì A  B  A B

QUY TẮC CỘNG CHO n TẬP HỢP

Nếu A A 1 , 2 , ,A n là các tập hữu hạn đôi một rời nhau, tức là i j

A A   nếu i j thì A 1   A n  A 1  A 2   A n Ở đây A i là lực lƣợng ( số các phần tử) của tập A i

Giả sử có n hành động loại trừ lẫn nhau H1, H2, , Hn, có nghĩa là không thể xảy ra hai hành động cùng lúc Mỗi hành động Hi có a_i cách thực hiện Do đó, hành động H có thể xảy ra theo cách H1, H2, , hoặc Hn.

H n xảy ra, có cả thảy a 1 a 2   a n cách thực hiện.

QUY TẮC NHÂN

Cho A B, là hai tập hữu hạn và A  B thì A B  A B.

QUI TẮC NHÂN CHO n TẬP HỢP

Nếu A 1 , ,A n là các tập hữu hạn bất kì và A 1   A n là tích Đề-các của các tập đó, thì: A 1 A 2   A n  A A 1 2 A n

Giả sử hành động H bao gồm n giai đoạn độc lập, với giai đoạn thứ i là H i và có a i cách thực hiện Khi đó, tổng số cách thực hiện của hành động H sẽ là a 1 × a 2 × × a n.

Số ánh xạ ánh xạ từ một tập hợp X có k phần tử tới một tập Y phần m phần tử bằng m k

Hệ quả

A là một tập hữu hạn, và B là một tập con của A Đặt B A B Ta có:

SỐ PHÂN TỬ CỦA HỢP HAI HOẶC BA TẬP HỢP HỮU HẠN

1.6.1 Trường hợp hai tập hợp

Cho hai tập hữu hạn A và B ta có công thức:

1.6.2 Trường hợp ba tập hợp

Với A , B là hai tập hữu hạn bất kì, ta luôn có A B A  B Đẳng thức A B A  B xảy ra    A B

1.6.2.2 Hệ quả Giả sử A , B là hai tập hữu hạn nếu B A thì B  A

1.6.2.3.Mệnh đề (Đề thi HSG Quốc gia THPT Bảng B - 2005)

Tìm hiểu kết quả học tập ở một lớp học, người ta thấy:

3 số học sinh đạt điểm giỏi ở môn Toán cũng đồng thời đạt điểm giỏi ở môn Vật lí

3 số học sinh đạt điểm giỏi ở môn Vật lí cũng đồng thời đạt điểm giỏi ở môn Văn

3 số học sinh đạt điểm giỏi ở môn Văn cũng đồng thời đạt điểm giỏi ở môn Lịch sử

3 số học sinh đạt điểm giỏi ở môn Lịch sử cũng đồng thời đạt điểm giỏi ở môn Toán

Khi đó trong lớp học nói trên có ít nhất một học sinh đạt điểm giỏi cả bốn môn Toán, Vật lí, Văn và Lịch sử

Chứng minh: Kí hiệu T L V S, , , lần lƣợt là tập hợp các học sinh giỏi

Toán, Vật lí, Văn, Lịch sử

Theo đề bài, ta có:

Để giải bài toán này, ta sử dụng phương pháp phản chứng Giả định rằng không có học sinh nào đạt điểm giỏi cả bốn môn Toán, Vật lí, Văn và Lịch sử, dẫn đến T∩ = ∅V hoặc L∩ = ∅S Nếu T∩ = ∅V, thì (T∩L)(∩L∩V) = ∅ và (T∩S)(∩S∩V) = ∅ Tuy nhiên, (T∩L)(+L∩V) ⊆ L và (T∩S)(+S∩V) ⊆ S, do đó, (T∩L)(+L∩V) ≤ L và (T∩S)(+S∩V) ≤ S.

Mặt khác, từ (*) ta có: 2  

Từ (1) và (2) ta gặp mâu thuẫn nên điều giả sử ban đầu là sai

Nếu L  S , lập luận tương tự cũng dẫn đến điều mâu thuẫn Bài toán đƣợc chứng minh.

TỔ HỢP KHÔNG LẶP

2.1 TỔ HỢP (TỔ HỢP KHÔNG LẶP)

Số tập con của một tập hợp có m phần tử

Cho tập hợp A có m phần tử Ta hãy xét xem tập hợp tất cả các tập con của nó, T A ( ), có bao nhiêu phần tử

Số tất cả các tập con của một tập hợp có m phần tử bằng 2 m

Một tập con k phần tử của một tập hợp m(m1) phần tử đƣợc gọi là một tổ hợp chập k của m phần tử

Kí hiệu C m k là số tổ hợp chập k của m phần tử thì :

Có C(m, 0) = 1 vì chỉ có một tập con rỗng không chứa phần tử nào Đồng thời, C(m, m) = 1 cũng đúng, vì chỉ có một tập con chứa tất cả m phần tử, đó chính là tập A.

2.3 MỘT SỐ TÍNH CHẤT QUAN TRỌNG CỦA CÁC SỐ C m k

Công thức này gọi là qui tắc đối xứng

Công thức này được gọi là qui tắc Pascal

HOÁN VỊ

Tập hợp A có n phần tử (với n ≥ 1) và mỗi cách sắp xếp các phần tử trong tập hợp này được gọi là một hoán vị.

Kí hiệu P m là số các hoán vị ta có :

Số song ánh từ một tập hợp m phần tử A lên chính nó bằng m!

CHỈNH HỢP

Các tập con sắp thứ tự cók phần tử của một tập hợp có m phần tử đƣợc gọi là các chỉnh hợp chập k của mphần tử đó (1   k m )

Các chỉnh hợp chập k của m phần tử sẽ được coi là khác nhau nếu chúng chứa các phần tử khác nhau Nếu có các phần tử giống nhau, thì thứ tự của các phần tử đó cũng cần phải khác nhau để tạo ra các chỉnh hợp khác nhau.

Kí hiệu A m k là số chỉnh hợp chập k của m phần tử , ta có :

Số đơn ánh từ một tập A có k phần tử đến một tập B có m phần tử

CHỈNH HỢP CÓ LẶP

Cho một tập hợp A có m phần tử, ta thực hiện việc rút ra ngẫu nhiên một phần tử từ A, ký hiệu là a1, và sau đó trả lại nó vào tập hợp Tiếp theo, ta tiếp tục rút ra một phần tử khác, ký hiệu là a2 (có thể là a1), và cũng trả lại vào A Quá trình này được lặp lại k lần (k không nhất thiết phải nhỏ hơn hoặc bằng m), tạo thành một dãy (a1, a2, , ak) gồm k phần tử, có thể có sự trùng lặp.

Một dãy nhƣ thế đƣợc gọi là một chỉnh hợp có lặp chập k của m phần tử đã cho

Tập hợp tất cả các chỉnh hợp có lặp chập k từ các phần tử của một tập hợp A với m phần tử được gọi là tập hợp các bộ (a₁, a₂, , aₖ) với i thuộc A Điều này tương đương với tích Đề các.

Từ đó suy ra ngay định lí sau: Định lí 5.1.1 Số chỉnh hợp có lặp chập k của m phần tử kí hiệu là k

A , được tính theo công thức: n

HOÁN VỊ CÓ LẶP

Một hoán vị có lặp chập m của s phần tử khác nhau, được đánh số từ 1 đến s, bao gồm k1 phần tử thứ nhất, k2 phần tử thứ hai, cho đến ks phần tử thứ s, được gọi là hoán vị có lặp cấp.

 1 2 s  m k   k k và kiểu  k k 1, 2, ,k s  của s phần tử đã cho

Nhờ vào khái niệm hoán vị có lặp với cấp m và kiểu  k k 1, 2, ,k s , chúng ta có thể diễn đạt lại định lý đã thiết lập trước đó dựa trên cách đoán nhận các hệ số đa thức.

Số hoán vị có lặp, cấp m , kiểu ( , , ) k k 1 2 k s của s phần tử đã cho bằng:

Chú ý: Theo công thức (1) , số hoán vị có lặp của hai phần tử cấp m, kiểu  k m ,  k  bằng:

Số này chính là C m k Vậy số hoán vị có lặp của hai phần tử cấp m, kiểu  k m ,  k  bằng số tổ hợp chập k của m phần tử

Cho p q rđồ vật khác nhau Số cách phân các đồ vật đó thành 3 nhóm ,sao cho nhóm thứ nhất chứa p đồ vật , nhóm thứ hai chứa q đồ vật

, nhóm thứ ba chứa r đồ vật là :   ( , , )(   )!

6.2.HOÁN VỊ VÒNG QUANH( HOÁN VỊ TRÒN)

Mời 6 người khách ngồi xung quanh một bàn tròn Liệu có bao nhiêu cách sắp xếp?

Khi mời một người nào đó ngồi vào một vị trí bất kỳ, số cách sắp xếp 5 người còn lại vào 5 vị trí dành cho họ là 5! = 120.

Vậy có cả thảy 120 cách sắp xếp 6 người ngồi xung quanh một bàn tròn

Số hoán vị vòng quanh của n phần tử khác nhau (Q n ) được tính bằng công thức:

TỔ HỢP LẶP

7.1 Định nghĩa Cho m phần tử khác nhau Một tổ hợp có lặp chập n (n không nhất thiết m) của m phần tử đã cho là một tập chứa n phần tử, trong đó mỗi phần tử là một trong m phần tử đã cho

7.2 Định lí Số tổ hợp có lặp chậpn của m phần tử, kí hiệu là C m n được xác định bởi công thức:

NGUYÊN LÝ BÙ TRỪ TỔNG QUÁT

Có bao nhiêu phần tử trong hợp của hai tập hợp hữu hạn phần tử?

Số lượng phần tử trong hai tập hợp A và B được xác định bằng tổng số phần tử của từng tập trừ đi số phần tử chung của chúng, cụ thể là: |A ∪ B| = |A| + |B| - |A ∩ B|.

8.2 Định lí Nguyên lý bù trừ:

Cho A A 1 , 2 , A n là các tập hữu hạn.Khi đó,

MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN TỔ HỢP

Nội dung phương pháp

Các bài toán tổ hợp thường liên quan đến các yếu tố ràng buộc theo những quy tắc nhất định Mục tiêu của bài toán là đánh giá một đại lượng liên quan đến các yếu tố này hoặc chứng minh một quy tắc hay một định luật nào đó là đúng Để giải quyết những bài toán tổ hợp này, chúng ta cần thực hiện hai bước cơ bản.

Bước đầu tiên trong quá trình giải quyết bài toán là xác định ẩn để mô tả các yếu tố trong đề bài, từ đó xây dựng một phương trình, bất phương trình hoặc hệ hỗn hợp chứa ẩn đã chọn.

Bước 2: Tiến hành xử lý các yếu tố đã mô tả theo yêu cầu của bài toán bằng cách giải ra nghiệm hoặc biến đổi chúng thành những kết quả hỗ trợ cho việc hình thành quy tắc hoặc quy luật đáp ứng yêu cầu của bài toán.

Các ứng dụng

2.1.2.1 Bài toán 1: Chứng minh định lí: Số các đơn ánh từ một tập X có r phần tử vào một tập Y có n phần tử là A n r

Nếu \( f(x) \) có các giá trị \( f(x) = a, b, \ldots, l \) cho \( r \) giá trị khác nhau, ta có thể biểu diễn hàm số \( f \) dưới dạng một chỉnh hợp của \( n \) phần tử \( y_i \) Biểu diễn này là một phép tương ứng một-một, do đó số lượng hàm đơn ánh bằng số chỉnh hợp \( n \) chập \( r \), tức là \( A(n, r) \).

2.1.2.2 Bài toán 2 (Đề thi HSG Ba Lan) : Cho tập hợp M có n phần tử, với hai tập con tùy ý A B, của M Tính số phần tử của AB Chứng minh rằng tổng tất cả các số phần tử của mọi giao có thể gồm 2 tập con của

Xét phần tử aM có 2 n 2 n  1 2 n  1 tập con của M có chứa phần tử a

 chia ra   2 n  1 2  4 n  1 cặp hai tập con của M có chứa a thuộc giao hai tập đó Vậy mỗi phần tử aM thì nó đƣợc đếm 4 n 1 lần 

Theo cách giải trên ta có thể giải bài toán tổng quát hơn sau:

Cho A là tập có n phần tử.E là tập tất cả các bộ( có thứ tự)

 A A 1, 2, ,A k  trong đó A i A;k là số tự nhiên đã cho Chứng minh rằng

2.1.2.3 Bài toán 3 ( Đề thi Olympic toán Châu Á Thái Bình Dương lần

Giả sử F là tập hợp tất cả các bộ  A A 1, 2, ,A k  trong đó A i là một tập con của 1,2, ,1998  i  1,2, , k  ( k  N , đã cho) Hãy tính

Lời giải: Đặt n1998 Gọi S k   i là số các bộ  A A 1, 2, ,A k F mà  k j

Do có 2 n tập con của A và 2 n 1 tập con của A \   i

2.1.2.4 Bài toán 4 (Đề thi Olympic Tây Ban Nha): Xét các tập A thỏa mãn: A gồm 100 số tự nhiên phân biệt sao cho a b c, , là các phần tử của A

Tam giác cạnha b c có thể phân biệt hoặc không, nhưng luôn tồn tại mà không có góc tù Tổng các chu vi của tam giác được xét được gọi là S A.

A Tìm giá trị nhỏ nhất của S A  

Lời giải: a 1a 2   a 100; a i A i  1,2, ,n  Xét tam giác 3 cạnh là

   a 1  1 2 99    a 1 240 Mỗi số a i là cạnh của: một tam giác đều; 99 tam giác cân mà hai cạnh bên là a i ; 99 tam giác cân mà a i là cạnh đ áy và C 99 2 tam giác thường Vậy,

2.1.2.5 Bài toán 5 ( USAMO 2001): Có 8 cái hộp, mỗi hộp chứa 6 trái banh Tìm số nhỏ nhất sao cho mỗi banh tùy ý đều đƣợc tô một trong n màu thỏa mãn đồng thời hai điều kiện sau:

1 Trong mỗi hộp không có hai banh nào đƣợc tô cùng một màu

2 Hai hộp bất kì có chung không quá một màu

+ Gọi x i là số màu xuất hiện i lần i1,2, ,k,  k  n  Ta có: n x 1 x 2   x k (1)

+ Gọi y là số cách chọn hai hộp không có chung màu nào Do hai hộp bất kì có chung không quá một màu nên:

+ Cách tô sau của 23 màu thỏa mãn bài toán (gọi tên màu là: 1,2, ,23)

+ Ở hình dưới đây, mỗi đường tượng trưng cho mỗi hộp, các giao điểm ở trên đường tượng trưng cho các banh

+ Có đúng 8 đường, mỗi đường chứa đúng 6 giao điểm và có tất cả

23 giao điểm Hai đường bất kì có tối đa một điểm chung

+ Mỗi cách đánh số 23 giao điểm, từ 1 đến 23, cho ta một cách tô màu trên các banh ở 8 hộp thỏa mãn các điều kiện bài toán

2.1.2.6 Bài toán 6 (IMO 2005): Trong một kì thi học sinh giỏi, các thí sinh phải giải 6 bài toán Biết rằng với hai bài toán bất kì luôn có nhiều hơn 2

Trong số các thí sinh tham gia thi, chỉ có 5 thí sinh giải được cả hai bài toán, và không có thí sinh nào giải được tất cả 6 bài toán Do đó, cần chứng minh rằng ít nhất có hai thí sinh, mỗi người trong số họ đã giải đúng 5 bài toán.

+ Gọi n là số thí sinh tham gia kì thi và x k là số thí sinh giải đƣợc đúng k bài toán  k 0,1,2,3,4,5,6 Ta có: x 6 0, nx 0  x 1 x 2  x 3 x 4 x 5 (4)

+ Với i j, và i j, gọi s i j     ,  s j i , là số thí sinh giải đƣợc cả bài i và bài j,  i j , 1,2,3,4,5,6

Theo giả thiết luôn có: 5 s i j   ,  2 n Do đó, 5 s i j   ,  2 n  1 Có tất cả C 6 2 15 cặp   i j , mà i  j nên:

+ Ta chứng minh thêm x 5 không thể bằng 1

Giả sử x 5 1 Lúc đó, từ(7) cho x 0  x 1 x 2 x 3 0 và x 4  n 1

Trường hợp này duy nhất một thí sinh A làm đúng 5 bài, còn lại tất cả đều làm đƣợc đúng 4 bài

Thí sinh A không giải được bài r, trong khi có k thí sinh khác đã hoàn thành bài này Mỗi thí sinh trong số k thí sinh này không chỉ giải được bài r mà còn hoàn thành thêm 3 bài toán khác trong số các bài còn lại.

Nếu a không phải là số nguyên thì:

+ Nếu a là số nguyên thì hiệu s i j   ,  a là số nguyên không âm

Từ công thức S = 6n + 4, ta có thể viết lại tổng ∑i j < (sij) - a = 1 Điều này dẫn đến việc trong 15 số hạng sij với i < j, sẽ có 14 số hạng có giá trị bằng a và một số hạng có giá trị bằng a + 1 Đặt spq = a + 1, từ đó giá trị của ∑6 j ≠ 1, j rsrj chỉ có thể là 5a hoặc 5a + 1, tùy thuộc vào việc r có thuộc vào (pq) hay không.

Kết hợp với (*), ta có hoặc 5a chia hết cho 3 hoặc 5 a  1 chia hết cho3 (**)

Thí sinh A đã giải quyết 5 bài, điều này cho thấy tồn tại một bài t khác với các bài p, q, r mà thí sinh A đã làm Gọi h là số thí sinh giải được bài t Trong số các thí sinh này, thí sinh A không chỉ giải được bài t mà còn thêm 4 bài nữa, trong khi đó, h - 1 thí sinh còn lại cũng giải được bài t và thêm đúng 3 bài nữa.

Suy ra 5 a   3 h 1 và 5 a   1 3 h  2 Điều này cũng mâu thuẫn với (**).

PHƯƠNG PHÁP SONG ÁNH

Có người đến dự một buổi nói chuyện trong một hội trường gồm

200 ghế Giả sử mỗi người chỉ chiếm một ghế ngồi và mỗi ghế chỉ có

Số lượng người ngồi tối đa là 19, và nếu được thông báo rằng mọi người đều có chỗ ngồi, ta có thể kết luận rằng n ≤ 200 Nếu biết không có ghế trống, ta xác định n = 200 Ngược lại, nếu có người phải đứng do thiếu ghế, ta suy ra n > 200 Qua đó, ta có thể ước lượng số phần tử của một tập hợp A dựa vào tập hợp B đã biết số phần tử thông qua một phép ánh xạ giữa A và B, đây là phương pháp hiệu quả để giải quyết nhiều bài toán đếm nâng cao.

 Ánh xạ f đƣợc gọi là một đơn ánh nếu với hai phần tử bất kì

 Ánh xạ f đƣợc gọi là một toàn ánh nếu với mọi b B  đều tồn tại a A để f a    b

Ánh xạ f được gọi là song ánh khi với mỗi phần tử b thuộc tập B, tồn tại duy nhất một phần tử a thuộc tập A sao cho f(a) = b Nói cách khác, f là song ánh khi nó đồng thời là đơn ánh và toàn ánh Định lý này áp dụng cho hai tập hợp hữu hạn A và B.

 Nếu có một đơn ánh f A :  B thì A  B

 Nếu có một toàn ánh f A :  B thì A  B

 Nếu có một song ánh f A :  B thì A  B

Ta biết rằng, nếu có song ánh f A :  B thì A  B Do đó, thay vì đếm số phần tử của A ta có thể đưa về đếm số phần tử của B

Trở ngại lớn nhất trong việc giải quyết bài toán tổ hợp là xác định hướng đi phù hợp Để nâng cao khả năng định hướng, việc rèn luyện các phương pháp tiếp cận là vô cùng cần thiết Dưới đây là một số lời giải cho bài toán tổ hợp, áp dụng hiệu quả phương pháp song ánh.

Dựa trên kết quả hiển nhiên, nếu tồn tại một ánh xạ từ tập hữu hạn X đến tập hữu hạn Y, thì số lượng phần tử trong hai tập này là bằng nhau.

Một cách tự nhiên, kết quả trên hướng chúng ta đến ý tưởng sử dụng song ánh để so sánh lực lƣợng hai tập hợp

2.2.2.1 Bài toán 1(Vô địch Liên Xô): Có một nhóm người mà trong đó, mỗi cặp không quen nhau có đúng hai người quen chung còn mỗi cặp không quen nhau thì không có người quen chung Chứng minh rằng số người quen của mỗi người là như nhau

Giả sử a quen b và có những người quen A và B (không tính a và b) Mỗi người a’ trong A sẽ quen duy nhất một người trong B, vì a’ và b không quen nhau và họ đã có một người quen chung là a Do đó, tồn tại một song ánh từ A đến B, cho thấy a và b có số người quen bằng nhau.

Nếu a không quen b thì tồn tại c quen cả a và b , do đó số người quen của a và b bằng nhau do cùng bằng số người quen của c

2.2.2.2.Bài toán 2 ( Trung Quốc – 1997): Trong các xâu nhị phân có độ dài n, gọi a n là số các xâu không chứa quá 3 số liên tiếp 0,1,0 và b n là số các xâu không chứa 4 số liên tiếp 0,0,1,1 hoặc 1,1,0,0 Chứng minh rằng

Lời giải : Ta gọi một xâu thuộc loại A nếu nó không chứa 3 số liên tiếp

0,1,0 và gọi một xâu thuộc loại B nếu nó không chứa 4 số hạng liên tiếp

Với mỗi xâu X  x x 1, 2, ,x n  1  ta xây dựng f X    y y 1, 2, ,y n  1  nhƣ sau: y 1 0, y k  x 1 x 2  x k  1 mod 2  Rõ ràng X chứa 3 số liên

21 tiếp 0,1,0 khi và chỉ khi f X   chứa 4 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 f X   thuộc B

Hàm f là một song ánh từ tập các xâu loại A có độ dài n đến các xâu loại B có độ dài n + 1 bắt đầu bằng 0 Mỗi xâu X thuộc B có thể tạo ra một xâu X' cũng thuộc B bằng cách đổi các phần tử theo quy tắc 1 ↔ 0 Do đó, số lượng xâu 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ừ đó chứng minh được điều cần thiết.

Phương pháp song ánh cho phép chúng ta đếm số phần tử của một tập hợp bằng cách so sánh lực lượng của nó với một tập hợp khác có số phần tử đã biết.

2.2.2.3 Bài toán 3 (Vô địch Ucraina – 1996): Gọi M là các số nguyên dương viết trong hệ thập phân có 2n chữ số, trong đó có n chữ số 1 và n chữ số 2 Gọi N là số tất cả các số viết trong hệ thập phân có n chữ số, trong đó chỉ có chữ số 1,2,3,4 và số chữ số 1 bằng số chữ số 2 Chứng minh rằng M N

Để giải quyết bài toán, ta có thể nhân đôi một số có n chữ số, bao gồm các chữ số 1, 2, 3, 4, với điều kiện số chữ số 1 bằng số chữ số 2 Cách thực hiện là viết hai phiên bản của số này kề nhau, tạo thành số có 2n chữ số Tiếp theo, các chữ số 3 trong n chữ số đầu và chữ số 4 trong n chữ số sau sẽ được thay thế bằng chữ số 1, trong khi các chữ số 3 ở n chữ số sau và chữ số 4 ở n chữ số đầu sẽ được thay thế bằng chữ số 2.

Để chứng minh rằng tập hợp các số có n chữ số 1 và n chữ số 2 tạo thành một song ánh, ta có thể xây dựng ánh xạ ngược Cụ thể, với mỗi số có n chữ số 1 và n chữ số 2, ta tiến hành cắt n chữ số đầu và n chữ số cuối, sau đó cộng chúng theo cột theo quy tắc đã định.

1 1 1, 2+2=2, 1+2=3, 2+1=4   và ta thu đƣợc một số có n chữ số gồm các chữ số 1,2,3,4 với số chữ số 1 bằng số chữ số 2

1221112 1234142 Nhƣ thế, song ánh giữa hai tập hợp đã đƣợc thiết lập và ta có

M N Cách xây dựng song ánh nhƣ trên khá đẹp song hơi cầu kì Chúng ta có một lời giải ngắn gọn hơn nhƣ sau:

Cách giải 2: Để thực hiện, chúng ta cần đánh dấu k trong n vị trí trên một hàng hai lần độc lập Sau khi hoàn tất, tại mỗi vị trí sẽ được ghi các chữ số tương ứng: số 3 nếu vị trí đó được đánh dấu 3 lần, số 4 nếu không được đánh dấu lần nào, số 1 nếu chỉ được đánh dấu ở lần đầu, và số 2 nếu chỉ được đánh dấu ở lần sau.

Khi cho k chạy trên S, tổng số các số thu được là N Đối với mỗi k thuộc S, số cách đánh dấu lần đầu tương ứng với việc chọn k trong n vị trí, trong khi số cách đánh dấu lần sau là chọn n-k vị trí trong n vị trí Do đó, tổng số cách đánh dấu khi k chạy trên S bằng số cách chọn n phần tử từ 2n phần tử, tức là C(2n, n), và giá trị này chính là M, điều cần chứng minh.

2.2.2.4 Bài toán 4 (Vô địch Trung Quốc – 1994):

Để giải bài toán, ta chọn n số từ tập hợp 2^(n+1) Đầu tiên, chia số này thành n cặp và một số x Tiếp theo, bước đầu tiên là chọn k cặp và từ mỗi cặp, ta sẽ thực hiện lựa chọn.

23 ra một số, bước 2: chọn  n  k  / 2  cặp trong n  k cặp còn lại, ngoài ra số x sẽ được chọn nếu n k  lẻ và không được chọn nếu n k  chẵn Rõ ràng bước

1 có 2 k C n k cách chọn và bước 2 có C n    n k  k  / 2  cách chọn và ta chọn được tổng cộng n số, trong đó k chạy từ 0 tới n Lập luận đó cho ta điều phải chứng minh

2.2.2.5 Bài toán 5: Cho trước các số nguyên dương ,m n Tính:

PHƯƠNG PHÁP TRUY HỒI

Trong nhiều tình huống, việc đếm trực tiếp các đối tượng trở nên khó khăn Tuy nhiên, nếu chúng ta thiết lập được mối quan hệ hồi quy giữa số lượng đối tượng cần đếm trong nhóm n và số lượng đối tượng trong các nhóm nhỏ hơn n, thì có thể áp dụng phương pháp này để tính toán số đối tượng trong nhóm lớn bằng cách đếm số lượng trong các nhóm nhỏ hơn, nơi việc đếm dễ dàng hơn.

Phương pháp này chủ yếu tập trung vào việc thiết lập mối quan hệ giữa các yếu tố, thay vì đếm trực tiếp f(n) theo yêu cầu của bài toán.

   , 1 ,  f n f n để từ đó tính đƣợc f n  

2.3.2.1 Bài toán 1 (Bungari-1995): Cho số nguyên 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ố

Lời giải: Gọi S n là số các hoán vị thỏa mãn điều kiện bài toán Để ý rằng số các hoán vị mà a n  n là S n  1 Còn số các hoán vị  a 1 , a 2 , , a n  với

Chú ý rằng S 2 1, từ đó ta có S n  2 n  n  1 Ở bài toán này ta thiết lập hệ thức truy hồi xuất phát từ S n đi đến

S n Trong một số trường hợp ta đi theo hướng ngược lại Chẳng hạn như bài toán sau:

Giả sử F k là tập hợp tấ cả các bộ  A 1 , A 2 , , A k  trong đó A i  i  1 , 2 , , k  là một tập con của  1, 2, , n  (Các tập A 1 , A 2 , , A k có thể trùng nhau) Hãy tính

Lời giải cho bài toán này dựa trên việc xác định số tập con của tập hợp  1, 2, , n  Với mỗi k bộ  A 1 , A 2 , , A k  từ tập  1, 2, , n - 1 , chúng ta có thể thêm hoặc không thêm phần tử n vào các tập A i để tạo ra k bộ mới từ tập  1, 2, , n  Số lượng k bộ  A 1 , A 2 , , A k  của tập  1, 2, , n - 1  là 2  n - 1  k, và có 2 k - 1 cách để thêm n vào k bộ này Do đó, ta có thể tính được S n.

Dễ thấy, S 1  2 k  1 Từ đó bằng qui nạp ta chứng minh đƣợc

2.3.2.3 Bài toán 3: 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 2 phần tử là hai số nguyên liên tiếp

Lời giải: Gọi S_n là tập hợp các tập con không rỗng của tập hợp {1, 2, , n}, trong đó không có hai phần tử nào là hai số nguyên liên tiếp Các phần tử của S_n được chia thành hai nhóm.

Nhóm không chứa   n : số các tập con nhƣ vậy là S n  1

Nhóm chứa phần tử n:   n hoặc  a 1 , a 2 , , a n , n   k  1  Rõ ràng i 1 a  n  i  1,2, , k  nên số các tập con nhƣ vậy là S n  2  1

Số tập con không rỗng của tập  1, 2, ,n  là 2^n - 1 Để tìm số tập con mà trong mỗi tập không có hai phần tử là hai số nguyên liên tiếp, cần áp dụng các quy tắc nhất định trong tổ hợp.

2.3.2.4 Bài toán 4: Có n  1 thí sinh ngồi trên một bàn tròn Hỏi có bao nhiêu cách phát đề sao cho hai thí sinh ngồi cạnh nhau luôn có đề khác nhau, biết rằng trong ngân hàng đề có đúng m m   1  đề và hiển nhiên mỗi đề có nhiều bản

Lời giải: Nhận xét: Do thí sinh ngồi theo vòng tròn nên một cách tự nhiên chúng ta nghĩ tới việc tìm cách cắt vòng tròn thành hàng thẳng

Chứng minh cách 1: Kí hiệu P n là số cách phát đề hợp lệ cho n học sinh a 1 , a 2 , , a n ngồi theo vòng tròn ( một cách phát đề đƣợc coi là hợp lệ

28 nếu mỗi thí sinh đƣợc nhận chỉ một đề và hai thí sinh bất kì ngồi gần nhau thì nhận đƣợc hai loại đề khác nhau)

Ta viết a i  a j  i  j , nếu a i và a j cùng loại đề và a i  a j trong trường hợp ngƣợc lại ta chứng minh:

Xét một cách phát đề hợp lệ cho n  1thí sinh a 1 , a 2 , , a n  1

Nếu a 1  a n thì ta bỏ a n  1 đi ta có một cách phát đề hợp lệ cho n thí sinh  a 1 , a 2 , , a n , và có  m  2 cách phát đề cho a n  1

Nếu a 1  a n thì ta bỏ a n  1 và a n đi ta có một cách phát đề hợp lệ cho

 n  1  thí sinh  a 1 , a 2 , , a n  1  Ta có  m  1  cách phát đề cho  a n , a n  1  để hợp lệ với a n  a 1 Vậy ta có đƣợc (1)

Bằng qui nạp ta chứng minh đƣợc: P n  m  1  n  m  1  1 n

Bài toán tương đương với việc đếm số các dãy   a i  i1, 2 , ,n  thỏa mãn a i  M   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   a i thỏa mãn a i  M ,  i 1,2, ,n và a 1 a 2 ,

2 a a  , …, a n  a 1 , gọi A n , B n lần lƣợt là tập hợp các dãy   a i mà a 1  a n và a n a 1 

Do với mỗi dãy thuộc B n , nếu bỏ đi số a n thì ta đƣợc một dãy thuộc

A n 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 )

Từ đó suy ra điều phải chứng minh

Để tìm số tự nhiên n thỏa mãn các điều kiện: i) n có 1000 chữ số, ii) tất cả các chữ số của n đều là số lẻ, iii) hiệu của hai chữ số liên tiếp bất kỳ của n luôn bằng 2, ta cần xác định các chữ số lẻ có thể là 1, 3, 5, 7, và 9 Với điều kiện hiệu của hai chữ số liên tiếp bằng 2, các cặp chữ số có thể là (1, 3), (3, 5), (5, 7), và (7, 9) Do đó, số n sẽ được tạo thành từ các chữ số lẻ này theo quy tắc nhất định, đảm bảo có tổng cộng 1000 chữ số.

Trong tập hợp S k các số nguyên dương n có k chữ số, các số này thỏa mãn các điều kiện (ii) và (iii) Gọi A k , B k , C k , D k , E k lần lượt là các tập hợp các số tận cùng bởi 1, 3, 5, 7, 9 Nếu từ mỗi số thuộc A k bỏ đi chữ số tận cùng, ta sẽ nhận được một số thuộc B k - 1 Ngược lại, từ mỗi số thuộc B k - 1, nếu bổ sung số 1 làm chữ số tận cùng, ta sẽ có số thuộc A k, do đó A k = B k - 1 Tương tự, từ mỗi số thuộc B k, nếu bỏ đi chữ số tận cùng, ta sẽ nhận được một số thuộc

A k hoặc C k  1 ,nếu ta bổ sung thêm số 3 làm chữ số tận cùng thì nhận đƣợc một số thuộc B k , do đó: B k  A k  1  C k  1

Sử dụng 5 đẳng thức trên, bằng cách thế liên tục, ta có:

2.3.2.6 Bài toán 6 (Dự tuyển IMO -1996): Cho bảng ô vuông

Trong một bảng có kích thước n x n với n > 2, câu hỏi đặt ra là có bao nhiêu cách đánh dấu các ô vuông sao cho trong mỗi hình vuông 2 x 2 có đúng 2 ô vuông được đánh dấu Hai cách đánh dấu được coi là khác nhau nếu có ít nhất một ô vuông được đánh dấu trong cách này nhưng không được đánh dấu trong cách kia.

Lời giải: Gọi S_n là số cách đánh dấu trong bảng n×n Xét tập T gồm các ô vuông trong cột cuối cùng và hàng cuối cùng, ta định nghĩa A_n là cách đánh dấu mà hai ô vuông kề nhau trong T cùng được đánh dấu hoặc cùng không được đánh dấu Ngược lại, B_n là các cách đánh dấu mà các ô vuông trong T được đánh dấu xen kẽ.

Mỗi cách đánh dấu thuộc B_n tương ứng với một cách đánh dấu thuộc B_{n-1}, trong khi mỗi cách đánh dấu thuộc A_n liên quan đến một cách đánh dấu thuộc A_{n-1} và một cách đánh dấu thuộc B_{n-1} Điều này có thể được chứng minh bằng cách xem xét bảng ô vuông (n-1) x (n-1) tạo ra từ bảng n x n sau khi loại bỏ T.

Dễ thấy rằng: S 2  6 , S 3  14 Từ đó bằng qui nạp ta có: S n  8 n  10, n  2.

PHƯƠNG PHÁP ĐỒ THỊ

Trong nhiều bài toán tổ hợp, phương pháp đồ thị là công cụ hữu ích để tìm ra kết quả Để áp dụng phương pháp này, chúng ta cần thực hiện theo các bước cụ thể.

Bước 1: Xây dựng đồ thị G   V E ,  mô tả đầy đủ các thông tin của bài toán, trong đó:

Mỗi đỉnh \( v \) trong tập hợp \( V \) đại diện cho một đối tượng trong bài toán, trong khi mỗi cạnh \( e \) trong tập \( E \) kết nối hai đỉnh \( v_i \) và \( v_j \), thể hiện mối quan hệ giữa các đối tượng tương ứng được biểu diễn bởi \( v_i \) và \( v_j \).

+ Vẽ đồ thị G   V E ,  mô tả bài toán (nếu đƣợc)

Bước 2: Sử dụng các định nghĩa, định lí, tính chất đã biết về lí thuyết đồ thị để suy ra điều cần giải (hoặc chứng minh)

2.4.2.1.Bài toán 1 Chứng minh rằng một đồ thị n đỉnh và k cạnh thì sẽ có ít nhất  4 2 

Để tính số tam giác trong đồ thị, ta đánh số các đỉnh từ 1 đến n và giả sử đỉnh i có bậc d_i Nếu hai đỉnh i và j được nối với nhau bằng một cạnh, thì giữa chúng sẽ có ít nhất d_i + d_j - 2 cạnh khác nối đến n - 2 đỉnh khác Do đó, số tam giác có i và j làm hai đỉnh ít nhất phải là d_i + d_j - n Từ đó, tổng số tam giác trong đồ thị sẽ được xác định.

(tổng lấy theo cạnhij) Mà       i i i j i d d d 2 Vậy tổng các tam giác bé nhất phải là   i i nk d 3

( trường hợp đặc biệt của bất đẳng thức Chebyshev)

Suy ra điều phải chứng minh

2.4.2.2 Bài toán 2 (IMO Shortlist 1990): Một tập hợp gồm 1990 người đƣợc chia thành các tập con rời nhau sao cho:

1 Không người nào trong một tập con quen biết tất cả các người nằm trong tập con đó

2 trong nhóm 3 người bất kì thuộc cùng một tập con luôn tồn tại ít nhất 2 người không quen biết nhau

3 Với bất kì một nhóm 2 người nào trong một tập con mà không quen biết lẫn nhau tồn tại đúng một người trong cùng tập con đó quen biết cả 2 người này a) Chứng minh rằng trong mỗi tập con, mỗi người đều có cùng một số người quen biết b) Tìm số lớn nhất các tập con có thể chia đƣợc

Chú ý: Ta giả thiết rằng nếu A quen biết B thì B cũng sẽ quen biết

A Ta cũng hiểu rằng mỗi người thì có quen biết với chính họ

Đề bài yêu cầu giải bằng đồ thị, trong đó mỗi người được biểu diễn như một đỉnh và mối quan hệ quen biết là cạnh nối các đỉnh Câu hỏi a không liên quan đến số 1990 mà chỉ tập trung vào một tập con với các điều kiện 1, 2 và 3 Tương tự, câu b chỉ liên quan một phần đến số 1990, điều này thường thấy trong các đề thi toán, nơi người ra đề thường chọn số giống năm thi.

Bây giờ ta phát biểu bài toán tương tự sau đây:

Cho đồ thị gồm n đỉnh thỏa mãn các điều kiện sau:

(1) không có đỉnh nào có thể đƣợc nối cạnh với tất cả các đỉnh khác

(2) Không tồn tại tam giác nào trong đồ thị,

(3) Với hai đỉnh bất kì A, B mà không có cạnh AB, tồn tại đúng một đỉnh C để cho ta có các cạnh AB và AC

Chứng minh rằng mọi đỉnh đều có cùng số các cạnh Tìm số n bé nhất có thể đƣợc

Giải bài toán tương tự:

Hai đỉnh A và B được nối với nhau nếu có cạnh AB tồn tại Đối với mỗi đỉnh X, ký hiệu degX biểu thị số bậc của X, tức là số cạnh nối với X Nếu ta xem xét đỉnh A bất kỳ với degA = m, thì sẽ có m đỉnh B, được ký hiệu là B1, B2, , Bm, nối với A.

Theo điều kiện 2, không có tam giác nên khi i khác j, các đỉnh B i và B j không thể nối với nhau Theo điều kiện 3, một đỉnh C khác A cũng không thể nối với B i và B j khi i khác j Do đó, có degB i - 1 đỉnh.

C ij nối đƣợc với B i , và tất cả các đỉnh C ij đều phân biệt nhau

Chỉ những đỉnh có thể kết nối với C ij mà không kết nối với B i được xác định, đó là các đỉnh C hk khác Tuy nhiên, C ij không thể kết nối với C ik và cũng không nối được với hai đỉnh khác nhau C kh và C kh ', do đó nó chỉ có thể kết nối với tối đa một đỉnh C kh với mọi k khác i Theo quy định, phải có một đỉnh X kết nối với cả B k lẫn.

C ij (với k ≠ i) chỉ có thể kết nối với các đỉnh B k, cụ thể là A và C kh Điều này dẫn đến kết luận rằng C ij phải kết nối với ít nhất một đỉnh C kh cho mọi k ≠ i Do đó, suy ra rằng deg C ij = m.

Nếu bắt đầu từ đỉnh B thay vì đỉnh A và áp dụng lại toàn bộ lý thuyết trước đó, ta sẽ nhận được deg B i tương tự như deg C hk, trong đó C hk là một trong các đỉnh kết nối với C ij.

Vậy tất cả mọi đỉnh đều có cùng bậc

Bậc của mỗi đỉnh được ký hiệu là m, trong đó có một đỉnh A m, một đỉnh B i và m m   1  đỉnh C jk, tổng cộng là m 2 1 đỉnh Khi đó, n = m 2 1 Giá trị nhỏ nhất của m là 1, nhưng không thỏa mãn điều kiện của đồ thị Giá trị nhỏ nhất tiếp theo là m = 2, dẫn đến 5 đỉnh, và dễ dàng kiểm tra rằng ngũ giác này thỏa mãn 3 điều kiện của bài toán.

Vậy n5 là giá trị bé nhất cần tìm

Trở lại bài toán ban đầu

Phần đầu của bài toán cải biên đã chứng minh cho câu   a với câu

  b , rõ ràng giá trị lớn nhất các tập con chia đƣợc thỏa mãn điều kiện đề bài là 1990: 5 398 

2.4.2.3 Bài toán 3: Trên một hình chữ nhật có kẻ ô, hãy chứng tỏ rằng một đường đi xuất phát từ góc Tây Bắc đi xuyên qua mỗi điểm mắc lưới trên hình chữ nhật kẻ ô đúng một lần, và kết thúc tại góc phía đông nam, thì đường đi đó sẽ chia hình chữ nhật kẻ ô thành 2 nửa bằng nhau mà: a) Một nửa thì mở ra ở hướng bắc hoặc đông (tức là tại đó đường đi không khép kín) b) Nửa còn lại mở ra hướng nam hoặc tây

Đồ thị minh họa một đường dẫn phù hợp với điều kiện của bài toán cho hình chữ nhật có kích thước 5x8 Trong đó, miền được tô đen mở ra theo hướng bắc hoặc đông, trong khi miền còn lại mở ra theo hướng nam hoặc tây.

Xét một đường đi trong bài toán, ta có những tính chất quan trọng sau: đầu tiên, số cạnh của đường đi là nm - 1 Tiếp theo, bằng phương pháp qui nạp, ta nhận thấy mỗi miền có s hình vuông sẽ kề với 2s + 1 cạnh của đường đi Cuối cùng, các cạnh nằm ở phía bắc hoặc đông của hình kẻ ô mà không nằm trên đường đi sẽ tương ứng với đúng một miền tô đen.

Gọi số các miền được tô đen là k và số ô vuông tương ứng trong mỗi miền là s1, s2, , sk Từ đó, ta có thể xác định số cạnh của đường đi hướng bắc hoặc đông trong hình kẻ ô.

Từ đó, theo (ii), tổng số các cạnh của đường đi là:

Nhƣ vậy tổng số các ô vuông đƣợc tô đen là:

PHƯƠNG PHÁP HÀM SINH

Hàm sinh có những ứng dụng hết sức đặc sắc trong toán học nói chung và trong tổ hợp nói riêng

Cho dãy số thực   a n Ta gọi tổng hình thức

S là một chuỗi lũy thừa

Chuỗi lũy thừa S x   gọi là hội tụ trên tập X nếu với mọi xX , dãy số   

Khi chuỗi lũy thừa S x   hội tụ, ta đƣợc hàm số f x   xác định bởi

Hàm số f x   nói trên gọi là hàm sinh của dãy   a n đã cho

Mệnh đề 1: Xét dãy a n  1 , n  0 Ta có:

Mệnh đề 2 Xét dãy a 0 1, a 1 2, a 2 3, , a n  n 1, Ta có:

2.5.1.2.Khai triển Taylor Định lí: Cho hàm số f x   có đạo hàm mọi cấp tại xa Khi đó ta có khai triển:

 f a x a a a x a f f x f Đặc biệt, khi a0 ta có:

2.5.1.3.Hệ số nhị thức mở rộng

 k u Cho u là một số thực và k là số nguyên không âm Ta định nghĩa

Với công thức hệ số nhị thức mở rộng đƣợc định nghĩa nhƣ trên ta có khai triển

1 k u k k x x u trong đó u là số thực tùy ý và x 1

2.5.2 Các ứng dụng Đối với một số bài toán đếm, ta qui về xác định công thức tường minh của một dãy số bởi công thức truy hồi Sử dụng hàm sinh của dãy, bằng việc khai triển một hàm số bằng hai cách khác nhau và so sánh hệ số của cùng một lũy thừa của x, ta có thể dễ dàng xác định đƣợc công thức tường minh của dãy đã cho Đó cũng chính là ý tưởng cơ bản của phương pháp hàm sinh Để làm quen với phương pháp này, ta làm một số bài toán sau:

2.5.2.1 Bài toán 1: Xét dãy Fibonacci a 0  a 1  1 , a n  a n  1  a n  2 , n2

Tìm công thức tường minh của hạng số tổng quát x n ?

Bây giờ ta đi khai triển hàm số S x   theo chuỗi lũy thừa Để khai triển S x   theo chuỗi lũy thừa ta biểu diễn S x   qua các hàm cơ bản Ta có:

So sánh hệ số của x n ta suy ta:

Cho dãy   a n xác định bởi:

2.5.2.3 Bài toán 3: giả sử ta có một lƣợng đủ lớn các loại hoa quả gồm táo, mận, lê, đào Hỏi có bao nhiêu cách sắp xếp một giỏ gồm n trái cây thỏa mãn các yêu cầu sau đây:

 Số quả táo phải chẵn

 Số quả mận phải chia hết cho 5

 Số quả lê không vƣợt quá 4

 Số quả đào không nhiều hơn 1

Gọi a_n, b_n, c_n, d_n lần lượt là số cách chọn n quả táo, mận, lê, đào theo yêu cầu bài toán Do đó, tổng số cách chọn n trái cây thỏa mãn yêu cầu là: n p q r s p q r s n.

Hàm sinh của dãy   a n là:   2 4 2

Hàm sinh của dãy   b n là:   5 10 15 5

Hàm sinh của dãy   c n là:   x x x x x x x

Hàm sinh của dãy   d n là: D   x  1  x

S nên hàm sinh của dãy S n là:

S   theo chuỗi lũy thừa ta có:

2.5.2.4 Bài toán 4: Tìm số nghiệm nguyên không âm của phương trình x 1  x 2   x n  m , trong đó ,m n là các số nguyên dương cho trước

Lời giải: Gọi a p q  ,  là số cách chọn x p q Khi đó, số nghiệm của phương trình đã cho là:

Vì a p q  ,    1, p q , nên với mỗi p, hàm sinh của dãy a p q  ,  là:

Suy ra hàm sinh của dãy S m là:

Khai triển S x   theo chuỗi lũy thừa ta đƣợc:

2.5.2.5 Bài toán 5: Có bao nhiêu cách đổi n dollars thành các đồng 1 dollars và 2dollars?

Gọi a(n) là số cách đổi n dollar thành các đồng 1 dollar, và b(n) là số cách đổi n dollars thành các đồng 2 dollars Số cách đổi n dollars thành các đồng 1 và 2 dollars được tính bằng tổng a(n) và b(n).

Hàm sinh của dãy   a n là:

Hàm sinh của dãy   b n là:

Suy ra hàm sinh của dãy S n là:

Bây giờ ta đi khai triển hàm số S x   thành chuỗi lũy thừa Ta có:      

2.5.2.6 Bài toán 6: Cho n1 Hỏi có bao nhiêu đa thức P x   có hệ số thuộc tập hợp  0,1, 2,3  thỏa mãn P   2  n

Lời giải: Đặt P   x  c 0  c 1 x  c 2 x 2   c m x m , trong đó c i   0 , 1 , 2 , 3 ,  i  1 ; m

Ta có: P   2  n  c 0  2 c 1  2 2 c 2   2 m c m  n Do đó số đa thức thỏa mãn yêu cầu bài toán bằng số bộ  c c 0; ; ;1 c m   0,1,2,3 thỏa mãn n c c c c 0 2 1 2 2 2  2 m m 

Do c i   0 , 1 , 2 , 3  nên hàm sinh của số cách chọn 2 i c i là:

Gọi S n là số đa thức P x   thỏa mãn yêu cầu bài toán Ta có hàm sinh của dãy   S n là:

Theo bài trên ta có 1

PHƯƠNG PHÁP TỔNG HỢP

Ngoài các phương pháp đã đề cập, chúng ta có thể giải quyết các bài toán tổ hợp bằng cách sử dụng công thức nhị thức Newton, nguyên lý Dirichlet, và số phức Tuy nhiên, một số bài toán tổ hợp yêu cầu khả năng suy luận cao, kết hợp nhiều kiến thức liên quan và sự kết hợp linh hoạt của các phương pháp đã nêu.

2.6.2.1.Bài toán 1 (Đề thi HSG tỉnh Hà Tĩnh 2007-2008)

Sử dụng đẳng thức C k n C n k  1 C n k   1 1  k , n  N * , n  k  1, ta có:

Ta cần chứng minh: C 2 n n   1 2 chia hết cho n  2  n N * Đặt n  1  k  k  N * , k  2 , ta chứng minh: C 2 k k chia hết cho k  1 hay

2.6.2.2 Bài toán 2 (Đề thi HSG tỉnh Hà Tĩnh 2008-2009)

Chứng minh rằng với mọi số nguyên n  2 ta luôn có:

Trong đó, C n k là số tổ hợp chập k của một tập hợp có n phần tử

Lời giải: +) Với n  2, n  3 thay vào ta thấy thỏa mãn

+) Với n  3 Áp dụng bất đẳng thức Bunhia kôpxky ta có:

Ta chỉ cần chứng minh     2 3

2.6.2.3 Bài toán 3 (Đề thi hsg tỉnh Hà Tĩnh 2009-2010): Sau khi khai triển và rút gọn thì biểu thức sau có bao nhiêu số hạng:

Lời giải: Số hạng tổng quát của

T T 1 , 2 rút gọn đƣợc nếu số mũ của x ở T T 1 , 2 bằng nhau hay

Từ (1) suy ra  10  n  chia hết cho 3 Do m n, N và 0  10  n  10 nên có các khả năng sau xảy ra:

Vậy, khai triển và làm gọn thì biểu thức A giảm đi 3 số hạng, nên số số hạng còn lại là 21 11 3 29    (số hạng)

2.6.2.4 Bài toán 4 (Đề thi hsg tỉnh Hà Tĩnh 2010-2011): a) Tìm hệ số của số hạng chứa x 4 trong khai triển:  1 2  x  3 x 2  10 b) Tính tổng: 1

Nhận xét: từ số hạng thứ tƣ trở đi ở khai triển trên không chứa x 4 nữa

Vậy hệ số của số hạng chứa x 4 là: C 10 0 C 10 4 16  3 C 10 1 C 9 2 4  9 C 10 2 C 8 0  8085 b) Ta có

Cộng theo vế n  1 đẳng thức trên ta có: 1

2.6.2.5 Bài toán 5: Cho một dãy gồm 19 số nguyên dương không vượt quá

Trong một dãy số gồm 93 số nguyên dương không vượt quá 19, có thể chứng minh rằng từ hai dãy số này, ta có thể chọn ra hai dãy con sao cho tổng các số hạng của chúng bằng nhau.

Ta xét bài toán tổng quát:

Cho hai dãy (hữu hạn) các số nguyên dương: x 1    x 2 x m  n , y 1  y 2   y n  m

Khi đó, tồn tại các “chỉ số” 1    i 1 i 2 m , 1    j 1 j 2 n sao cho

Giải bài toán tổng quát: Đặt a p : i p  1 x i  p  Z ,1   p m  và q : q 1 j b  j  y  q  Z ,1   q n 

Thay đổi vai trò của các “kí tự” x a m i p, , , , tương ứng với các kí tự

, , , , y b n j q nếu cần, ta có thể xem rằng a m  b n Khi đó, với mỗi

  1, p  m , tồn tại f p   :    q   1, n là chỉ số bé nhất mà a p b q

Trước hết, ta có nhận xét rằng mọi hiệu đều bé hơn m Thật vậy, nếu có một chỉ số p   Z   1, m nào đó sao cho mb f p   a p , thì mb f p   nên

  mâu thuẫn với định nghĩa của f p   Mâu thuẫn đó chứng tỏ rằng quả thực, mỗi hiệu ở (1) là bé hơn n

Nếu một trong các hiệu b f p   a p 0 triệt tiêu, ta sẽ có ngay đpcm với cách chọn i 1: 1 : , :  j i 1 2  p j, :2  f p   Trong trường hợp còn lại, toàn bộ m hiệu ở (1) đều thuộc.

  , một tập hợp chỉ có m1 phần tử, nên theo nguyên lí Dirichlet, có hai hiệu bằng nhau; tức là, tồn tại r s ,     1, m , r  s để: b f r    a r b f s   a s

b f r   b f s    a r a s và ta cũng có đpcm, với i 1: s 1, :i 2 r j, :1  f s  1, :j 2  f r  

Cho n điểm trong mặt phẳng, với n4 và không có ba điểm nào thẳng hàng Chứng minh rằng có ít nhất

2 n n tứ giác lồi có đỉnh nằm trong số n điểm đã cho

Khi xem xét 5 điểm bất kỳ mà không có 3 điểm nào thẳng hàng, ta có thể vạch ra một bao lồi từ những điểm này Nếu bao lồi chứa hơn 3 điểm, sẽ có ít nhất một tứ giác lồi xuất hiện Ngược lại, nếu bao lồi chỉ gồm 3 điểm, ví dụ như A, B, C, thì không thể tạo thành tứ giác lồi.

Trong tam giác ABC, hai điểm D và E nằm trong cùng một nửa mặt phẳng với đường thẳng DE, trong khi các điểm còn lại sẽ nằm bên trong tam giác.

D E, hai đỉnh đó tạo thành một tứ giác lồi Nhƣ vậy, mệnh đề cần chứng minh đúng với n5

Xét n điểm với n5 Vì không có 3 điểm nào thẳng hàng nên số tất cả cách chọn n điểm nhƣ trên là:

Mỗi cách chọn điểm cho phép tạo ra ít nhất một tứ giác lồi Tuy nhiên, bất kỳ tứ giác lồi nào cũng có thể được hình thành từ (n - 4) tập hợp khác nhau của 5 điểm đã cho, do đó, số lượng tứ giác lồi tối thiểu là rất đa dạng.

  số tất cả các tứ giác lồi đƣợc thành lập từ n điểm đã cho Để kết thúc chứng minh, ta sẽ chứng tỏ rằng:

 với n5 Điều phải chứng minh này tương đương với:

Dễ dàng thấy rằng các số n5 và n6 là nghiệm của phương trình n n   1  n  2   60  n  4   0, do đó, ta có thể phân tích thành nhân tử nhƣ sau: n n   1  n  2   60  n  4    n  5  n  6  n  8 

Với mọi n nguyên dương và 5, ta lập bảng xét dấu, dễ thấy dấu của  n  5  n  6  n  8  cũng là dấu của  n  5  n  6 

Và ta đƣợc  n  5  n  6   0 khi n  5, 6;  n  5  n  6   0 khi

6 n , suy ra điều phải chứng minh