Dùng ánh xạ trong các bài toán Tổ hợp


Để đếm số phần tử của một tập hữu hạn A, ta tìm một tập hữu hạn B có cùng số phần tử như A nhưng dễ đếm hơn.

Nguyên lý ánh xạ. Cho AB là các tập hữu hạn khác rỗng và f:A\to B là một ánh xạ. Khi đó

a)Nếu f là đơn ánh thì |A|\leq |B|;

b)Nếu f là toàn ánh thì |A|\geq |B|;

c)Nếu f là song ánh thì |A|=|B|.


Bài 7.1. Chứng minh rằng số các tập con của tập có n(n\in\mathbb{N}) phần tử bằng 2^n.

Hướng dẫn. Có một song ánh với tập các xâu nhị phân độ dài n\Box.

Bài 7.2. Cho m,n là các số nguyên lớn hơn 1S là một tập có n phần tử. Giả sử có các tập con A_1,A_2,\cdots,A_m của S thoả mãn: Với mỗi hai phần tử x,y\in S, có tập A_i sao cho x\in A_i,y\not\in A_i hoặc x\not\in A_i,y\in A_i. Chứng minh rằng n\leq 2^m.

Lời giải. Gọi T là tập các xâu nhị phân độ dài m. Xét ánh xạ f:S\to T xác định theo quy tắc sau: Nếu x\in S thì f(x)=(x_1,x_2,\cdots,x_{m})\in T, ở đây x_i=1 nếu x\in Ax_i=0 nếu x\not\in A. Dễ thấy đây là đơn ánh \Box.

Bài 7.3. Cho m,n là các số nguyên dương và một bảng ô vuông cỡ m\times n. Giả sử A,B là hai trong các đỉnh của các ô vuông nhỏ của bảng, một đường đi từ A đến B là một dãy điểm D_0D_1\cdots D_k sao cho D_iD_{i+1} là cạnh của một ô vuông con(có thể là cạnh chung của hai ô vuông con) và D_0=A,D_k=B; khi đó k gọi là độ dài của đường đi đó. Tính số các đường đi ngắn nhất nối đỉnh dưới bên trái và đỉnh trên bên phải của bảng ô vuông.

Hướng dẫn. Đường đi ngắn nhất phải là đường đi có độ dài m+n vì muốn đến đỉnh trên bên phải thì đường đi phải lên m lần và ngang n lần. Có một song ánh giữa tập các đường ngắn nhất trên và tập các xâu nhị phân độ dài m+n mà có đúng m số 0n số 1. Cụ thể là một bước đi ngang ta cho ứng với số 0, một bước đi lên ta cho ứng với 1. Đáp số của bài toán là C_{m+n}^m\Box.

Bài 7.3. Cho n là một số nguyên dương và X=\{1,2,\cdots,n\}. Chứng minh rằng số r-tổ hợp của X không chứa hai số nguyên liên tiếp là C_{n-r+1}^r. Trong đó r là số nguyên thoả mãn 0\leq r\leq n-r+1.

Lời giải. Có một song ánh giữa tập cần đếm và tập các r-tổ hợp của tập \{1,2,\cdots,n-r+1\}. Song ánh đó được xác định như sau \{s_1,s_2,\cdots,s_r\}\longmapsto \{s_1,s_2-1,\cdots,s_r-(r-1)\},

ở đây ta đã giả sử s_1<s_2<\cdots<s_r\,\,\Box.

Bài 7.4(IMO 1989). Cho n là một số nguyên dương.

Một hoán vị x_1x_2\cdots x_{2n} của tập \{1,2,\cdots,2n\} được gọi là có tính chất P nếu |x_i-x_{i+1}|=n với ít nhất một i\in\{1,2,\cdots,2n-1\}. Chứng minh rằng với mỗi số nguyên dương n, số các hoán vị có tính chất P nhiều hơn số hoán vị không có tính chất đó.

Hướng dẫn. Xét n>1. Gọi A là tập các hoán vị không có tính chất PB là tập các hoán vị có tính chất P. Ta xây dựng một ánh xạ f:A\to B sao cho f là đơn ánh nhưng không phải toàn ánh. Nếu x_1x_2\cdots x_{2n} không có tính chất P thì chỉ có duy nhất một r>2 sao cho |x_1-x_r|=n. Ta cho hoán vị này ứng với hoán vị x_2x_3\cdots x_1x_r\cdots x_{2n}. Dễ thấy đây là đơn ánh. Nó không phải là toàn ánh vì trong B có thể có các hoán vị có hai cặp có khoảng cách bằng n\,\,\Box.

Bài 7.5. Cho n là một số nguyên dương. Có bao nhiêu cách viết n thành tổng của ít nhất hai số nguyên dương? Ở đây thứ tự các số hạng được quan tâm.

Hướng dẫn. Xét sơ đồ sau (1-1-1-\cdots -1-1)

với n số 1. Ở giữa các số 1 này có n-1 vị trí trống. Trong các vị trí trống này ta điền dấu “+” hoặc dấu “)+(“. Mỗi cách điền ứng với một cách biểu diễn n, trừ cách điền n-1 dấu “+“. Vậy đáp số của bài toán là 2^{n-1}-1\,\,\Box.

Bài 7.6. Cho m,n là các số nguyên dương. Chứng minh rằng có

a)C_{n-1}^{m-1} bộ (x_1,x_2,\cdots,x_m) các số nguyên dương thoả mãn x_1+x_2+\cdots+x_m=n;

