Có 5 công việc đánh số 1, 2, 3, 4, 5 và 5 người thợ được đánh số 1, 2, 3, 4, 5. Tùy thuộc tay nghề chuyên môn, mỗi thợ chỉ có thể thực hiện 1 số công việc nào đó: Người thợ 1 chỉ có thể thực hiện công việc 4, thợ 2 chỉ có thể thực hiện công việc 1 hoặc 5, thợ 3 chỉ có thể thực hiện công việc 4, thợ 4 chỉ có thể thực hiện công việc 2 hoặc 3, thợ 5 chỉ có thể thực hiện công việc 1 hoặc 5. Hỏi có thể chọn ra nhiều nhất bao nhiêu công việc để phân công cho thợ sao cho mỗi công việc chỉ được thực hiện bởi duy nhất 1 người thợ (phù hợp tay nghề chuyên môn) và mỗi thợ không được thực hiện quá 1 công việc?

Để tìm độ dài đường đi ngắn nhất từ đỉnh 6 đến đỉnh 3 trong đồ thị bằng thuật toán duyệt theo chiều rộng (BFS), ta thực hiện các bước sau:

1. Bắt đầu từ đỉnh 6: Duyệt các đỉnh kề của đỉnh 6 theo thứ tự từ điển. Các đỉnh kề của 6 là: 1, 2, 4, 5.

2. Duyệt các đỉnh kề của 6:
- Từ 6 đến 1 (độ dài đường đi = 1)
- Từ 6 đến 2 (độ dài đường đi = 1)
- Từ 6 đến 4 (độ dài đường đi = 1)
- Từ 6 đến 5 (độ dài đường đi = 1)

3. Duyệt các đỉnh kề của 1, 2, 4, 5 (theo thứ tự duyệt)
- Từ 1: Các đỉnh kề của 1 là 2, 3, 6. Ta đã duyệt 6, nên xét 2 và 3.
- Từ 6 -> 1 -> 2 (độ dài đường đi = 2)
- Từ 6 -> 1 -> 3 (độ dài đường đi = 2)
Vậy ta đã tìm thấy đường đi từ 6 đến 3 với độ dài bằng 2.

Vậy độ dài đường đi ngắn nhất từ đỉnh 6 đến đỉnh 3 là 2.

Do đó, đáp án đúng là A.

Gọi X = {1, 2, 3, 4}.
Ta có |A \u222a B| = 4 và |A \u2229 B| = 1.
Suy ra |A| + |B| = |A \u222a B| + |A \u2229 B| = 4 + 1 = 5.
Vì A \u2229 B khác rỗng nên ta chọn 1 phần tử thuộc A \u2229 B từ tập X có 4 cách.
Gọi phần tử đó là x. Khi đó A' = A \ {x} và B' = B \ {x} là hai tập con rời nhau của X \ {x} và |A' \u222a B'| = 3.
Với mỗi phần tử y thuộc X \ {x}, ta có 3 khả năng:
- y thuộc A' (và không thuộc B')
- y thuộc B' (và không thuộc A')
- y không thuộc A' và B'
Vậy mỗi phần tử thuộc X \ {x} có 3 cách chọn.
Vì |X \ {x}| = 3 nên số cách chọn A' và B' là 3^3 = 27.
Do đó số bộ (A, B) thỏa mãn là 4 * 27 = 108.
Tuy nhiên, không có đáp án nào trùng với kết quả này. Có lẽ có một lỗi trong các đáp án đã cho. Để giải thích rõ hơn, ta xem xét một cách tiếp cận khác.

Chọn một phần tử chung cho A và B: có 4 cách.
Chọn 3 phần tử còn lại để đưa vào A hoặc B hoặc không thuộc A và B. Vì A \u222a B = {1,2,3,4}, nên mỗi phần tử trong {1,2,3,4} \ {phần tử chung} phải thuộc A hoặc B.
Vậy mỗi phần tử có 2 lựa chọn: thuộc A hoặc thuộc B.
Vậy có 2^3 = 8 cách chọn.
Vậy có tất cả 4*2^3 = 4*8 = 32 cách chọn.
Chọn các phần tử thuộc A giao B: có C(4,1) = 4 cách.
Chọn các phần tử thuộc A \ B, B \ A. Gọi số phần tử của A \ B là x, số phần tử của B \ A là y. Ta có x + y = 3. x, y >=0
Có các trường hợp:
+ x = 0, y = 3: C(3,0) * C(3,3) = 1
+ x = 1, y = 2: C(3,1) * C(2,2) = 3
+ x = 2, y = 1: C(3,2) * C(1,1) = 3
+ x = 3, y = 0: C(3,3) * C(0,0) = 1
=> Tổng số cách chọn = 1 + 3 + 3 + 1 = 8
Vậy số bộ (A,B) = 4*8 = 32

Vì các tập A, B, C đôi một rời nhau, nghĩa là không có phần tử chung nào giữa chúng. Do đó, số phần tử của hợp của ba tập hợp này bằng tổng số phần tử của mỗi tập hợp.
|A∪B∪C| = |A| + |B| + |C| = 100 + 100 + 100 = 300.

Tập X có 9 phần tử {1,2,3,4,5,6,7,8,9}. Tập A là tập con của X, A={1,2,3,8}. Để biểu diễn tập A bằng xâu bit, ta dùng xâu 9 bit, mỗi bit tương ứng với một phần tử của X. Nếu phần tử đó thuộc A thì bit đó là 1, ngược lại là 0.

Vậy, xâu bit biểu diễn tập A là: 111000010 (1 tương ứng với 1, 1 tương ứng với 2, 1 tương ứng với 3, 0 tương ứng với 4, 0 tương ứng với 5, 0 tương ứng với 6, 0 tương ứng với 7, 1 tương ứng với 8, 0 tương ứng với 9).

Công thức đúng là 2ⁿ.

Số tập con của một tập hợp có n phần tử là 2ⁿ, bao gồm cả tập rỗng và chính tập hợp đó.