Hai nguyên lý đếm cơ bản


Nguyên lý cộng. Giả sử có n_1 cách thực hiện việc E_1, n_2 cách thực hiện việc E_2,…,n_k cách thực hiện việc E_k. Nếu k việc này không thể làm đồng thời thì sẽ có n_1+n_2+\cdots+n_k cách thực hiện một trong các việc E_1,E_2,\cdots,E_k.

Theo ngôn ngữ của lý thuyết tập hợp, nguyên lý này có thể phát biểu như sau: Nếu A_1,A_2,\cdots,A_k là các tập hữu hạn và đôi một rời nhau thì |\cup_{i=1}^kA_i|=\sum_{i=1}^k|A_i|.

Ví dụ 1.1. Người ta có thể đi từ Hải Phòng đến Đà Nẵng bằng một trong ba phương tiện: tàu hoả, tàu thuỷ và máy bay. Nếu có hai cách đi bằng tàu hoả, ba cách đi bằng tàu thuỷ, và 1 cách đi bằng máy bay thì sẽ có 2+3+1=6 cách đi từ Hải Phòng đến Đà Nẵng \Box.

Ví dụ 1.2. Tìm số các cặp có thứ tự (x;y) các số nguyên thoả mãn x^2+y^2\leq 5.

Lời giải. Mỗi i=0,1,2,3,4,5 ta đặt S_i=\{(x,y)|x,y\in\mathbb{Z},x^2+y^2=i\}, khi đó tập cần tính số phần tử sẽ là hợp rời rạc của các S_i. Ta tính số phần tử của các S_i bằng phương pháp liệt kê và cuối cùng được đáp số của bài toán là 21\Box.

Nguyên lý nhân. Giả sử rằng việc E có thể được làm bằng cách thực hiện liên tiếp các việc E_1,E_2,\cdots,E_k; và có n_1 cách thực hiện việc E_1, n_2 cách thực hiện việc E_2,…,n_k cách thực hiện việc E_k. Khi đó số cách làm việc En_1\times n_2\times\cdots\times n_k.

Theo ngôn ngữ của lý thuyết tập hợp, nguyên lý này có thể phát biểu như sau: Nếu A_1,A_2,\cdots,A_k là các tập hữu hạn thì |\prod_{i=1}^kA_i|=\prod_{i=1}^k|A_i|.

Ví dụ 1.3. Đề đi từ thành phố A đến thành phố D người ta phải đi lần lượt qua hai thành phố BC. Nếu có hai cách đi từ A đến B, ba cách đi từ B đến C và một cách đi từ C đến D thì sẽ có 2\times 3\times 1=6 cách đi từ A đến B\Box.

Ví dụ 1.4. Cho kn là các số nguyên dương. Một dãy k-phân độ dài n là một dãy (a_1,a_2,\cdots,a_n) với a_1,a_2,\cdots,a_n\in\{0,1,\cdots,k-1\}. Hỏi có bao nhiêu dãy này?

Lời giải. Đặt A=\{0,1,\cdots,k-1\}. Để hình thành một dãy k-phân, đầu tiên chúng ta cần chọn a_1 từ B, sau đó chọn a_2 từ B, và cứ như thế cho đến cuối cùng cần chọn a_n từ B. Bởi vì có k cách để làm mỗi bước nên theo nguyên lý nhân, số các dãy như vậy bằng k^n\Box.

Ví dụ 1.5. Tìm số các ước dương của 600.

Lời giải. Ta có 600=2^3\times 3^1\times 5^2 nên một số nguyên dương m là một ước dương của 600 khi và chỉ khi nó có dạng m=2^a\times 3^b\times 3^c với a,b,c là các số nguyên thoả mãn 0\leq a\leq 3,0\leq b\leq 1,0\leq c\leq 2. Như vậy số các ước dương của 600 bằng số các bộ ba (a,b,c) thoả mãn a\in\{0,1,2,3\},b\in\{0,1\},c\in\{0,1,2\}, theo nguyên lý nhân, số ước dương của 600 bằng 4\times 2\times 3=24\Box.

Tổng quát hơn ta có: Nếu số nguyên dương n có phân tích tiêu chuẩn n=\prod p_i^{k_i} thì số các ước dương của n bằng \prod (k_i+1).

Ví dụ 1.6. Cho X=\{1,2,\cdots,100\}S=\{(a,b,c)|a,b,c\in X,a<b,a<c\}.

Tính |S|.

Lời giải. Với mỗi k=1,2,\cdots,99 ta đặt S_k=\{(k,b,c)|b,c\in X, b>k,c>k\}. Khi đó S là hợp rời rạc của các S_k, mà theo nguyên lý nhân ta có |S_k|=(100-k)^2 nên suy ra |S|=\sum S_k=328350\Box.

Để ý đến lời giải ví dụ thứ hai và thứ sáu, ta thấy chúng có một điểm chung là chia bài toán đã cho thành các bài toán con đơn giản hơn và giải chúng. Đây là cách cơ bản nhất để giải các bài toán đếm, có thể sẽ có cách khác ngắn gọn hơn, nhưng việc chia một bài toán thành các bài toán con mà chúng ta đã biết cách giải sẽ giúp ta ít gặp phải các sai lầm hơn.

Ví dụ 1.7. Có bao nhiêu số tự nhiên có ba chữ số được lấy từ tập \{1,2,3,4,5,6\} nếu

a)Các chữ số không cần phải khác nhau?

b)Các chữ số phải khác nhau?

c)Các chữ số phải khác nhau và chứa số 3?

d)Các chữ số không cần phải khác nhau và chứa số 3?

Lời giải. a)6^3, b)6\times 5\times 4.

c)Đầu tiên ta chọn vị trí cho số 3, sau đó chọn hai số còn lại lần lượt. Đáp số là 3\times 5\times 4.

d)Nếu tiếp tục làm như trên ta sẽ được kết quả là 3\times 6\times 6, đây là một kết quả không chính xác! Vì làm như vậy những số như 323 sẽ được đếm hai lần. Vấn đề ở chỗ ta đã dùng sai nguyên lý nhân, mỗi hai tổ hợp khác nhau cách thực hiện các công việc E_i phải cho hai kết quả khác nhau thì ta mới áp dụng được nguyên lý nhân. Bài này ta lại phải chia thành các bài toán con và giải chúng lần lượt.

Ta chia trường hợp theo vị trí của số 3 nằm bên trái nhất. Nếu số 3 này nằm ở vị trí hàng trăm thì số có ba chữ số phải có dạng \overline{3ab}, nếu nó nàm ở vị trí hàng chục thì số có ba chữ số phải có dạng \overline{a3b} với a\not=3, và cuối cùng, nếu số 3 này nằm ở vị trí hàng đơn vị thì số ba chữ số phải có dạng \overline{ab3} với a,b\not=3. Giải các bài toán con ta được đáp số của bài toán là 6\times 6+5\times 6+5\times 5\Box.

Như vậy nếu chia được bài toán cần giải về các bài toán đếm đã biết cách giải thì mọi việc còn lại là đơn giản. Không may, trong đa số các bài toán đếm việc tìm ra một cấu trúc để chia bài toán thành các bài toán nhỏ hơn là việc làm khó khăn nhất. Hay nói khác đi, khó khăn nằm ở lúc bắt đầu. Sau khi chọn được cấu trúc rồi, bạn phải kiểm chia xem việc chia như vậy có đảm bảo đầu ra là các mô hình khác nhau hay không.

Hầu hết các bài toán đếm đều yêu cầu bạn phải thực sự hiểu mô hình mà mình cần đếm, hay cái mà bạn cần đếm. Biết lời giải một bài toán đếm sẽ giúp ích bạn một chút khi giải bài toán đếm khác, nhưng muốn thực sự giỏi thì bạn phải làm nhiều bài tập, việc đọc các ví dụ là không bao giờ đủ!

Ví dụ 1.8. Một rổ bóng chứa 5 quả bóng xanh giống nhau và 8 quả bóng đỏ giống nhau. Hỏi có bao nhiêu cách bốc ít nhất 1 quả bóng ra khỏi rổ?

Lời giải. Rõ ràng là có thể giải bài toán bằng cách chia thành các trường hợp: Bốc 1, bốc 2,…,bốc 13 quả bóng. Nhưng như thế hơi dài. Ở trên chia theo số bóng bốc ra, rõ ràng là số bóng khác nhau thì ta có hai lần bốc khác nhau. Liệu còn có cách khác phân biệt hai lần bốc? Ta thấy hai lần bốc cho hai kết quả giống nhau nếu và chỉ nếu số bóng xanh và số bóng đỏ như nhau, vậy hai lần bốc khác nhau nếu và chỉ nếu số bóng xanh hoặc số bóng đỏ khác nhau. Như vậy ta có lời giải sau.

Số cách bốc bằng số cặp (a,b) trừ đi 1, ở đây 0\leq a\leq 5 là số quả bóng xanh và 0\leq b\leq 8 là số quả bóng đỏ. Như vậy ta có đáp số của bài toán là 6\times 9-1=53\Box.

Sau đây là một số bài tập tự luyện.

Bài 1.1. Cho bảng ô vuông 10\times 10. Hỏi có bao nhiêu hình vuông có các đỉnh nằm ở tâm của các ô vuông của bảng vuông này?