b)C_{n+m-1}^{m-1} bộ (x_1,x_2,\cdots,x_m) các số nguyên không âm thoả mãn x_1+x_2+\cdots+x_m=n.

Hướng dẫn. Câu a) sẽ được giải như trên. Giờ ta quan tâm đến b). Ta có thể viết lại phương trình trên như là (x_1+1)+(x_2+1)+\cdots+(x_m+1)=m+n

và dùng a). Hoặc ta có thể làm như sau: Giả sử ta có m+n-1 hình tròn trên một đường thẳng. Ta tô đen m-1 trong chúng. Giả sử c_1,c_2,\cdots,c_{m-1} là các hình tròn đen được đánh số từ trái sang phải. Với mỗi 1\leq i\leq m-2, gọi x_i là số hình tròn trắng ở giữa c_ic_{i+1}; x_1 là số hình tròn trắng bên trái c_1; x_m là số hình tròn trắng bên phải c_{m-1}. Dễ thấy ta có một song ánh \Box.

Bài 7.7(APMO 1998). Cho k là một số nguyên dương và F là tập các bộ (A_1,A_2,\cdots, A_k) các tập con của tập \{1,2,\cdots,1998\}. Tính tổng

S=\sum_{(A_1,A_2,\cdots,A_k)\in F}|A_1\cup A_2\cup\cdots\cup A_k|.

Lời giải. Bài toán này không dùng phương pháp song ánh theo nghĩa thường, ở đây sẽ không có ánh xạ nào cả. Nguyên lý ánh xạ ở đây được dùng bằng cách, thay vì tính tổng này ta tìm cách tính một tổng khác dễ hơn và có giá trị bằng tổng đã cho. Với mỗi i=1,2,\cdots,1998 ta gọi S_i là số các bộ trong Fi thuộc hợp các phần tử của họ. Rõ ràng trong S thì i được đếm S_i lần, do đó S=\sum S_i. Dễ thấy các S_i bằng nhau và bằng 2^{1997k}(2^k-1) và tổng cần tính bằng 1998\times 2^{1997k}(2^k-1)\,\,\Box.

Bài 7.8. Cho n là một số nguyên dương. Giả sử M là tập tất cả các số nguyên dương viết trong hệ thập phân có n chữ số 1, n chữ số 2 và không có chữ số nào khác; N là tập tất cả các số nguyên dương viết trong hệ thập phân gồm n chữ số, chỉ chứa các chữ số 1,2,3,4 và số các số 1 bằng số các số 2. Chứng minh rằng |M|=|N|.

Hướng dẫn. Ta sẽ chứng minh có song ánh giữa MN. Lấy một số trong N viết liền nhau hai số này ta được một số có 2n chữ số. Sau đó các số 3 trong phần đầu thay bằng 2, phần sau thay bằng 1 và các số 4 trong phần đầu thay bằng 2 các số 4 trong phần sau thay bởi 1. Đây là một song ánh \Box.

Bài 7.9. Cho n>1 là một số nguyên dương và S là dãy số 1,2,\cdots,n. Một dãy con của S được gọi là cấp số cộng cực đại của S nếu nó là một cấp số cộng và dãy này không thể thành một cấp số cộng dài hơn bằng cách bổ sung một phần tử. Hỏi có bao nhiêu cấp số cộng cực đại của S?

Hướng dẫn. Xét n=2m. Ta có thể chứng minh rằng nếu a_1,a_2,\cdots,a_k là một cấp số cộng cực đại thì a_1\leq ma_k\geq m+1. Suy ra có số i để a_i\leq m<m+1\leq a_{i+1}, ta cho dãy ứng với cặp (a_i,a_{i+1}) này. Đây là một song ánh và trong trường hợp này ta có kết quả m^2. Khi n=2m+1 ta có kết quả m(m+1). Như vậy đáp số của bài toán là [n^2/4]\Box.

Bài 7.10. Cho A=\{a_1,a_2,\cdots,a_{100}\}B=\{1,2,\cdots,50\}. Hỏi có bao nhiêu ánh xạ f:A\to B sao cho f toàn ánh và

f(a_1)\leq f(a_2)\leq\cdots\leq f(a_{100})?

Nếu f không cần toàn ánh thì sao?

Hướng dẫn. Mỗi hàm như vậy sẽ ứng với một dãy (x_1,x_2,\cdots,x_{50}) ở đây x_k là số các i để f(a_i)=k với k=1,2,\cdots,50\,\,\Box.

Bài 7.11(Putnam 2002). Cho n>1 là một số nguyên dương và T_n là số các tập con khác rỗng của tập \{1,2,\cdots,n\} sao cho trung bình cộng tất cả các phần tử của nó là một số nguyên. Chứng minh rằng T_n-n là một số chẵn.

Hướng dẫn. Có n tập con 1 phần tử và các tập này đều thoả mãn điều kiện trong đầu bài. Vậy ta chỉ cần chứng minh số các tập con nhiều hơn một phần tử có tính chất đó là một số chẵn là xong. Ta hãy ghép các tập con này thành từng cặp như sau: Các tập có trung bình thuộc nó đi với một tập có trung bình không thuộc nó \Box.

1 thought on “Dùng ánh xạ trong các bài toán Tổ hợp”

  1. cho em hỏi rõ bài cuối cùng ạ, bài putnam 2002
    thầy có thể giải chi tiết hơn được không ạ

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s