Nguyên lý bù-trừ 2


Bài viết xem như sự mở đầu của phương pháp SÀNG trong các bài toán đếm. Ở phương pháp này, khi muốn đếm số phần tử của một tập A, ta bắt đầu với một tập B chứa A, sau đó tìm cách loại đi các phần tử không nằm trong A.

Chúng ta biết rằng nếu AB là các tập hữu hạn rời nhau thì |A\cup B|=|A|+|B|, tổng quát hơn ta có: Nếu AB là các tập hữu hạn bất kỳ(không nhất thiết rời nhau) thì  |A\cup B|=|A|+|B|-|A\cap B|, đây chính là nguyên lý bù-trừ cho hai tập hợp, dễ hiểu tại sao người ta lại gọi đây là nguyên lý bù trừ. Với n>1 tập hợp ta có định lý sau

Định lý. Nếu A_1,A_2,\cdots,A_n là các tập hữu hạn thì

|\cup_{i=1}^nA_i|=\sum_{1\leq i\leq n}|A_i|-\sum_{1\leq i<j\leq n}|A_i\cap A_j|+\cdots+(-1)^{n+1}|\cap_{1\leq i\leq n}A_i|.

Ta sẽ chứng minh rằng rằng mỗi phần tử trong \cup_{i=1}^nA_i được đếm đúng một lần trong vế phải. Gọi x là một phần tử trong hợp đó và nó nằm trong dúng m tập A_i, khi đó trong vế phải nó sẽ được đếm đúng C_m^1-C_m^2+\cdots+(-1)^{m+1}C_m^m=1

lần (lưu ý (1-1)^m=0). Định lý được chứng minh.

Ngoài cách chứng minh trên các bạn có thể chứng minh Định lý bằng phương pháp quy nạp toán học, tôi chọn giới thiệu cách chứng minh đó vì phong cách Tổ hợp của nó.

Một áp dụng đẹp của nguyên lý bù-trừ là bài toán Bernoulli-Euler về các bức thư sai địa chỉ: Có n>1 bức thư khác nhau phải gửi đến n địa chỉ khác nhau. Có bao nhiêu cách gửi mà các bức thư đều đến không đúng địa chỉ của mình? Theo ngôn ngữ ánh xạ, bài toán được phát biểu như sau: Có bao nhiêu song ánh từ S=\{1,2,\cdots,n\} đến chính S sao cho nó không có điểm cố định? Ta đếm số các song ánh có điểm cố định, số này bằng C_n=|\cup_{1\leq i\leq n}A_i|, ở đây A_i là tập các song ánh nhận i làm điểm cố định. Theo nguyên lý bù-trừ dễ có C_n=\sum_{k=1}^nC_n^k(-1)^{k+1}(n-k)! và đáp số của bài toán là D_n=n!-C_n.

Bài tập.

Bài 10.1. Tìm số các số nguyên dương trong \{1,2,\cdots,500\} chia hết cho 2 hoặc 3 hoặc 5.

Bài 10.2. Tính giá trị của phi hàm Euler tại n theo phân tích chính tắc của n.

Bài 10.3. Chứng minh nguyên lý bù-trừ bằng quy nạp toán học.

Bài 10.4. Cho X là một tập hữu hạn và A,B,C là các tập con của nó. Chứng minh rằng |\bar{A}\cap B|=|B|-|A\cap B||\bar{A}\cap\bar{B}\cap C|=|C|-|A\cap C|-|B\cap C|+|A\cap B\cap C|.

Bài 10.5. Tìm số các số nguyên trong tập \{1,2,\cdots,1000\} không chia hết cho 5, không chia hết cho 7, nhưng chia hết cho 3.

Bài 10.6. Có bao nhiêu số nguyên dương n sao cho n là ước của ít nhất một trong hai số 10^{40}20^{30}?

Bài 10.7. Với mỗi số nguyên dương n>1, gọi A_n là số các song ánh từ S đến S sao cho f(k) khác k+1 với mỗi k=1,2,\cdots,n-1.

