Số các xâu nhị phân có độ dài nhỏ hơn hoặc bằng 8 là.

1024

512

510

1022

Trả lời:

Đáp án đúng: C

Số xâu nhị phân có độ dài k là 2^k. Vậy số xâu nhị phân có độ dài nhỏ hơn hoặc bằng 8 là: 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^7 + 2^8 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 = 511.

500+ câu hỏi trắc nghiệm Toán rời rạc có đáp án kèm giải thích - Phần 11

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 18:

Trong 100 người có ít nhất mấy người cùng tháng sinh?

Lời giải:

Đáp án đúng: B

Ta sử dụng nguyên lý Dirichlet (hay còn gọi là nguyên lý chuồng bồ câu). Nguyên lý này phát biểu rằng nếu có n con bồ câu nhốt vào m chuồng, với n > m, thì tồn tại ít nhất một chuồng có ít nhất hai con bồ câu.

Trong bài toán này, ta có thể coi 100 người là "n con bồ câu" và 12 tháng trong năm là "m chuồng". Nếu ta chia đều 100 người cho 12 tháng, mỗi tháng sẽ có \(\lfloor\frac{100}{12}\rfloor = 8\) người. Tuy nhiên, vì 100 không chia hết cho 12, sẽ có một số tháng có nhiều hơn 8 người.

Để tìm số người ít nhất cùng tháng sinh, ta tính \(\lceil\frac{100}{12}\rceil = 9\). Điều này có nghĩa là, chắc chắn sẽ có ít nhất một tháng có ít nhất 9 người sinh cùng tháng.

Vậy, trong 100 người, có ít nhất 9 người cùng tháng sinh.

Câu 19:

Cần phải có tối thiểu bao nhiêu sinh viên ghi tên vào lớp Toán rời rạc để chắc chắn sẽ có ít nhất 6 sinh viên đạt cùng một điểm thi nếu thang điểm gồm 5 bậc?

Lời giải:

Đáp án đúng: C

Đây là một bài toán ứng dụng nguyên lý Dirichlet (hay còn gọi là nguyên lý chuồng bồ câu). Nguyên lý này phát biểu rằng nếu có n chuồng và m > n con bồ câu, thì ít nhất một chuồng phải chứa nhiều hơn một con bồ câu.

Trong bài toán này, các "chuồng" là các bậc điểm thi (5 bậc), và các "con bồ câu" là các sinh viên. Chúng ta muốn tìm số lượng sinh viên tối thiểu (m) sao cho ít nhất một bậc điểm có ít nhất 6 sinh viên.

Giả sử số lượng sinh viên ở mỗi bậc điểm là tối đa, tức là 5 sinh viên. Khi đó, tổng số sinh viên là 5 (bậc điểm) * 5 (sinh viên mỗi bậc) = 25 sinh viên.

Nếu ta thêm 1 sinh viên nữa (tức là 26 sinh viên), thì chắc chắn phải có ít nhất một bậc điểm có 6 sinh viên (vì nếu không, số sinh viên tối đa chỉ có thể là 25).

Vậy, cần tối thiểu 26 sinh viên để đảm bảo có ít nhất 6 sinh viên đạt cùng một điểm thi.

Câu 20:

Cho tập A = {-12, -11,…11, 12} và quan hệ tương đương trên A: R = {(a,b)| a ≡ b(mod 4)}. Hỏi R sẽ tạo ra một phân hoạch gồm bao nhiêu tập con trên A?

Lời giải:

Đáp án đúng: D

Tập A = {-12, -11, ..., 11, 12} bao gồm các số nguyên từ -12 đến 12. Quan hệ tương đương R được định nghĩa là a ≡ b (mod 4), nghĩa là a và b có cùng số dư khi chia cho 4.

Để tìm số tập con trong phân hoạch, ta cần xác định số lượng các số dư khác nhau có thể có khi chia các phần tử của A cho 4. Các số dư có thể là 0, 1, 2, và 3.

