Principle of inclusion and exclusion

Bài này là một 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$ .

Để theo dõi bài này cho dễ, các bạn hãy xem qua các bài sau:

[1] https://nttuan.org/2011/09/15/basic-counting-principles/

[2] https://nttuan.org/2012/09/15/permutations/

[3] https://nttuan.org/2013/09/15/combinations/

Chúng ta biết rằng nếu $A$ và $B$ 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 $A$ và $B$ là các tập hữu hạn bất kỳ thì $|A\cup B|=|A|+|B|-|A\cap B|,$ đây chính là nguyên lý bù-trừ cho hai tập hợp. Với $n>1$ tập hợp ta có định lí sau

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

$\displaystyle \left|\bigcup_{i=1}^nA_i\right|=\sum_{1\leq i\leq n}|A_i|-\sum_{1\leq i<j\leq n}|A_i\cap A_j|+\cdots+(-1)^{n+1}\left|\bigcap_{1\leq i\leq n}A_i\right|.$

Chứng minh. Ta sẽ chứng minh rằng mỗi phần tử trong $\displaystyle\bigcup_{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$ ). $\Box$

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 này vì phong cách tổ hợp của nó.

Ví dụ 1. 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}$ và $20^{30}$ ?

Lời giải. Gọi $A$ và $B$ lần lượt là tập các ước dương của $10^{40}$ và $20^{30}$ . Đề bài yêu cầu tính $|A\cup B|$ . Ta có $10^{40}=2^{40}5^{40}, 20^{30}=2^{60}5^{30}$ và $(10^{40},20^{30})=2^{40}5^{30}.$ Suy ra $|A|=(40+1)(40+1)=1681, |B|=(60+1)(30+1)=1891$ và $|A\cap B|=(40+1)(30+1)=1271.$ Bởi thế nên $|A\cup B|=|A|+|B|-|A\cap B|=2301.$ $\Box$

Ví dụ 2. Tìm số các số nguyên dương trong $\{1,2,\ldots,500\}$ chia hết cho $2$ hoặc $3$ hoặc $5.$

Lời giải. Đặt $S=\{1,2,\ldots,500\}$ . Gọi $A,B$ và $C$ lần lượt là tập các phần tử của $S$ chia hết cho $2,3$ và $5$ . Khi đó $A\cup B\cup C$ là tập các số nguyên dương trong $S$ chia hết cho $2$ hoặc $3$ hoặc $5.$ Đề bài yêu cầu tính $|A\cup B\cup C|$ .

Vì $2,3$ và $5$ là các số nguyên dương đôi một nguyên tố cùng nhau nên $A\cap B$ là tập các số nguyên dương trong $S$ chia hết cho $6$ , $B\cap C$ là tập các số nguyên dương trong $S$ chia hết cho $15$ , $C\cap A$ là tập các số nguyên dương trong $S$ chia hết cho $10$ , và $A\cap B\cap C$ là tập các số nguyên dương trong $S$ chia hết cho $30$ . Suy ra $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|$ $\displaystyle=\left[\frac{500}{2}\right]+\left[\frac{500}{3}\right]+\left[\frac{500}{5}\right]-\left[\frac{500}{6}\right]-\left[\frac{500}{15}\right]-\left[\frac{500}{10}\right]+\left[\frac{500}{30}\right]=366.$ $\Box$

Với mỗi số nguyên dương $m$ , ký hiệu $\varphi (m)$ là số các số nguyên dương không vượt quá $m$ và nguyên tố cùng nhau với $m$ . Hàm số $\varphi:\mathbb{N}^*\to\mathbb{N}^*$ được gọi là hàm phi của Euler.

Ví dụ 3. Tính $\varphi (180)$ .

Lời giải. Vì $180=2^23^25$ nên $X$ chính là tập các số trong $S$ không chia hết cho $2,3$ và $5$ . Suy ra $S\setminus X=X_1\cup X_2\cup X_3$ với $X_1$ là tập các số trong $S$ chia hết cho $2$ , $X_2$ là tập các số trong $S$ chia hết cho $3$ , và $X_3$ là tập các số trong $S$ chia hết cho $5.$ Tương tự như bài toán trên ta có

$\displaystyle |X_1\cup X_2\cup X_3|=|X_1|+|X_2|+|X_3|-|X_1\cap X_2|-|X_2\cap X_3|-|X_3\cap X_1|+|X_1\cap X_2\cap X_3|$

$\displaystyle =\left[\frac{180}{2}\right]+\left[\frac{180}{3}\right]+\left[\frac{180}{5}\right]-\left[\frac{180}{6}\right]-\left[\frac{180}{15}\right]-\left[\frac{180}{10}\right]+\left[\frac{180}{30}\right]=132.$ Do đó $\varphi (180)=|X|=|S|-|S\setminus X|=180-132=48.$ $\Box$

Làm tương tự như trên ta có nếu $n$ có phân tích chính tắc $\displaystyle n=\prod p_i^{k_i}$ thì $\displaystyle\varphi (n)=n\prod \left(1-\frac{1}{p_i}\right).$

Ví dụ 4. Tìm số các lời giải nguyên không âm của phương trình $x_1+x_2+x_3=15$ với $x_1\leq 5,x_2\leq 6$ và $x_3\leq 7$ .

Lời giải. Gọi $A$ là tập các nghiệm nguyên không âm của phương trình $x_1+x_2+x_3=15,$ và $B$ là tập các nghiệm nguyên không âm của phương trình thỏa mãn $x_1\leq 5,x_2\leq 6$ và $x_3\leq 7.$ Ta cần tính $\mid B\mid.$ Ta có $A\setminus B=B_1\cup B_2\cup B_3,$ trong đó: $B_1$ là tập các nghiệm nguyên không âm của phương trình thỏa mãn $x_1>5.$ $B_2$ là tập các nghiệm nguyên không âm của phương trình thỏa mãn $x_2>6.$ $B_3$ là tập các nghiệm nguyên không âm của phương trình thỏa mãn $x_3>7.$

Theo nguyên lý bù-trừ, ta có $C^2_{17}-\mid B\mid =\mid A\mid -\mid B\mid =\mid A\setminus B\mid =\sum \mid B_i\mid -\sum \mid B_i\cap B_j\mid+\mid B_1\cap B_2\cap B_3\mid. \quad (*)$

Bộ số tự nhiên $(x_1,x_2,x_3)$ thuộc $B_1$ khi và chỉ khi $(x_1-6)+x_2+x_3=9,$ do đó $\mid B_1\mid =C^2_{11}.$ Hoàn toàn tương tự, ta có $\mid B_2\mid =C^2_{10}$ và $\mid B_3\mid = C_9^2.$

Bộ số tự nhiên $(x_1,x_2,x_3)$ thuộc $B_1\cap B_2$ khi và chỉ khi $(x_1-6)+(x_2-7)+x_3=2,$ do đó $\mid B_1\cap B_2\mid =C^2_{4}.$ Hoàn toàn tương tự, ta có $\mid B_2\cap B_3\mid =1,$ $\mid B_3\cap B_1\mid = C_3^2,$ và $\mid B_1\cap B_2\cap B_3\mid =0.$

Bây giờ thay các kết quả trên vào $(*)$ ta có $\mid B\mid =10.$ $\Box$

Ví dụ 5. 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 8$ và $7\leq x_3\leq 17$ .

Hướng dẫn. Đáp số: $28.$ Đặt $y_1=x_1-3,$ $y_2=x_2,$ và $y_3=x_3-7.$ Ta cần tính số nghiệm tự nhiên của phương trình $y_1+y_2+y_3=18$ thỏa mãn $y_1\leq 6,$ $y_2\leq 8$ và $y_3\leq 10.$ Đến đây làm như ví dụ trên. $\Box$

Ví dụ 6. Với $k=1,2,\ldots,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,\ldots,1992\}.$ Tính $\displaystyle \left|\bigcup_{i=1}^{1992}A_i\right|.$

Hướng dẫn. Chứng minh giao của tất cả các tập chứa đúng một phần tử. Từ đó có đáp số là $85657.\Box$

Cuối cùng là một áp dụng quan trọng của nguyên lý bù-trừ vào bài toán Bernoulli-Euler về các bức thư sai địa chỉ.

Continue reading →

Combinations

Cho một tập $A$ có $n$ phần tử ( $n\in\mathbb{N}$ ) và $0\leq k\leq n$ là một số nguyên. Một $k-$ tổ hợp (một tổ hợp chập $k$ ) của $A$ là một tập con $k$ phần tử của $A$ .

Ví dụ 1. Các $3-$ tổ hợp của $A=\{a,b,c,d\}$ là

$\{a,b,c\},\{b,c,d\},\{c,d,a\},\{d,a,b\}.$

