Ôn tập Câu hỏi toán học nâng cao - Môn Toán | Toán Rời Rạc | Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội

1. Cho {v1, . . . , vn} là các véctơ độ dài 1 trong Rd. Chứng minh rằng tồn tại một véctơ (ϵ1, . . . , ϵn) √
với ϵi ∈ {±1} sao cho véctơ Pn ϵ n i ≤ =1 ivi có chuẩn Euclidean .
2. Chọn ngẫu nhiên một phép thế σ trên tập {1, ..., n}. Tính giá trị kì vọng của số điểm cố định.
3. Cho F là một họ các tập gồm 3 phần tử của X. Chứng minh rằng các phần tử của X có thể tô
với 3 màu sao cho có ít nhất |F| · 3!/33 tập trong F sao cho mọi phần tử đều có màu khác nhau.
4. Cho B = {b1, . . . , bn} là một tập các số nguyên khác không. Chứng minh rằng tồn tại một tập
con A ⊂ B sao cho |A| > n/3 và không tồn tại ba phần tử a1, a2, a3 ∈ A sao cho a1 + a2 = a3.
5. Chứng minh rằng các cạnh của Kn có thể tô bằng ba màu sao cho số tam giác đồng màu ≤ 1 · n. 9 3
6. Chứng minh rằng thuật toán Prim trả về một cây bao trùm.
7. Chứng minh tính đúng đắn của thuật toán Kruskal.
8. Cho X = R2 và F là họ tất cả các hình chữ nhật Sz F
1 ,z2 ,z3 ,z4 . Tìm số chiều VC của .
9. Cho X = R2 và F là họ tất cả các đường tròn trên X. Tìm số chiều VC của F .
10. Cho X = R2 và F là họ tất cả các hàm trên X có dạng
fw,b(x) = sign(w · x + b), w, x ∈ X, b ∈ R. Tìm số chiều VC của F .
11. Cho X = R và F là họ tất cả các khoảng [a, b] với b − a = 1. Tìm số chiều VC của F .
12. Tìm mọi giá trị của n sao cho ϕ(n) không chia hết cho 4.
13. Tìm mọi giá trị của n sao cho ϕ(n) = 10.
14. Chứng minh rằng nếu gcd(m, n) = 1 thì ϕ(mn) = ϕ(m)ϕ(n).
15. Có bao nhiêu số nguyên dương chia hết 1040 hoặc 2030?
16. Xác định số phép thế với chính xác k điểm cố định trên một tập gồm n phần tử.
17. Có bao nhiêu số nguyên dương ≤ 385 không chia hết cho một trong các số sau: 5, 7, 11? 18. Chứng minh rằng P
ϕ(d) = n với mọi số tự nhiên n. d|n
19. Có bao nhiêu cách đặt k quả bóng vào n hộp sao cho mỗi hộp có nhiều nhất 1 quả và k ≤ n? 1
20. Tìm số nghiệm của phương trình sau x1 + x2 + x3 + x4 = 100,
với xi ∈ N và x1 ≥ 0, x2 > 5, x3, x4 ≥ 0.
21. Cho X là một tập các số tự nhiên. Giả sử rằng tồn tại hai tập con B1 và B2 khác rỗng sao cho
tổng các phần tử trong B1 bằng tổng các phần tử trong B2. Chứng minh rằng ta có thể tìm hai
tập con B′ and B′ của X sao cho B′ 1 2 1 ∩ B′ = 2
∅ và chúng có cùng tổng.
22. Chứng minh mọi tập gồm 10 số phân biệt lấy từ tập {1, . . . , 100} chứa 2 tập con không rỗng rời nhau và có cùng tổng.
23. Cho n ∈ N, tìm số tập con của {1, 2, ..., n} có cấp chẵn, và số tập con có cấp lẻ.
24. Chứng minh rằng mọi đồ thị phẳng G với n ≥ 3 đỉnh có ≤ 3n − 6 cạnh.
25. Chứng minh rằng mọi đồ thị 2 phần phẳng với ít nhất 3 đỉnh có ≤ 2n − 4 cạnh.
26. Chứng minh đồ thị K5,5 không phẳng (không sử dụng công thức số cạnh ≤ 3n − 6).
27. Xác định mọi số nguyên dương r và s sao cho Kr,s là phẳng.
28. Cho G là một đồ thị với n đỉnh và 3n − 6 + k cạnh, trong đó k > 0. Chứng minh rằng với bất
kì cách vẽ nào của G trên mặt phẳng, ta luôn có ít nhất k cặp cạnh cắt nhau.
29. Cho G là một đồ thị phẳng với < 12 đỉnh. Chứng minh rằng G có một đỉnh bậc ≤ 4.
30. Cho G là một đồ thị phẳng với n đỉnh, chứng minh rằng với 3 đỉnh bất kì x, y, z, ta có d(x) + d(y) + d(z) ≤ 2n + 2.
31. Tìm các giá trị n sao cho đồ thị Kn chứa (a) Euler trail (b) Euler tour (c) Đường đi Hamilton (d) Chu trình Hamilton
32. Với những giá trị nào của m và n thì đồ thị hai phần Km,n chứa một Euler tour? Xác định độ
dài đường đi dài nhất và chu trình dài nhất trong Km,n?
33. Cho G là một đồ thị liên thông và có Euler tour. Trong những khẳng định sau, khẳng định nào đúng:
(a) Nếu G là hai phần thì số cạnh của G là chẵn.
(b) Nếu G có số đỉnh chẵn thì G có số cạnh chẵn
(c) Với hai cạnh e và f có chung một đỉnh, G có một Euler tour sao cho e và f xuất hiện liên tiếp nhau.
34. Chứng minh rằng nếu k > 0 thì tập cạnh của một đồ thị liên thông với 2k đỉnh bậc lẻ có thể phân hoạch thành k trails.
35. Chứng minh rằng trong mọi đồ thị liên thông G, luôn có một walk sao cho mỗi cạnh xuất hiện chính xác hai lần.
36. Định nghĩa số chiều VC. 2
37. Định nghĩa không gian xác suất, biến ngẫu nhiên, giá trị kỳ vọng, và chứng minh tính chất số (4).
38. Định nghĩa đồ thị, cây, chu trình, đường đi, walk, Euler tour, chu trình Hamilton.
39. Trình bày thuật toán tìm kiếm cây bao trùm theo chiều rộng, thuật toán Prim, thuật toán Kruskal.
40. Định nghĩa cách vẽ, cách vẽ phẳng, đồ thị phẳng, và phát biểu công thức Euler.
41. Định nghĩa hàm Euler và công thức tính ϕ(pα1 ). 1 · · · pαn n
42. Trình bày bài toán trả mũ. 3