Ta có thể liệt kê các phần tử của A theo số dư của chúng khi chia cho 4:
- Số dư 0: -12, -8, -4, 0, 4, 8, 12 (7 phần tử)
- Số dư 1: -11, -7, -3, 1, 5, 9 (6 phần tử)
- Số dư 2: -10, -6, -2, 2, 6, 10 (6 phần tử)
- Số dư 3: -9, -5, -1, 3, 7, 11 (6 phần tử)

Mỗi số dư khác nhau tương ứng với một tập con trong phân hoạch. Vì có 4 số dư khác nhau (0, 1, 2, 3), nên R sẽ tạo ra một phân hoạch gồm 4 tập con trên A.

Vậy đáp án đúng là D. 4

Câu 21:

Cho tập A = {-12, -11,…11, 12} và quan hệ tương đương trên A: R = {(a,b)| a≡b(mod 3)}. Hỏi R sẽ tạo ra một phân hoạch gồm bao nhiêu tập con trên A?

Lời giải:

Đáp án đúng: C

Tập A = {-12, -11,…11, 12} gồm các số nguyên từ -12 đến 12. Quan hệ tương đương R = {(a,b)| a≡b(mod 3)} nghĩa là a và b có cùng số dư khi chia cho 3.

Chúng ta cần xác định số lượng tập con trong phân hoạch của A do R tạo ra. Các tập con này tương ứng với các lớp tương đương theo modulo 3.

Các số dư khi chia cho 3 có thể là 0, 1 hoặc 2. Do đó, có 3 lớp tương đương:

- Lớp các số chia hết cho 3: {..., -12, -9, -6, -3, 0, 3, 6, 9, 12, ...}
- Lớp các số chia 3 dư 1: {..., -11, -8, -5, -2, 1, 4, 7, 10, ...}
- Lớp các số chia 3 dư 2: {..., -10, -7, -4, -1, 2, 5, 8, 11, ...}

Mỗi số trong tập A sẽ thuộc đúng một trong ba lớp này. Vì vậy, R tạo ra một phân hoạch gồm 3 tập con trên A.

Câu 22:

Cho tập A = {-12, -11, …, 11, 12}, và quan hệ R = {(a,b)| a ≡ b (mod 3)}. Hãy cho biết tập nào trong số các tập sau là lớp tương đương của phần tử -8?

Lời giải:

Đáp án đúng: A

Để tìm lớp tương đương của -8 theo quan hệ đồng dư modulo 3, ta cần tìm tất cả các phần tử a trong tập A sao cho a ≡ -8 (mod 3). Điều này có nghĩa là a - (-8) chia hết cho 3, hay a + 8 chia hết cho 3.

Kiểm tra từng đáp án:

Đáp án A: {-11, 4, -8, -5, 1, 7, 10, -2}
- -11 + 8 = -3 chia hết cho 3
- 4 + 8 = 12 chia hết cho 3
- -8 + 8 = 0 chia hết cho 3
- -5 + 8 = 3 chia hết cho 3
- 1 + 8 = 9 chia hết cho 3
- 7 + 8 = 15 chia hết cho 3
- 10 + 8 = 18 chia hết cho 3
- -2 + 8 = 6 chia hết cho 3
Vậy đáp án A thỏa mãn.
Đáp án B: {-12, 3, -8, 5, -2, 4, -10}
- -12 + 8 = -4 không chia hết cho 3
Vậy đáp án B không thỏa mãn.
Đáp án C: {-1, 4, 6, -9, -8, -4, 3, 9}
- -1 + 8 = 7 không chia hết cho 3
Vậy đáp án C không thỏa mãn.
Đáp án D: {-9, 6, 1, -8, 3, -5, 0, -12}
- 1 + 8 = 9 chia hết cho 3
- -5 + 8 = 3 chia hết cho 3
- -12 + 8 = -4 không chia hết cho 3
Vậy đáp án D không thỏa mãn.

Vậy, đáp án đúng là A.

Câu 23:

Cho quan hệ R = {(a,b)| a ≡ b(mod 5)} trên tập {-12, -11, …,11, 12}. Hãy xác định [2]_R?

Lời giải: