Giáo trình Toàn rời rạc 1 - Bài tập chương 6: Phép đếm

Trường Đại Học Bách Khoa Tp.Hồ Chí Minh

Khoa Khoa Học và Kỹ Thuật Máy Tính

Bài tập chương 6

Phép đếm

1 Dẫn nhập

Trong bài tập dưới đây, chúng ta sẽ làm quen với các kiến thức liên quan đến các phép

đếm (bao gồm lượng số, tổ hợp, chỉnh hợp, và các nguyên lý đếm). Sinh viên cần ôn lại lý

thuyết của chương 3 trước khi làm bài tập bên dưới.

2 Bài tập mẫu

Câu 1.

Giả sử bộ môn Khoa học máy tính có tổng cộng 10 môn học chuyên ngành.Trong bộ môn

có 12 giảng viên (6 kĩ sư, 4 tiến sĩ và 2 giáo sư). Biết rằng mỗi môn học sẽ do một tiến sĩ

hoặc một giáo sư đảm nhiệm. Mỗi môn học cũng có một trợ giảng là kĩ sư. Cho biết:

a) Tổng số kết hợp có thể có của các môn học và các giảng viên trong bộ môn. Cho trước

kết hợp là bộ 3: Môn học + Giảng viên lý thuyết + trợ giảng

b) Nếu số lượng môn học và giảng viên giảm đi một nửa. Tổng số kết hợp có thể có là bao

nhiêu?

c) Giả sử số lượng môn học và giảng viên như câu b, khoa tuyển thêm một thạc sĩ toán

học chuyên giảng dạy Toán rời rạc. Tổng số kết hợp có thể có là bao nhiêu?

Lời giải.

a) Kết hợp của các bộ 3 là tích Đề Các A × B × C với A là tập tất cả môn học, B là tập

các tiến sĩ và giáo sư, C là tập các kĩ sư. Tổng số kết hợp sẽ là 10 × 6

b) 5 × 3 × 3

c) Số lượng tăng thêm 1 × 1 × 6

2

Câu 2.

Nhà nhiếp ảnh có bao nhiêu cách sắp xếp một hàng 6 người từ một nhóm gồm 10 người

trong một lễ cưới, nếu chú rể và cô dâu cũng nằm trong số 10 người đó, nếu

Giáo trình Toán Rời Rạc 1

Trang 1/8

Trường Đại Học Bách Khoa Tp.Hồ Chí Minh

Khoa Khoa Học và Kỹ Thuật Máy Tính

1. cô dâu phải có mặt trong bức ảnh?

2. cả cô dâu và chú rể phải có mặt trong bức ảnh?

3. phải có chính xác một người, hoặc cô dâu, hoặc chú rể có mặt trong bức ảnh?

Lời giải.

1. Bài toán được chia làm 2 giai đoạn: chọn vị trí cho cô dâu trước, sau đó chọn vị trí

cho 5 người còn lại.

• Chọn vị trí cho cô dâu: 6 cách chọn

• Chọn vị trí cho 5 người còn lại: chọn và hoán vị 5 người trong 9 người còn lại,

9!

P(9, 5) =

4!

9!

Vậy số cách sắp xếp: 6.

4!

2. Bài toán chia làm 2 giai đoạn: chọn vị trí cho cô dâu và chú rể, sau đó chọn vị trí

cho 4 người còn lại.

6!

4!

• Chọn vị trí cho cô dâu và chú rể: chọn và hoán vị 2 trong 6 vị trí: P(6, 2) =

• Chọn vị trí cho 4 người còn lại: chọn và hoán vị 4 người trong 8 người còn lại,

8!

P(8, 4) =

4!

6! 8!

4! 4!

Vậy số cách sắp xếp:

.

3. Có 2 cách làm: 1) chọn vị trí cho chú rể, sau đó chọn 5 vị trí còn lại cho 8 người (trừ

cô dâu), sau đó nhân 2 để có thêm trường hợp chỉ chọn cô dâu, hoặc 2) lấy kết quả

của câu a nhân với 2 để có trường hợp có mặt cô dâu hoặc chú rể, sau đó trừ đi 2

lần câu b để loại ra trường hợp có mặt cả cô dâu và chú rể, mà ta đã đếm 2 lần cho

câu a, một khi có mặt cô dâu, và một khi có mặt chú rể.

Đáp số: 2.P(6, 1).P(8, 5) = 2.6.P(9, 5) − 2.P(6, 2).P(8, 4)

2

3 Bài tập cần giải

Câu 3.

Nhà nhiếp ảnh có bao nhiêu cách sắp xếp một hàng 6 người trong một lễ cưới, trong đó

