Bài viết đã được chỉnh sửa nội dung bởi alex_hoang: 27-01-2012 - 15:06
Bài toán đơn biến
Bắt đầu bởi alex_hoang, 26-01-2012 - 00:28
#1
Đã gửi 26-01-2012 - 00:28
Đề 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ù
#2
Đã gửi 26-01-2012 - 23:43
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
- Trần Đức Anh @@ yêu thích
\
#3
Đã gửi 27-01-2012 - 06:49
Đâ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.
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh