Chủ đề này có 2 trả lời

[alex_hoang]

Đề bài Trong quốc hội Mỹ,mỗi nghị sỹ có không quá $3$ kẻ thù.Chứng minh rằng có thể chia quốc hội thành hai viện sao cho trong mỗi viện,mỗi nghị sỹ có không quá một kẻ thù

Bài viết đã được chỉnh sửa nội dung bởi alex_hoang: 27-01-2012 - 15:06

[Peter Pan]

Ban đầu chia bất kì các Nghị sĩ thành 2 nhóm, gọi S là số các cặp kẻ thù trong cùng 1 nhóm, nếu 1 người có số kẻ thù ít nhất là 2 trong nhóm này thì sẽ có nhiều nhất 1 kẻ thù trong nhóm kia, giờ ta chuyển người này qua nhóm kia thì S sẽ giảm đi ít nhất là 1.Vì S là số nguyên dương ko âm nên quá trình này sẽ dừng sau hữu hạn bước khi đó ta được 2 nhóm thỏa mãn

[batigoal]

Đây là bài toán đơn biến chứ không phải bất biến và cách giải như bạn winwave đã trình bày. Quá trình dừng sau một số hữu hạn bước.