Trích:
| Bài 6: Giả sử ko có cách chia 2 nhóm. Ban đầu ta chia các thí sinh đó thành các nhóm gồm hai thành viên và hai thí sinh đó phải quen nhau. Gọi tập các nhóm là S. Nếu S có đủ 21 nhóm thì ta đc đpcm. Xét trường hợp S có ít hơn 21 nhóm và các thí sinh ko thuộc S ko thể tạo nên1 cặp vs thí sinh khác để thuộc S. Thì ta xét thí sinh b thuộc S quen với a ko thuộc S mà người thuộc nhóm vs b trong S là c cũng quen vs d ko thuộc S thì ta chỉ cần cho a và b, c và d thành 1 cặp. Cách chọn này luôn tồn tại vì số người quen cuả mỗi người là 20 mà số nhóm trong S nhỏ hơn hoặc bằng 20. Như thế sau mỗi lần thực hiện số người ko thuộc S giảm đi 2. Mà số người ko thuộc S ko âm nên qúa trình này phải dừng. Vì ta giả sử ko có cách chia 2 nhóm tức là tập đỉnh của đồ thị này ko thể chia làm 2 thành phần đày đủ 21 phần và ko có cầu, nên quá trình này ko thể dừng ở 2.Vì nếu nó dừng ở 2 thì do trong S có 20 cặp . Và bậc đỉnh mỗi đỉnh là 20 nên theo định lí Turản ta suy ra được trong S chứa tập đầy đủ 20 đỉnh.. và 20 đỉnh còn lại cũng tạo thành 1 tập đầy đủ. Do đó 2 đỉnh ko thuộc S sẽ phải lần lượt thuộc 2 tập này lúc đó tạo ra 2 nhóm thỏa mãn ( mâu thuẫn với điều giả sử) vậy phải dừng ở 0. Lúc này ta có 21 tập thỏa mãn |
Một bài giải của bạn
The Gunner bên VMF, ko biết có đúng ko
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]