September 2011 – T's Lab

Nguyên lý thứ nhất (Quy tắc 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,\ldots,E_k$ .

Ví dụ 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ụ 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ý thứ hai (Quy tắc 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,\ldots,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 $E$ là $n_1\times n_2\times\cdots\times n_k$ .

Ví dụ 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ố $B$ và $C$ . 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 $D.$ $\Box$

Ví dụ 4. Cho $k$ và $n$ 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,\ldots,a_n)$ với $a_1,a_2,\ldots,a_n\in\{0,1,\ldots,k-1\}$ . Hỏi có bao nhiêu dãy này?

Lời giải. Đặt $A=\{0,1,\ldots,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 quy tắc nhân, số các dãy như vậy bằng $k^n.$ $\Box$

Ví dụ 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 5^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 quy tắc 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ụ 6. Cho $X=\{1,2,\ldots,100\}$ và

$S=\{(a,b,c)\mid 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 quy tắc 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ụ 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?

(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$ .

(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 quy tắc 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 quy tắc 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$