IMC training 2016 (3)

Methods of Counting (2)

Problem 1. Find the number of pairs (x;y) of integers such that $|x|+|y|\le 1000$.

Problem 2. How many positive integers not exceeding 2001 are multiples of 3 or 4 but not 5?

Problem 3. Let x=.1234567891011…998999, where the digits are obtained by writing the integers 1 through 999 in order. Find the ${{1983}^{rd}}$ digit to the right of the decimal point.

Problem 4. A spider has one sock and one shoe for each of its eight legs. In how many different orders can the spider put on its socks and shoes, assuming that, on each leg, the sock must be put on before the shoe?

Problem 5.  Find the number of sets {a,b,c} of three distinct positive integers with the property that the product of a,b, and c is equal to the product of 11,21,31,41,51, and 61.

Problem 6. Find the number of five-digit positive integers, n, that satisfy the following conditions:

(a) the number n is divisible by 5,

(b) the first and last digits of n are equal, and

(c) the sum of the digits of n is divisible by 5.

Problem 7. Nine people sit down for dinner where there are three choices of meals. Three people order the beef meal, three order the chicken meal, and three order the fish meal. The waiter serves the nine meals in random order. Find the number of ways in which the waiter could serve the meal types to the nine people such that exactly one person receives the type of meal ordered by that person. Continue reading “IMC training 2016 (3)”

IMC training 2016 (2)

Methods of Counting

Problem 1. How many subsets are there in a set of size $10$?

Problem 2. Find the number of squares contained in an $10\times 10$ squares array.

Problem 3. A team is to be chosen from 4 girls and 6 boys. The only requirement is that it must contain at least 2 girls. Find the number of different teams that may be chosen.

Problem 4. You wish to give your Aunt Mollie a basket of fruit. In your refrigerator you have six oranges and nine apples. The only requirement is that there must be at least one piece of fruit in the basket (that is, an empty basket of fruit is not allowed). How many different baskets of fruit are possible?

Problem 5. Find the number of ways 30 identical pencils can be distributed among three girls so that each gets at least 1 pencil.

Problem 6. There 7 boys and 3 girls in a gathering. In how many ways can they be arranged in a row so that

1) the 3 girls form a single block?

2) the two end-possitions are occupied by boys and no girls are adjacent?

Problem 7. Between 20000 and 70000, find the number of even integers in which no digit is repeated. Continue reading “IMC training 2016 (2)”

VMO training 2016 – Part 2

Bài 10. Chứng minh rằng tồn tại $2015$ số nguyên dương liên tiếp sao cho trong chúng có đúng $14$ số nguyên tố.
Bài 11. Với số nguyên dương chẵn $n$ ta đặt các số $1,2,...,n^2$ vào các ô của bàn cờ cỡ $n\times n$ (mỗi số xuất hiện đúng một lần trên bàn). Gọi $S_1$ là tổng các số trên các ô đen và $S_2$ là tổng các số trên các ô trắng. Tìm tất cả $n$ sao cho ta có thể có $\dfrac{S_1}{S_2}=\dfrac{39}{64}.$
Bài 12. Cho số nguyên tố lẻ $p$. Một bộ $(a_1,a_2,a_3,\ldots,a_p)$ các số nguyên được gọi là tốt nếu nó thỏa mãn đồng thời các điều kiện:
(1) $0\le a_i\le p-1$ với mỗi $i$;
(2) $a_1+a_2+a_3+\cdots+a_p$ không chia hết cho $p$;
(3) $a_1a_2+a_2a_3+a_3a_4+\cdots+a_pa_1$ chia hết cho $p$.
Tìm số các bộ tốt.
Bài 13. Cho $A$ là một tập hữu hạn các số thực dương, $B = \{x/y\mid x,y\in A\}$$C = \{xy\mid x,y\in A\}.$ Chứng minh rằng $|A|\cdot|B|\le|C|^2$.
Bài 14. 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.
Bài 15. Tìm số đa thức $f(x)=ax^3+bx$ thỏa mãn cả hai điều kiện:
(i) $a,b\in\{1,2,\ldots,2013\}$;
(ii) $\{f(1),f(2),\ldots,f(2013)\}$ là một hệ thặng dư đầy đủ modulo $2013$. Continue reading “VMO training 2016 – Part 2”

T-Math 3

Đề trước có ở https://nttuan.org/2015/12/10/topic-723/

Bài 1. Cho số nguyên tố lẻ $p$. Một bộ $(a_1,a_2,a_3,\ldots,a_p)$ các số nguyên được gọi là tốt nếu nó thỏa mãn đồng thời các điều kiện:
(1) $0\le a_i\le p-1$ với mỗi $i$;
(2) $a_1+a_2+a_3+\cdots+a_p$ không chia hết cho $p$;
(3) $a_1a_2+a_2a_3+a_3a_4+\cdots+a_pa_1$ chia hết cho $p$.

Tính số bộ tốt.
Bài 2. Cho tam giác $ABC$. Đường tròn nội tiếp của tam giác tiếp xúc với $BC$ tại $A'$. Đoạn $AA'$ cắt lại đường tròn nội tiếp tam giác tại $P$. Các đoạn $BP,CP$ cắt lại đường tròn nội tiếp tại $M,N$ tương ứng. Chứng minh rằng ba đường thẳng $AA',BN,CM$ đồng quy.
Bài 3. Cho các số nguyên dương $a,b,c$$d$. Trên mặt phẳng xét $a+b+c+d$ điểm sao cho không có ba điểm nào trong chúng thẳng hàng. Chứng minh rằng tồn tại hai đường thẳng $l_1, l_2$ sao cho các điều kiện sau được thỏa mãn đồng thời:
(1) $l_1$$l_2$ không song song;
(2) $l_1, l_2$ không đi qua điểm nào trong $a+b+c+d$ điểm đã cho;
(3) Có $a, b, c, d$ điểm trên mỗi miền chia bởi $l_1, l_2$.

Hoán vị tròn

Định nghĩa. Cho $A$ là một tập có $n$ phần tử($n\in\mathbb{N}$) và $1\leq r\leq n$ là một số nguyên. Một $r-$hoán vị tròn của $A$ là một cách xếp $r$ phần tử nào đó của $A$ lên một đường tròn, hai cách xếp được coi là như nhau nếu chúng sai khác nhau một phép quay. Một $n-$hoán vị tròn của $A$ sẽ gọi đơn giản là một hoán vị tròn của $A$.

Số hoán vị tròn. Cho $A$ là một tập có $n$ phần tử($n\in\mathbb{N}$) và $1\leq r\leq n$ là một số nguyên. Khi đó số các $r-$hoán vị tròn của $A$ bằng $Q_n^r=\dfrac{A_n^r}{r}$. Nói riêng, số các hoán vị tròn của $A$ bằng $Q_n^n=(n-1)!$.

Chứng minh. Ta sẽ dùng nguyên lý chia để chứng minh công thức này.

Nguyên lý chia. Nếu tập $A$$n$ phần tử được phân hoạch thành các tập hợp có $k$ phần tử thì số khối của phân hoạch bằng $\dfrac{n}{k}$.

Tập các $r-$hoán vị tuyến tính có thể phân hoạch thành các phần nhỏ sao cho hai hoán vị tuyến tính thuộc cùng một phần nếu chúng xác định cùng một hoán vị tròn. Vì số các hoán vị tuyến tính trong mỗi phần bằng $r$ nên số các hoán vị tròn bằng $Q_n^r=\dfrac{A_n^r}{r}\Box$.

Ví dụ 3.1. Có bao nhiêu cách để $5$ bé trai và $3$ bé gái ngồi quanh một bàn tròn nếu

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

b)Bé trai $T_1$ và bé gái $G_1$ không ngồi cạnh nhau?

c)Không có bé gái nào ngồi cạnh nhau?

Đáp số. a)$Q_8^8$.

b)$6!\times 5$.

c)$4!\times 5\times 4\times 3\Box$.

Ví dụ 3.2. Tìm số cách xếp $n$ cặp vợ chồng ngồi quanh một bàn tròn sao cho

a)Đàn ông và đàn bà ngồi xen kẽ nhau;

b)Mỗi người đàn bà ngồi cạnh chồng của cô ấy.

Hướng dẫn. a)Chọn chỗ cho đàn ông trước sau đó đến đàn bà, đáp số $(n-1)!\times n!$.

b)Coi một cặp là một người, xếp $n$ người này, và sau đó xếp vị trí vợ-chồng, đáp số $(n-1)!\times 2^n\Box$.

Ví dụ 3.3. Người ta định xếp $6$ cậu bé và $5$ cô bé ngồi xung quanh một cái bàn. Tìm số cách xếp nếu

a)Không có thêm điều kiện gì;

b)Không có hai cô bé nào ngồi cạnh nhau;

c)Tất cả các cô bé ngồi liền nhau;

d)Cô bé $G$ ngồi cạnh hai cậu bé $T_1,T_2$.

Đáp số. a)$10!$.

b)$5!\times A_6^5$.

c)$6!\times 5!$.

d)$2\times 8!\Box.$

Ví dụ 3.4. Cho $n,k$ là các số nguyên dương. Chứng minh rằng có $\dfrac{(kn)!}{n^k}$ cách xếp $kn$ người ngồi xung quanh $k$ cái bàn khác nhau sau cho mỗi bàn có $n$ người.

Hướng dẫn. Chọn một $n-$hoán vị tròn xếp vào bàn $1$, sau đó bàn $2$,…$\Box.$

Đếm bằng truy hồi (1)

C1. Cho số nguyên $n>1$. Hãy tìm số các hoán vị $(a_1,a_2,\cdots,a_n)$ của $\{1,2,\cdots,n\}$ sao cho tồn tại duy nhất $i$ để $a_i>a_{i+1}$.

C2. Cho $n>1$ là một số nguyên dương. Tìm số các tập con của $\{1,2,\cdots,n\}$ sao cho trong mỗi tập con có ít nhất hai phần tử là hai số nguyên liên tiếp.

C3. Cho $n>1$ thí sinh ngồi quanh một bàn tròn. Hỏi có bao nhiêu cách phát đề sao cho hai thí sinh ngồi cạnh nhau luôn có đề khác nhau, biết rằng trong ngân hàng đề có đúng $m>1$ đề và mỗi đề có nhiều bản.

C4. Cho một mặt cầu. Một đường tròn lớn của mặt cầu là đường tròn nằm trong một mặt phẳng đi qua tâm của cầu và nằm trên mặt cầu. $5$ đường tròn lớn khác nhau chia mặt cầu thành $n$ phần. Tìm giá trị lớn nhất và bé nhất của $n$.

C5. Một tập hữu hạn các số nguyên dương được gọi là tốt nếu mỗi phần tử của nó ít nhất bằng số phần tử của nó. (Tập rỗng cũng được xem là tốt) Gọi $a_n$ là số tập con tốt của $[n]$ mà không chứa hai số liên tiếp, và $b_n$ là số các tập con của $[n]$ mà hai phần tử bất kì khác nhau ít nhất $3$. Chứng minh rằng $a_n=b_n$ với mỗi $n\geq 0.$

C6. Sử dụng các chữ số $0,1,2,3,4$ ta có thể lập bao nhiêu dãy $10$ chữ số sao cho hay chữ số cạnh nhau vênh nhau $1$?

C7. Gọi $A_n$ là kí hiệu tập các đoạn mã độ dài $n$ hình thành bởi sử dụng các chữ $a,b,c$ sao cho không có các chữ $a$ hay $b$ đứng cạnh nhau. $B_n$ là tập các đoạn mã độ dài $n$ hình thành từ các chữ $a,b,c$ sao cho không có $3$ chữ phân biệt đứng cạnh nhau. Chứng minh rằng $|B_{n+1}|=3|A_n|\forall n\geq 1.$

Tổ hợp

Định nghĩa. Cho một tập $A$$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ụ 4.1. Các $3-$tổ hợp của $A=\{a,b,c,d\}$$\{a,b,c\},\{b,c,d\},\{c,d,a\},\{d,a,b\}\Box.$

Số tổ hợp. Cho một tập $A$$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.

Hoán vị tuyến tính

Định nghĩa. 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$$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ụ 2.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$

Số hoán vị. 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$$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 nguyên lý nhân ta có $A_n^r=n(n-1)\cdots (n-r+1)=\dfrac{n!}{(n-r)!}.$

