Xem bài viết đơn
Old 17-04-2012, 11:31 PM   #29
ThangToan
+Thành Viên+
 
Tham gia ngày: Nov 2010
Đến từ: THPT chuyên Vĩnh Phúc
Bài gởi: 570
Thanks: 24
Thanked 537 Times in 263 Posts
Trích:
Nguyên văn bởi hoangcongduc View Post

Bài 6: (7 điểm)
Có 42 học sinh tham dự kì thi chọn đội tuyển Olympic toán quốc tế. Biết rằng một học sinh bất kì quen đúng 20 học sinh khác. Chứng minh rằng ta có thể chia 42 học sinh thành 2 nhóm hoặc 21 nhóm sao cho số học sinh trong các nhóm bằng nhau và 2 học sinh bất kì trong cùng nhóm thì quen nhau.
Có lẽ bài này là kết quả mở rộng của định lý liên quan đến cặp ghép sau:
Cho đồ thị vô hướng $G=(V, E) $ với $|X|\ge 2n $ và bậc của mỗi đỉnh của đồ thị đều không nhỏ hơn $n $. Khi đó trong $G $ luôn tồn tại một đồ thị bộ phận hai mảng $G_1=(V_1, V_2, E_1) $ ($E_1 $ là tập con của $E $) với $|V_1|=n $ đồng thời ghép cặp được $V_1 $ với $V_2 $ (trên đồ thị bộ phận)
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
ThangToan is offline   Trả Lời Với Trích Dẫn
 
[page compression: 8.10 k/9.10 k (11.08%)]