2 replies to this topic

[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ù

Edited by 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.