Ví dụ 2.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$$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-\{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 nguyên lý nhân ta có số các từ thoả mãn là $A_5^2\times A_{21}^3=159600\Box$.

Ví dụ 2.3.$7$ bé trai và $3$ bé gái trong một buổi liên hoan. Có bao nhiêu cách có thể xếp họ thành một hàng sao cho

a)$3$ bé gái đứng cạnh nhau?

b)Hai vị trí đầu và cuối hàng bị chiếm bởi các bé trai và không có hai bé gái nào đứng cạnh nhau?

Lời giải. a)Vì $3$ bé gái đứng cạnh nhau nên ta có thể xem họ là một “bé gái”. Một cách xếp thoả mãn yêu cầu của bài toán sẽ được hình thành sau hai bước: Đầu tiên, xếp $8$ người này thành một hàng, sau đó xếp vị trí cho $3$ bé gái.

Vì có $P_8$ cách thực hiện bước đầu và $P_3$ cách thực hiện bước thứ hai nên theo nguyên lý nhân ta có số các cách xếp thoả mãn là $P_8\times P_3\Box.$

b)Theo đầu bài, vị trí của các bé trai và các bé gái chỉ có thể như sau

$1\,\,\,2\,\,\,3\,\,\,4\,\,\,5\,\,\,6\,\,\,7\,\,\,8\,\,\,9\,\,\,10\,\,\,11\,\,\,12\,\,\,13.$

Với vị trí của các bé trai là $1,3,5,7,9,11,13$ và các vị trí của các bé gái là $2,4,6,8,10,12$. Theo nguyên lý nhân, số cách xếp thoả mãn là $P_7\times A_6^3\Box.$

Ví dụ 2.4. Tìm số các số nguyên chẵn nằm giữa $20000$$70000$ sao cho các chữ số của chúng đôi một khác nhau.

Lời giải. Gọi $\overline{abcde}$ là một số thoả mãn. Ta thấy $a\in\{2,3,4,5,6\}$$e\in\{0,2,4,6,8\}$.

i)Nếu $a\in\{2,4,6\}$.

Một số thoả mãn sẽ được hình thành sau ba bước: Đầu tiên chọn $a$ từ tập $\{2,4,6\}$; sau đó chọn $e$ từ tập $\{0,2,4,6,8\}-\{a\}$; cuối cùng chọn một $3-$hoán vị của tập $\{0,1,2,3,4,5,6,7,8,9\}-\{a,e\}$ và cho $b$ bằng số thứ nhất, $c$ bằng số thứ hai, và $d$ bằng số thứ ba của hoán vị.

Bởi vì có $3$ cách để làm bước thứ nhất, $4$ cách để làm bước thứ hai, và $A_8^3$ cách để làm bước thứ ba nên theo nguyên lý nhân ta có số các số thoả mãn trong trường hợp này là $3\times 4\times A_8^3$.

ii)Nếu $a\in\{3,5\}$. Tương tự ta có số các số thoả mãn trong trường hợp này là $2\times 5\times A_8^3$.

Theo nguyên lý cộng, số các số thoả mãn là $7392.\Box$

Ví dụ 2.5. Gọi $S$ là tập các số nguyên có các chữ số lấy từ $\{1,3,5,7\}$ và các chữ số của chúng đôi một khác nhau. Tính

a)$|S|$;

b)$\sum_{n\in S}n$.

Lời giải. a)Gọi $S_i\subset S$ với $i=1,2,3,4$ là tập các số trong $S$$i$ chữ số, dễ thấy $|S|=|S_1|+|S_2|+|S_3|+|S_4|=A_4^1+A_4^2+A_4^3+A_4^4=4+12+24+24=64.$

b)Gọi $n_1,n_2,n_3,n_4$ tương ứng là tổng các chữ số hàng đơn vị, hàng chục, hàng trăm, hàng nghìn của các số trong $S$. Khi đó tổng cần tính bằng

$n_1+10n_2+100n_3+1000n_4.$

i)Tính $n_1$.

Tổng các chữ số hàng đơn vị của các số trong $S_1$ bằng $1+3+5+7=16$. Đê tính tổng các chữ số hàng đơn vị của các số trong $S_2$, ta cần tìm xem có bao nhiêu số trong $S_2$ có chữ số hàng đơn vị bằng $1,3,5,7$ tương ứng? Suy ra tổng các chữ số hàng đơn vị của các số trong $S_2$ bằng $A_3^1\times (1+3+5+7)=3\times 16=48$. Tương tự, tổng các chữ số hàng đơn vị của các số trong $S_3$ bằng $96$, và trong $S_4$ bằng $96$. Suy ra $n_1=256$.

ii)Tính $n_2$.

Tương tự $n_2=240$.

iii)Tính $n_3$.

Tương tự $n_3=192$.

iv)Tính $n_4$.

Tương tự $n_4=96$.

Vậy tổng cần tính bằng $117856\Box$.

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

Bài 2.1. Có bao nhiêu cách xếp $26$ chữ cái trong bảng chữ cái tiếng Anh thành một hàng nếu các nguyên âm không đứng cạnh nhau?

Hướng dẫn. Làm như Ví dụ 2.3, đáp số của bài toán là $P_{21}\times A_{22}^5\Box$.

Bài 2.2. Có bao nhiêu số nguyên dương có $7$ chữ số sao cho các chữ số đôi một khác nhau thuộc tập $\{1,2,3,4,5,6,7,8,9\}$ và các chữ số $5,6$ không đứng cạnh nhau?

Hướng dẫn. Chia các số cần đếm thành $4$ loại

Loại 1:Không có $5$$6$ trong biểu diễn thập phân. Loại này có $P_7$ số.

Loại 2:Có $5$ nhưng không có $6$ trong biểu diễn thập phân. Loại này có $7\times A_7^6.$

Loại 3:Có $6$ nhưng không có $5$ trong biểu diễn thập phân. Loại này có $7\times A_7^6.$

Loại 4:Có cả $5$$6$ trong biểu diễn thập phân. Ta lại chia các số loại này thành $3$ loại:

i)$5$ xuất hiện ở đầu. Loại này có $5\times A_7^5$ số.

ii)$5$ xuất hiện ở cuối. Loại này cũng có $5\times A_7^5$ số.

iii)$5$ không xuất hiện ở đầu cũng không xuất hiện ở cuối. Loại này có $5\times 4\times A_7^5$.

Như vậy số các số thoả mãn là $151200\Box.$

Ta có thể làm cách khác bằng cách dùng nguyên lý sau:

Nguyên lý trừ. Nếu $A\subset B$ là các tập hữu hạn thì $|B-A|=|B|-|A|$.

Muốn dùng nguyên lý này vào giải bài toán trên, ta gọi $B$ là tập các số có $7$ chữ số khác nhau lấy từ $\{1,2,3,4,5,6,7,8,9\}$$A$ là tập các số trong $B$ mà trong biểu diễn thập phân có $5$$6$ đứng cạnh nhau. Dễ thấy $|B|=A_9^7$$|A|=2\times 6\times A_7^5\Box$.

Bài 2.3. Có bao nhiêu từ gồm $5$ chữ cái lấy trong các chữ cái $A,B,C,D,E,F, G,H,I,J$ nếu

a)Các chữ cái trong các từ đôi một khác nhau?

b)Nếu các chữ cái trong các từ đôi một khác nhau và $A,B,C,D,E,F$ chỉ có thể ở các vị trí thứ nhất, ba và năm; trong khi các chữ còn lại chỉ có thể ở các vị trí thứ hai và thứ tư?

Đáp số. a)$A_{10}^5$;

b)$A_6^3\times A_4^2\Box.$

Bài 2.4. Có bao nhiêu cách xếp $26$ chữ cái trong bảng chữ cái tiếng Anh thành một hàng nếu có đúng $5$ chữ cái giữa $X$$Y$?

Đáp số. $2\times A_{24}^5\times P_{20}\Box.$

Bài 2.5. Có bao nhiêu số nguyên lẻ giữa $3000$$8000$ nếu các chữ số của nó đôi một khác nhau?

Đáp số. $1232\Box$.

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 $E$$n_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ố $B$$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 $B\Box$.

Ví dụ 1.4. Cho $k$$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,\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

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 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|ak\}$ 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 $a$$b$ 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 $a$$b$ 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=\emptyset$$A\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 C$$C\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$.