có cô dâu và chú rể, nếu

1. cô dâu phải đứng kế chú rể?

Giáo trình Toán Rời Rạc 1

Trang 2/8

Trường Đại Học Bách Khoa Tp.Hồ Chí Minh

Khoa Khoa Học và Kỹ Thuật Máy Tính

2. cô dâu không đứng kế chú rể?

3. cô dâu đứng ở đâu đó phía bên trái chú rể?

Lời giải.

1. Vì cô dâu và chú rể luôn đứng kế nhau, nên ta ghép hai người thành 1 vị trí, bài toán

trở thành hoán vị một hàng gồm có 5 người: P(5). Ngoài ra, cô dâu có thể đứng bên

trái hoặc bên phải chú rể, nên kết quả là 2.P(5).

2. Cô dâu không đứng kế chú rể sẽ là toàn bộ các trường hợp sắp xếp trừ ra các trường

hợp đã tính trong câu a, tức là, P(6) − 2.P(5)

3. Trong trường hợp này ta phải xét từng vị trí đứng cụ thể của chú rể trong hàng. Giả

sử đánh số vị trí đứng từ 1 đến 6 từ trái sang.

• Chú rể đứng ngoài cùng bên trái (vị trí 1), cô dâu không có chỗ đứng: 0

• Chú rể đứng vị trí 2, cô dâu có 1 chỗ đứng, 4 người còn lại hoán vị qua lại:

1.P(4)

• Chú rể đứng vị trí 3, cô dâu có 2 chỗ đứng (ở vị trí 1 và 2), 4 người còn lại hoán

vị qua lại: 2.P(4)

• ....

Kết quả sẽ là: P(4) + 2.P(4) + 3.P(4) + 4.P(4) + 5.P(4)

2

Câu 4.

Có bao nhiêu chuỗi bit có chiều dài là 10 có hoặc năm số 0 liên tiếp hoặc 5 số 1 liên tiếp?

Lời giải.

Gọi A là tập chuỗi bit có chiều dài là 10 có 5 số 0 liên tiếp.

Với i từ 1 đến 6, A_ilà tập các chuỗi bit có chiều dài 10 trong đó năm số 0 xuất phát tại vị

trí i. Khi đó A₁, A₂, A₃, A₄, A₅và A₆đôi một rời nhau và A = A₁∪A₂∪A₃∪A₄∪A₅∪A₆.

Theo luật cộng, ta có

|A| = |A₁| + |A₂| + |A₃| + |A₄| + |A₅| + |A₆|.

Với chuỗi bit trong A₁, năm chữ số đầu tiên là 0 và 5 chữ số sau có thể là 0 hoặc 1. Do đó

|A₁| = 1 × 1 × 1 × 1 × 1 × 2 × 2 × 2 × 2 × 2 = 32.

Với chuỗi bit trong A₂, chữ số đầu là 1, năm chữ số tiếp là 0 và 4 chữ số tiếp theo sẽ là 0

hoặc 1. Do đó

|A₂| = 1 × 1 × 1 × 1 × 1 × 1 × 2 × 2 × 2 × 2 = 16.

Với chuỗi bit trong A₃, chữ số đầu là 1 hoặc 0, chữ số thứ 2 là 1, năm chữ số tiếp theo là

0 và ba chữ số cuối là 0 hoặc 1. Do đó

|A₃| = 2 × 1 × 1 × 1 × 1 × 1 × 1 × 2 × 2 × 2 = 16.

Giáo trình Toán Rời Rạc 1

Trang 3/8

Trường Đại Học Bách Khoa Tp.Hồ Chí Minh

Khoa Khoa Học và Kỹ Thuật Máy Tính

Tương tự,

|A₄| = |A₅| = |A₆| = 16.

Do đó,

|A| = 32 + 16 + 16 + 16 + 16 + 16 = 112.

Gọi B là tập chuỗi bit có chiều dài 10 có chứa dãy 5 số 1 liên tiếp. Tương tự như A, ta có

|B| = 32 + 16 + 16 + 16 + 16 + 16 = 112.

Hơn nữa,

A ∩ B = {0000011111, 1111100000}.

Theo nguyên lý inclusion-exclusion, số chuỗi bit có chiều dài là 10 có chứa hoặc 5 số 0 liên

tiếp hoặc 5 số 1 liên tiếp là

|A ∪ B| = |A| + |B| − |A ∩ B| = 112 + 112 − 2 = 222.

2

Câu 5.

Giả sử mật khẩu của một hệ thống máy tính phải có tối thiểu 8 ký tự, nhưng không được

quá 12 ký tự, trong đó mỗi ký tự phải là chữ tiếng Anh ở dạng chữ thường hoặc chữ hoa,

chữ số, hoặc một trong sáu ký tự đặc biệt *, >, <, !, +, và =.

1. Có tất cả bao nhiêu mật khẩu khác nhau mà hệ thống này chấp nhận?

2. Có bao nhiêu mật khẩu trong số mật khẩu này có chứa ít nhất một lần xuất hiện

của ít nhất một trong sáu ký tự đặc biệt?

3. Nếu một hacker cần một nano-giây để kiểm tra từng mật khẩu một có phải mật khẩu

của ta hay không, hacker phải mất bao nhiêu lâu để dò qua hết tất cả các mật khẩu?

Lời giải.

1.

• Xét trường hợp mật khẩu có 8 ký tự, mỗi ký tự chấp nhận bộ ký tự gồm 26 chữ

tiếng Anh thường, 26 chữ tiếng Anh hoa, 10 chữ số, 6 ký tự đặc biệt, tổng cộng

là 68 khả năng. Theo nguyên tắc nhân, 8 ký tự sẽ có 68 × 68 × 68 × 68 × 68 ×

68 × 68 × 68 = 68⁸.

• Tương tự với các trường hợp có 9, 10, 11, 12 ký tự.

Theo nguyên tắc cộng, tổng số mật khẩu khác nhau là 68⁸+68⁹+68¹⁰+68¹¹+68¹².

2. Thay vì tìm số lượng mật khẩu cho từng trường hợp rồi cộng lại với nhau, ta sẽ tìm

số lượng mật khẩu không xuất hiện bất kỳ ký tự nào trong 6 ký tự đặc biệt, rồi trừ

nó ra khỏi tổng số khả năng để tìm thấy đáp số.

Kết quả sẽ là: 68⁸+ 68⁹+ 68¹⁰+ 68¹¹+ 68¹²− (62⁸+ 62⁹+ 62¹⁰+ 62¹¹+ 62¹²)

3. Sinh viên tự giải quyết.

2

Giáo trình Toán Rời Rạc 1

Trang 4/8

Trường Đại Học Bách Khoa Tp.Hồ Chí Minh

Khoa Khoa Học và Kỹ Thuật Máy Tính

Câu 6.

Một mạng máy tính gồm 6 máy tính. Mỗi máy sẽ nối trực tiếp với 0 hoặc nhiều máy tính

khác. Chứng minh rằng sẽ có ít nhất là hai máy tính trong mạng được kết nối trực tiếp

đến cùng số máy tính khác.

Lời giải.

Nhận xét rằng trên thực tế, không phải một máy tính có thể có 0, 1, 2, . . . , 5 kết nối

đến máy tính trong máy (tức là 6 khả năng), mà chỉ có tổng cộng 5 khả năng mà thôi, vì

việc kết nối đến 0 máy tính và 5 máy tính không thể đồng thời cùng xảy ra. Nói một cách

nôm na, nếu một máy trong mạng có 0 kết nối, thì không có máy nào trong các máy còn

lại có 5 kết nối, tức là có 0 thì không có 5. Hơn nữa, nếu một máy trong mạng có 5 kết

nối, thì không có máy nào trong các máy còn lại có 0 kết nối, tức là có 5 thì không có 0.

Vậy một máy tính trong mạng chỉ có 5 khả năng kết nối, tạo thành 5 chuồng, mỗi chuồng

tương ứng với số kết nối khác nhau. 6 máy tính tương ứng với 6 chim bồ câu. Phân bổ 6

chim vào 5 chuồng thì chắc chắn sẽ có ít nhất 1 chuồng có từ 2 chim trở lên, tức là sẽ có

ít nhất 2 máy có cùng số kết nối đến máy khác.

2

Câu 7.

Chứng minh rằng trong bất kỳ n + 1 số nguyên dương không lớn hơn 2n, chắc chắn phải

có một số nguyên chia hết cho một trong các số nguyên còn lại.

Lời giải.

Ta sử dụng định lý: Mọi số tự nhiên đều có thể viết ở dạng tích một số lẻ với 2 lũy thừa

một số nguyên không âm. Hay nói cách khác, số nguyên dương a_i, i = 1, . . . , n + 1, có thể

được biểu diễn a_i= 2^kⁱq_i, trong đó k_ilà số nguyên không âm và q_ilà số lẻ.

Ta biết rằng n + 1 số a_isẽ tương ứng có n + 1 số q_i, mà các số a_i< 2n dẫn đến q_i< 2n,