Lời giải. Chia các hình vuông làm hai loại, loại có các cạnh song song với cạnh của bảng và loại có các cạnh không song song với các cạnh của bảng. Mỗi hình vuông ở loại thứ hai sẽ nội tiếp trong một hình vuông của loại thứ nhất, và mỗi hình vuông ở loại thứ nhất có cạnh k sẽ ngoại tiếp đúng k-1 hình vuông ở loại thứ hai. Như thế ta chỉ cần đếm số các hình vuông thuộc loại thứ nhất, dễ thấy với mỗi k, số hình vuông cạnh k thuộc loại thứ nhất bằng (10-k)^2. Do đó đáp số của bài toán là \sum_{k=1}^9(10-k)^2k=825\Box.

Bài 1.2. Cho số nguyên dương n. Hỏi có bao nhiêu tam giác có độ dài các cạnh là các số khác nhau trong tập [n]=\{1,2,\cdots,n\}?

Lời giải. Ba số dương a<b<c là độ dài ba cạnh của một tam giác khi và chỉ khi a+b>c. Như vậy số các tam giác trong đầu bài bằng giá trị của tổng |A_1|+|A_2|+\cdots+|A_n|, ở đây A_k=\{(a,b,k)\in [n]^3|a<b<k,a+b>k\} với k=1,2,\cdots,n. Do đó bài toán sẽ được giải nếu ta tính được |A_k| với mỗi k. Không khó khăn ta thấy |A_1|=|A_2|=|A_3|=0. Bây giờ ta sẽ tính |A_k| với k\geq 4.

a)Nếu k chẵn, k=2m với m>1 là số nguyên dương. Trong trường hợp này ta có |A_k|=(m-1)^2.

b)Nếu k lẻ, k=2m+1 với m>1 là số nguyên dương. Trong trường hợp này ta có |A_k|=m(m-1).

Như vậy đáp số của bài toán là \dfrac{p(p-1)(4p+1)}{6} nếu n=2p+1, \dfrac{p(p-1)(4p-5)}{6} nếu n=2p\Box.

Bài 1.3. Xác định số cặp có thứ tự các số nguyên dương (a,b) sao cho bội chung nhỏ nhất của ab bằng 2^35^711^{13}.

Lời giải.a,b là các ước của 2^35^711^{13} nên ta có thể viết a=2^x5^y11^z,b=2^s5^t11^u, từ đây ta phải có \max\{x,s\}=3,\max\{y,t\}=7,\max\{z,u\}=13. Bằng phương pháp liệt kê ta sẽ đếm được số các cặp (x,s),(y,t),(z,u) và đáp số của bài toán là 7\times 15\times 27\Box.

Tổng quát hơn ta có nếu n=\prod p_i^{a_i} thì số các cặp có thứ tự các số nguyên dương (a;b) sao cho bội chung nhỏ nhất của ab bằng n bằng \prod (2a_i+1).

Bài 1.4. Tìm số các số nguyên dương bé hơn 1000 mà trong biểu diễn thập phân của chúng có chứa ít nhất một chữ số 1.

Hướng dẫn. Ta đếm phần bù, đáp số của bài toán là 271\Box.

Bài 1.5. Tìm số các ánh xạ f:\{1,2,\cdots,2008\}\to\{2009,2010,2011,2012\} thoả mãn f(1)+f(2)+\cdots+f(2008) là số chẵn.

Đáp số. 4^{2007}\Box.

Bài 1.6. Có bao nhiêu tập con có ba phần tử của tập \{2^1,2^2,\cdots,2^{2010}\} sao cho ba phần tử đó có thể xếp thành một cấp số nhân tăng?

Hướng dẫn. Ta cần đếm số các cấp số cộng tăng gồm ba số hạng trong tập \{1,2,\cdots,2010\}. Để làm điều này ta hãy chọn phần tử ở giữa của cấp số cộng đó \Box.

Bài 1.7. Tìm số bộ ba có thứ tự các tập (A,B,C) sao cho A\cap B\cap C=\emptysetA\cup B\cup C=\{1,2,\cdots,2010\}.

Lời giải. Mỗi một số 1,2,\cdots,2010 chỉ có thể nằm trong một trong sáu tập A,B,C,A\cap B,B\cap CC\cap A. Như vậy đáp số của bài toán là 6^{2010}\Box.

Bài 1.8. Tìm số các tập con của một tập có n phần tử, ở đây n là một số nguyên dương.

Hướng dẫn. Mỗi một phần tử của tập nói đến trong đầu bài, nó có thể thuộc hay không thuộc vào tập con. Như vậy ta có đáp số của bài toán là 2^n\Box.

12 thoughts on “Hai nguyên lý đếm cơ bản”

  1. tại sao kết thúc mỗi lời giải em đều thấy có 1 ô vuông hả thầy? Và IMO shortlish là gì ạ?

  2. Những lời giải trên của thầy đã thật đầy đủ chưa ạ? Hay nó chỉ là định hướng cho lời giải ạ?

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