Định lí 1. Cho một tập $A$ có $n$ phần tử ( $n\in\mathbb{N}$ ) và $0\leq k\leq n$ là một số nguyên. Khi đó số $k-$ tổ hợp của $A$ bằng $C_n^k=\dfrac{A_n^k}{k!}=\dfrac{n!}{k!(n-k)!}.$

Chứng minh. Sự khác nhau giữa một $k-$ tổ hợp và một $k-$ hoán vị chính là một đằng không quan tâm đến thứ tự, trong khi đằng kia có quan tâm đến thứ tự. Tận dụng điều này ta có chứng minh như sau.

Một $k-$ hoán vị của $A$ có thể hình thành sau hai bước: Đầu tiên, chọn một $k-$ tổ hợp của $A$ ; sau đó xếp $k$ phần tử của tập này thành một hàng. Bởi vì có $C_n^k$ cách để làm bước một, $k!$ cách để làm bước hai nên theo nguyên lý nhân ta có $A_n^k=C_n^k\times k!.$ $\Box$

Ví dụ 2. Có bao nhiêu xâu nhị phân độ dài $7$ mà có đúng ba số $0$ ?

Lời giải. Một xâu nhị phân có tính chất như trong đề bài sẽ được hình thành khi ta chọn $3$ vị trí trong $7$ vị trí để viết số $0.$ Do đó số xâu thỏa mãn là $C_7^3.$ $\Box$

Ví dụ 3. Có bao nhiêu cách có thể thành lập một hội đồng gồm $5$ thành viên từ một nhóm có $11$ người chứa $4$ giáo viên và $7$ học sinh nếu

(1) Không có thêm điều kiện gì?

(2) Hội đồng chứa đúng $2$ giáo viên?

(3) Hội đồng chứa ít nhất $3$ giáo viên?

(4) Giáo viên $A$ và học sinh $B$ không thể cùng nằm trong hội đồng?

Hướng dẫn giải. (1) $C_{11}^5$ . (2) $C_4^2\times C_7^3$ . (3) $3$ hoặc $4$ giáo viên có thể nằm trong hội đồng, đáp số $91$ .

(4) Dùng quy tắc trừ, đáp số $378$ . $\Box$

Ví dụ 4. Cho $n$ là một số nguyên dương và $A$ là một tập có $2n$ phần tử. Có bao nhiêu cách phân hoạch $A$ thành các tập có $2$ phần tử?

Lời giải 1. Đầu tiên, cố định một phần tử $x$ của $A$ và chọn một phần tử trong $2n-1$ phần tử còn lại của $A$ để ghép lại với $x$ tạo thành một khối của phân hoạch; sau đó cố định một phần tử $y$ trong các phần tử còn lại của $A$ và chọn một phần tử trong $2n-3$ phần tử còn lại của $A$ để ghép lại với $y$ tạo thành một khối của phân hoạch; ta cứ làm như vậy cho đến khi còn $2$ phần tử thì đây chính là khối còn lại của phân hoạch. Theo quy tắc nhân, số phân hoạch thoả mãn là $(2n-1)\times (2n-3)\times\cdots\times 1$ . $\Box$

Lời giải 2. Chọn một tập con có $2$ phần tử của $A$ làm khối thứ nhất, sau đó chọn một tập con có $2$ phần tử của tập hợp gồm $2n-2$ phần tử còn lại làm khối thứ hai, ta cứ làm như vậy cho đến khi còn hai phần tử thì đây chính là khối thứ $n$ . Vì thứ tự các khối là không quan trọng nên số các phân hoạch thoả mãn là $\dfrac{C_{2n}^2\times C_{2n-2}^2\times\cdots\times C_2^2}{n!}$ . $\Box$

Lời giải 3. Ta xếp $2n$ phần tử của $A$ thành một hàng vào $2n$ vị trí như hình dưới đây

$\{(1),(2)\},\{(3),(4)\},\cdots,\{(2n-1),(2n)\}$ có $(2n)!$ cách để làm điều này. Vì trong mỗi tập con có $2$ phần tử thứ tự các phần tử là không quan trọng và thứ tự các khối của phân hoạch là không quan trọng nên số phân hoạch thoả mãn là

$\dfrac{(2n)!}{2!\times 2!\times\cdots\times 2!\times n!}=\dfrac{(2n)!}{n!\times 2^n}.$ $\Box$

Continue reading →

Permutations

Cho $n$ là một số nguyên dương, $r$ là một số nguyên thoả mãn $0\leq r\leq n$ và $A$ là một tập hợp có $n$ phần tử. Một $r-$ hoán vị của $A$ (hay một chỉnh hợp chập $r$ của $A$ ) là một cách xếp $r$ phần tử nào đó của $A$ thành một hàng. Một $n-$ hoán vị của $A$ sẽ được gọi là một hoán vị của $A.$

Ví dụ 1. Cho tập $A=\{a,b,c,d\}$ . Khi đó các $3-$ hoán vị của $A$ là (có tất cả $24$ ):

$abc,acb,bac,bca,cab,cba,$

$abd,adb,bad,bda,dab,dba,$

$acd,adc,cad,cda,dac,dca,$

$bcd,bdc,cbd,cdb,dbc,dcb.$ $\Box$

Định lí 1. Cho $n$ là một số nguyên dương, $r$ là một số nguyên thoả mãn $0\leq r\leq n$ và $A$ là một tập hợp có $n$ phần tử. Khi đó số $r-$ hoán vị của $A$ bằng $A_n^r=\dfrac{n!}{(n-r)!}$ . Nói riêng, số hoán vị của $A$ bằng $P_n=n!$ .

Chứng minh. Một $r-$ hoán vị của $A$ sẽ được hình thành sau $r$ bước: Đầu tiên, chọn một phần tử từ $A$ và đặt nó vào vị trí thứ nhất; sau đó ta chọn trong các phần tử còn lại của $A$ một phần và đặt nó vào vị trí thứ hai;…; và cuối cùng ta chọn một phần tử từ $n-r+1$ phần tử còn lại của $A$ và đặt nó vào vị trí thứ $r$ . Vì có $n$ cách làm bước thứ nhất, $n-1$ cách làm bước thứ hai;…; và $n-r+1$ cách làm bước thứ $r$ nên theo quy tắc nhân, ta có $A_n^r=n(n-1)\cdots (n-r+1)=\dfrac{n!}{(n-r)!}.$ $\Box$

Ví dụ 2. Gọi $E$ là tập tất cả $26$ chữ cái tiếng Anh. Tìm số các từ gồm $5$ chữ trong $E$ sao cho chữ đầu tiên, chữ cuối cùng là các nguyên âm phân biệt và ba chữ còn lại là các phụ âm phân biệt.

Lời giải. Có $5$ nguyên âm trong $E$ đó là $a,e,i,o,u$ và $21$ chữ cái còn lại là các phụ âm. Một từ thỏa mãn yêu cầu của đầu bài sẽ được hình thành sau hai bước: Đầu tiên, chọn một $2-$ hoán vị của $\{a,e,i,o,u\}$ và đặt nguyên âm thứ nhất vào vị trí $1$ , nguyên âm thứ hai vào vị trí $5$ , sau đó chọn một $3-$ hoán vị của $E\setminus \{a,e,i,o,u\}$ và đặt phụ âm thứ nhất, hai, ba của hoán vị vào vị trí $2,3,4$ tương ứng.

Bởi vì có $A_5^2$ cách để làm bước thứ nhất và $A_{21}^3$ cách để làm bước thứ hai nên theo quy tắc nhân ta có số các từ thoả mãn là $A_5^2\times A_{21}^3=159600.$ $\Box$

Continue reading →

A Proof of Karamata’s Inequality

Bất đẳng thức Karamata là một trong những công cụ mạnh mẽ và kinh điển nhất khi xử lý các bài toán Bất đẳng thức Olympic. Trong tài liệu ngắn này, chúng tôi trình bày một chứng minh chi tiết và tự nhiên cho định lý này, sử dụng “Bổ đề làm đều hai số” kết hợp với phương pháp quy nạp toán học dựa trên quan hệ trội.

Karamata Download

The Isoperimetric Inequality for Polygons

Trong tất cả các đa giác $n$ cạnh có cùng chu vi, đa giác nào có diện tích lớn nhất? Đáp án là đa giác đều: nếu đa giác đơn có chu vi $L$ và diện tích $S$ thì $S \le \frac{L^2}{4n\tan(\pi/n)}$ , đẳng thức xảy ra khi và chỉ khi đa giác đều. Bài viết trình bày hai chứng minh: một bằng giải tích Fourier rời rạc, một bằng phương pháp hình học cực trị. Nội dung đầy đủ ở file PDF bên dưới.

isoperime.ineq Download