đồng nghĩa với q_ichỉ có n giá trị khác nhau (có n nguyên dương lẻ khác nhau bé hơn 2n).

Theo nguyên lý chuồng chim bồ câu, sẽ có ít nhất 2 số (chẳng hạn a_ivà a_j) có q_i= q_j.

Vậy ta có thể biểu diễn a_i= 2^kⁱq_ivà a_j= 2^k^jq_i. Nếu k_i≤ k_j, a_jsẽ chia hết cho a_i. Ngược

lại, a_ichia hết cho a_j. Vậy suy ra điều phải chứng minh.

2

Câu 8.

Có bao nhiêu cách để 8 người đàn ông và 5 người phụ nữ đứng vào một hàng sao cho không

có hai người phụ nữ nào đứng kế nhau?

Lời giải.

• Đầu tiên ta xếp 8 người đàn ông vào hàng 8 người, có P(8) cách sắp xếp.

• Hàng 8 người đàn ông tạo ra 7 chỗ trống ở giữa họ và 2 chỗ ở 2 đầu hàng. 5 người

phụ nữ sẽ được xếp vào 9 chỗ trống này để đảm bảo họ không bao giờ đứng kế nhau:

P(9, 5)

Kết quả: P(8)P(9, 5)

2

Giáo trình Toán Rời Rạc 1

Trang 5/8

Trường Đại Học Bách Khoa Tp.Hồ Chí Minh

Khoa Khoa Học và Kỹ Thuật Máy Tính

Câu 9.

Có bao nhiêu cách để xếp chỗ cho 6 người ngồi quanh một bàn tròn?

Lời giải.

Bài toán trở thành xếp chỗ theo hàng ngang khi ta cố định chỗ ngồi của 1 người. Như

vậy việc sắp xếp sẽ là các chỗ ngồi khác nhau ở một bên của người làm mốc: P(5).

2

Câu 10.

Một cửa hàng kẹo có bán các loại kẹo dẻo, kẹo cứng, kẹo trái cây, kẹo mạch nha, kẹo mút,

kẹo cam thảo, kẹo bông và kẹo bọc đường. Có bao nhiêu cách để chọn

1. sáu viên kẹo?

2. một tá kẹo?

3. hai tá kẹo?

4. một tá kẹo với mỗi loại có ít nhất một viên?

5. một tá kẹo với ít nhất 3 kẹo trái cây và không có quá hai viên kẹo cứng?

Lời giải.

Đầu tiên phải xác định được là cửa hàng có bán 8 loại kẹo khác nhau, tất nhiên số

lượng kẹo mỗi loại là không giới hạn và các viên kẹo cùng loại không phân biệt được với

nhau. Đây là dạng tổ hợp lặp. Ở đây, tôi không dùng công thức mà giải dựa vào suy luận

và quy tắc cộng và nhân.

1. Có 6 viên kẹo xếp thành hàng, dùng 7 vách ngăn đặt vào bất cứ vị trí nào giữa 6

viên kẹo sẽ tạo ra 8 ô, tương ứng với 8 loại kẹo. Khi đó ta sẽ xác định được số viên

kẹo mỗi loại trong số 6 viên. Nói cách khác, chọn sáu viên kẹo từ 8 loại kẹo tương

đương với việc đầu tiên chọn vị trí cho 6 viên kẹo trong hàng gồm 13 vị trí, rồi 7 vị

trí còn trống sẽ là 7 vách ngăn: C(13, 6).

2. Tương tự, C(19, 12).

3. Tương tự, C(31, 24).

4. Lấy sẵn mỗi loại một viên, vậy ta chỉ cần phải chọn ngẫu nhiên 4 viên trong 8 loại

nữa: C(11, 4).

5. Có ít nhất 3 kẹo trái cây tức là đã có chắc chắn 3 viên trái cây, còn lại thoải mái lựa

chọn: C(16, 9). Trong số các khả năng lựa chọn đó, số lượng khả năng ít nhất 3 viên

kẹo cứng, tương tự như trên, nhưng giờ chỉ còn được chọn 6 chứ không phải 9 viên:

C(13, 6). Dẫn đến đáp số của bài là C(16, 9) − C(13, 6).

Giáo trình Toán Rời Rạc 1

Trang 6/8

Trường Đại Học Bách Khoa Tp.Hồ Chí Minh

Khoa Khoa Học và Kỹ Thuật Máy Tính

2

Câu 11.

Giả sử một gia đình có 14 đứa con, trong có hai nhóm sinh 3, ba cặp sinh đôi, và 2 đứa