a)Tính A_n;

b)Chứng minh rằng A_n=D_n+D_{n-1} với mỗi n>1.

Bài 10.8. Tìm số các số nguyên dương là ước của ít nhất một trong các số 10^{60},20^{50},30^{40}.

Bài 10.9. Với k=1,2,\cdots,1992 cho A_k là một tập với 44 phần tử. Giả sử rằng |A_i\cap A_j|=1 với mỗi i,j khác nhau trong \{1,2,\cdots,1992\}. Tính |\cup_{i=1}^{1992}A_i|.

Bài 10.10. Cho A_1,A_2,\cdots,A_nn tập hữu hạn. Chứng minh rằng

|\cup_{i=1}^nA_i|\geq \sum_{i=1}^n|A_i|-\sum_{1\leq i<j\leq n}|A_i\cap A_j|.

Sử dụng bất đẳng thức này để giải bài toán sau: Một hoán vị của \{1,2,\cdots,2n\} được gọi là có tính chất P nếu có ít nhất hai số dạng k,n+k đứng cạnh nhau. 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ố các hoán vị không có tính chất đó.

Bài 10.11. Cho các số nguyên dương m\leq nA,B là các tập có n,m phần tử tương ứng. Tìm số các toàn ánh từ A lên B. Từ đó suy ra \sum_{k=0}^n(-1)^kC_n^k(n-k)^n=n!.

Bài 10.12. a) Cho A là một tập hữu hạn và f là một hàm từ A đến \mathbb{R}. Với mỗi tập con B của A ta đặt f(B)=\sum_{x\in B}f(x)f(\emptyset)=0. Chứng minh rằng nếu A=\cup_{i=1}^nA_i thì f(A)=\sum_{I\not =\emptyset}(-1)^{|I|+1}f\left(\cap_{i\in I}A_i\right),

ở đây tổng chạy trên các tập con của \{1,2,\cdots,n\};

b) Cho n>1 là một số nguyên và a_1,a_2,\cdots,a_{\varphi (n)} là các số trong tập \{1,2,\cdots,n\} nguyên tố cùng nhau với n. Chứng minh rằng

a_1^2+a_2^2+\cdots+a_{\varphi (n)}^2=\dfrac{\varphi (n)}{6}(2n^2+(-1)^kp_1p_2\cdots p_k),

ở đây p_1,p_2,\cdots,p_k là các ước nguyên tố phân biệt của n.

Bài 10.13. Tìm số các lời giải nguyên không âm của x_1+x_2+x_3=15 với x_1\leq 5,x_2\leq 6x_3\leq 7.

Bài 10.14. Tìm số nghiệm nguyên của phương trình x_1+x_2+x_3=28 với 3\leq x_1\leq 9,0\leq x_2\leq 87\leq x_3\leq 17.

Bài 10.15. Tìm số nghiệm nguyên của phương trình x_1+x_2+x_3=40 với 6\leq x_1\leq 15, 5\leq x_2\leq 2010\leq x_3\leq 25.

Bài 10.16. Tìm số lời giải nguyên của phương trình x_1+x_2+x_3+x_4=20 thoả mãn 1\leq x_1\leq 5,0\leq x_2\leq 7,4\leq x_3\leq 82\leq x_4\leq 6.

Bài 10.17. Cho k,n,r là các số nguyên dương. Chứng minh rằng số nghiệm nguyên của phương trình

x_1+x_2+\cdots+x_n=r

sao cho 0\leq x_i\leq k với mỗi i bằng

\sum_{i=0}^n(-1)^iC_n^iC_{r-(k+1)i+n-1}^{n-1},

và nếu thay điều kiện bởi 1\leq x_i\leq k với mỗi i thì số nghiệm bằng

\sum_{i=0}^n(-1)^iC_n^iC_{r-ki-1}^{n-1}.

6 thoughts on “Nguyên lý bù-trừ 2”

  1. Cái cm nguyên lý thiếu bù kia hay vãi, thông báo với cưng Trọc là nó đã bị anh chôm đi nói phét =))

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