Cho đồ thị có hướng G = (V, E) trong đó tập đỉnh V = {1,2,3,4,5,6} và tập cung E = {(1,2),(2,5),(2,6),(3,1),(3,2),(5,4),(5,6),(6,1),(6,4)}. Hỏi có thể tiến hành sắp xếp TOPO các đỉnh trên G hay không?

Đồ thị lưỡng phân đầy đủ K_{m,n} có m * n cạnh.
Trong trường hợp này, K_{3,5} có 3 * 5 = 15 cạnh.
Vậy đáp án đúng là D.

Xét đồ thị vô hướng G có 10 đỉnh, bậc của mỗi đỉnh lớn hơn hoặc bằng 5. Ta cần chứng minh hoặc phản chứng G luôn liên thông.

Giả sử G không liên thông, tức là G có ít nhất hai thành phần liên thông. Gọi số đỉnh của một thành phần liên thông là k (1 ≤ k ≤ 9). Khi đó, số đỉnh của thành phần liên thông còn lại là 10 - k.

Xét thành phần liên thông có k đỉnh. Vì bậc của mỗi đỉnh lớn hơn hoặc bằng 5, nên k ≥ 6. Nếu k < 6 thì bậc của đỉnh trong thành phần đó tối đa là k-1 < 5 (mâu thuẫn với giả thiết đề bài). Vì vậy k phải >= 6.

Tương tự, xét thành phần liên thông có 10 - k đỉnh. Vì bậc của mỗi đỉnh lớn hơn hoặc bằng 5, nên 10 - k ≥ 6, suy ra k ≤ 4.

Ta thấy rằng không thể đồng thời có k ≥ 6 và k ≤ 4. Điều này chứng tỏ giả sử ban đầu của chúng ta là sai. Vậy nên, đồ thị G phải liên thông.

Vậy phát biểu "G luôn là đồ thị liên thông" là đúng.

Để một hàm số f: R -> R khả nghịch, nó phải là một song ánh, tức là vừa đơn ánh (injective) và vừa toàn ánh (surjective).

* A. f(x) = x² − 4x + 5: Đây là một hàm bậc hai. Ta có thể viết lại f(x) = (x - 2)² + 1. Vì (x - 2)² ≥ 0, nên f(x) ≥ 1. Hàm này không toàn ánh vì không có giá trị x nào để f(x) = 0 (ví dụ). Hơn nữa, f(1) = f(3) = 2, nên hàm này không đơn ánh. Vậy hàm này không khả nghịch.

* B. f(x) = x⁴: Hàm này cũng không khả nghịch. Ví dụ, f(1) = f(-1) = 1, nên nó không đơn ánh. Hơn nữa, x⁴ ≥ 0, nên nó cũng không toàn ánh vì không có giá trị x nào để f(x) = -1 (ví dụ).

* C. f(x) = x³: Hàm này là một hàm bậc ba. Với mọi y thuộc R, tồn tại duy nhất một x thuộc R sao cho x³ = y, cụ thể là x = căn bậc ba của y. Vậy hàm này vừa đơn ánh vừa toàn ánh, do đó nó khả nghịch.

* D. f(x) = 6 − x²: Hàm này không khả nghịch. Ví dụ, f(1) = f(-1) = 5, nên nó không đơn ánh. Hàm này cũng không toàn ánh vì f(x) ≤ 6 với mọi x thuộc R. Ví dụ không có giá trị x nào để f(x) = 7.

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

Ta cần tìm số lượng phần tử ít nhất cần lấy ra từ tập A để chắc chắn có một cặp số có tổng bằng 20.

Các cặp số trong tập A có tổng bằng 20 là: (1, 19), (3, 17), (5, 15), (7, 13), (9, 11).

Để chắc chắn có ít nhất một cặp có tổng bằng 20, ta cần xét trường hợp xấu nhất là lấy ra các số mà không tạo thành cặp nào có tổng bằng 20.

Ta có thể lấy ra các số: 1, 3, 5, 7, 9. Khi đó ta đã lấy ra 5 số và chưa có cặp nào có tổng bằng 20. Ta có thể lấy thêm số 10 là số không thuộc tập A, nhưng vì bài toán yêu cầu lấy từ tập A nên ta phải xét các phần tử còn lại.

Nếu ta lấy thêm bất kỳ một số nào trong các số còn lại của tập A (11, 13, 15, 17, 19), ta sẽ tạo thành một cặp có tổng bằng 20.

Ví dụ: Nếu ta lấy thêm số 11, ta có cặp (9, 11) có tổng bằng 20.
Nếu ta lấy thêm số 13, ta có cặp (7, 13) có tổng bằng 20.
Nếu ta lấy thêm số 15, ta có cặp (5, 15) có tổng bằng 20.
Nếu ta lấy thêm số 17, ta có cặp (3, 17) có tổng bằng 20.
Nếu ta lấy thêm số 19, ta có cặp (1, 19) có tổng bằng 20.

Vậy, ta cần lấy ra 5 số {1, 3, 5, 7, 9} trước, sau đó lấy thêm 1 số bất kỳ trong các số còn lại để tạo thành một cặp có tổng bằng 20. Vậy ta cần lấy ít nhất 6 phần tử.

Một cách khác, ta có thể lấy các số lớn hơn 10, tức là {11, 13, 15, 17, 19}. Như vậy, ta lấy 5 số này, không có cặp nào có tổng bằng 20. Nếu ta lấy thêm bất kỳ số nào từ tập {1, 3, 5, 7, 9}, ta cũng sẽ có một cặp có tổng bằng 20. Vậy số phần tử ít nhất cần lấy là 6.

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

Số tập con có ít hơn ba phần tử bao gồm các tập con có 0 phần tử, 1 phần tử và 2 phần tử.

- Số tập con có 0 phần tử là C(100, 0) = 1.
- Số tập con có 1 phần tử là C(100, 1) = 100.
- Số tập con có 2 phần tử là C(100, 2) = 100! / (2! * 98!) = (100 * 99) / 2 = 4950.

Vậy tổng số tập con có ít hơn ba phần tử là 1 + 100 + 4950 = 5051.