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)”

Olympic sinh viên và học sinh 2016-Đề thi dành cho sinh viên


Đề hay hơn hồi mình thi nhiều quá. Continue reading “Olympic sinh viên và học sinh 2016-Đề thi dành cho sinh viên”

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,cd. 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_1l_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 .

Continue reading “T-Math 3”

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 An 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.

Continue reading “Đếm bằng truy hồi (1)”

Tổ hợp


Định nghĩa. Cho một tập An 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 An 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.

Continue reading “Tổ hợp”

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 nA 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 nA 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,u21 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 2000070000 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 Si 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ó 56 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ả 56 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ó 56 đứ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 XY?

Đá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 30008000 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 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.