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

Download

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 6 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

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

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, P(9, 5) =

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

Giáo trình Cấu Trúc Rời Rạc

Trang 1/4

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

• 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, P(8, 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)

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

Câu 3.

1. Sắp xếp 5 người vào một băng ghế có 5 chỗ ngồi. Hỏi có bao nhiêu cách xếp?

2. Có 10 học sinh được yêu cầu xếp thành hàng dọc, trong đó có bạn An. Hỏi có bao nhiêu cách

xếp sao cho An luôn đứng đầu hàng?

3. Từ các chữ số 0, 1, 2, 3, 4 có thể lập được mấy số tự nhiên có 5 chữ số khác nhau?

Câu 4.

Hai hộp chứa các quả banh: hộp thứ nhất chứa 3 quả đỏ và 2 quả xanh; hộp thứ hai chứa 4 quả đỏ

và 6 quả xanh. Hỏi có bao nhiêu cách lấy 3 quả banh sao cho:

1. 3 quả bất kỳ

2. 3 quả đỏ

3. 3 quả xanh

4. 3 quả trong đó có 2 quả đỏ, 1 quả xanh

5. 3 quả trong đó có ít nhất 1 quả đỏ.

Câu 5.

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ể?

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

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

Câu 6.

Một bài kiểm tra trắc nghiệm gồm 10 câu hỏi. Mỗi câu hỏi có 4 lựa chọn trả lời.

a) Có bao nhiêu cách mà một sinh viên làm bài kiểm tra trắc nghiệm nếu mỗi câu hỏi đều được sinh

viên đó trả lời.

Giáo trình Cấu Trúc Rời Rạc

Trang 2/4

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) Có bao nhiêu cách mà một sinh viên làm bài kiểm tra trắc nghiệm nếu các câu hỏi cho phép bỏ

trống.

Câu 7.

Có bao nhiêu số nguyên dương từ 100 đến 999 sao cho

a) chia hết cho 7?

b) là số lẻ?

c) không chia hết cho 4?

d) chia hết cho 3 và 4?

e) chia hết cho 3 hoặc 4?

f) không chia hết cho 3 hoặc 4?

g) chia hết cho 3 nhưng không chia hết cho 4?

Câu 8.

Một rổ gồm 10 trái banh xanh và 10 trái banh đỏ. Bạn An chọn ngẫu nhiên các trái banh mà không

nhìn vào rổ.

a) Bạn An phải chọn bao nhiêu trái banh để đảm bảo có ít nhất 3 trái cùng màu?

b) Bạn An phải chọn bao nhiêu trái banh để đảm bảo có ít nhát 3 trái màu xanh?

Câu 9.

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?

Câu 10.

Chứng minh rằng giữa 4 số bất kỳ ta luôn tìm được 2 số sao cho hiệu của chúng chia hết cho 3.

Câu 11.

Một đồng xu được tung 10 lần, biết mỗi lần tung đồng xu chỉ cho ra mặt sấp hoặc mặt ngửa. Có bao

nhiêu trường hợp:

a) có thể xảy ra tất cả?

b) đúng hai mặt ngửa?

c) nhiều nhất ba mặt sấp?

d) số mặt ngửa bằng với số mặt sấp?

Câu 12.

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?

Câu 13.

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

Câu 14.

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

Giáo trình Cấu Trúc Rời Rạc

Trang 3/4

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

Câu 15.

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?

Câu 16.

Có bao nhiêu cách xếp 5 trái banh vào 3 hộp nếu mỗi hộp phải có ít nhất một trái nếu

a) cả hộp và banh đều phân biết?

b) các trái banh không phân biệt, nhưng các hộp thì phân biệt?

Câu 17.

Có bao nhiêu số tự nhiên gồm 3 chữ số thập phân sao cho:

a) Không chứa cùng một chữ số ba lần.

b) Bắt đầu bằng chữ số lẻ.

c) Có đúng hai chữ số 4.

Câu 18.

Có bao nhiêu chuỗi gồm 4 chữ số thập phân sao cho

a) không chứa chữ số nào hai lần?

b) kết thúc chuỗi với một chữ số chẵn?

c) có đúng ba chữ số là 9?

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

Câu 19.

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?

Câu 20.

a) Tìm số nghiệm nguyên của phương trình x₁+ x₂+ x₃+ x₄= 20 với x₁≥ 6, x₂≥ 3, x₃≥ 9 và

x₄≥ −2

b) Tìm số nghiệm nguyên không âm của bất phương trình x₁+ x₂+ x₃≤ 11

Câu 21.

Cho tập X = {0, 1, 2, ..., 15}. Chứng minh rằng nếu S là một tập con gồm 9 phần tử của X thì có ít

nhất 2 phần tử của S có tổng bằng 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 6.

Giáo trình Cấu Trúc Rời Rạc

Trang 4/4

4 trang baolam 26/04/2022 3180

Download

Bạn đang xem tài liệu "Giáo trình Cấu trúc rời rạc - Bài tập chương 6: Phép đếm", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

giao_trinh_cau_truc_roi_rac_bai_tap_chuong_6_phep_dem.pdf