sinh một. Có bao nhiêu cách để sắp chỗ ngồi cho chúng thành 1 hàng nếu các nhóm trẻ

sinh ba và sinh đôi là không thể phân biệt được giữa chúng với nhau?

Lời giải.

Có thể dùng công thức dạng Tổ hợp có phần tử không phân biệt được với nhau, hoặc

sử dụng cách suy nghĩ theo nguyên tắc cộng, nhân và tổ hợp, chỉnh hợp thông thường để

giải quyết. Có 14 chỗ tổng cộng, đầu tiên xếp chỗ cho nhóm sinh 3 đầu tiên C(14, 3), xếp

cho nhóm sinh 3 thứ hai C(11, 3), xếp cho cặp sinh đôi đầu tiên C(8, 2), xếp cho cặp thứ

hai C(6, 2), cặp thứ ba C(4, 2), đứa sinh một đầu tiên C(2, 1) và đứa cuối cùng C(1, 1).

Vậy kết quả sẽ là:

C(14, 3)C(11, 3)C(8, 2)C(6, 2)C(4, 2)C(2, 1)

2

4 Bài tập làm thêm

Câu 12.

Một trăm tờ vé số, được đánh số từ 1, 2, 3, . . ., 100, được bán cho 100 người khác nhau để

rút thăm. Sẽ có bốn giải được trao, trong đó có một giải đặc biệt. Có bao nhiêu cách để

trao giải nếu

1. không có bất kỳ hạn chế nào?

2. người đang giữ vé 47 giành giải đặc biệt?

3. người đang giữ vé 47 giành được một giải?

4. người đang giữ vé 47 không giành giải nào cả?

5. những người đang giữ vé 19 và 47 đều giành giải?

6. những người đang giữ vé 19, 47, và 73 đều giành giải?

7. những người đang giữ vé 19, 47, 73, và 97 đều giành giải?

8. không có ai trong số những người đang giữ vé 19, 47, 73, và 97 giành giải?

9. người thắng giải đặc biệt là người đang giữ vé 19, 47, 73, hoặc 97?

10. người đang giữ vé 19 và 47 giành giải, nhưng người giữ vé 73 và 97 không giành giải?

Giáo trình Toán Rời Rạc 1

Trang 7/8

Trường Đại Học Bách Khoa Tp.Hồ Chí Minh

Khoa Khoa Học và Kỹ Thuật Máy Tính

Câu 13.

Cho n là một số nguyên dương. Chứng minh rằng trong bất kỳ tập gồm n số nguyên liên

tiếp, luôn có chính xác một số chia hết cho n.

Câu 14.

Hai anh em John chia nhau một bịch kẹo có 100 viên.

Biết rằng em John chỉ mới 3 tuổi nên chỉ biết đếm từ 1 tới 9.

Với những số lớn hơn 9 thì lại chỉ đếm được thành hàng đơn vị (nghĩa là 10 sẽ đếm thành

0, 11 đếm thành 1...).

Khi John chia kẹo cho 2 anh em, nếu em của John đếm kẹo của 2 bên mà khác nhau thì

sẽ khóc.

Hỏi John có bao nhiêu cách chia 100 viên kẹo để em mình không khóc và số kẹo của John

luôn nhiều hơn kẹo của em.

Câu 15.

Có bao nhiêu hoán vị của 26 kí tự Tiếng Anh mà không chứa các chuỗi "fish", "rat" và

"bird".

Câu 16.

Có bao nhiêu quan hệ trên tập gồm n phần tử là quan hệ phản xạ? Giải thích.

Câu 17.

Cho A và B lần lượt là các tập hợp có m và n phần tử. Xác định số lượng các quan hệ từ

A đến B. Giải thích.

Câu 18.

Có bao nhiêu lời giải cho phương trình

x₁+ x₂+ x₃+ x₄+ x₅= 21,

trong đó x_i, i = 1, 2, 3, 4, 5, là số nguyên không âm sao cho

1. x₁≥ 1?

2. x_i≥ 2 với i = 1, 2, 3, 4, 5?

3. 0 ≤ x₁≤ 10?

4. 0 ≤ x₁≤ 3, 1 ≤ x₂< 4, và x₃≥ 15?

5 Tổng kết

Thông qua các bài tập trong phần này, chúng ta đã hiểu rõ hơn và làm quen với các phép

đếm (bao gồm lượng số, tổ hợp, chỉnh hợp, và các nguyên lý đếm) mà chi tiết về lý thuyết

đã được trình bày trong slide chương 3.

Giáo trình Toán Rời Rạc 1

Trang 8/8