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

[lehoan]

1)Có 100 người đến từ 25 quốc gia.Mỗi nước 4 người và họ ngồi trên một cái bàn tròn .CMR ta có thể chia họ thành 4 nhóm sao cho mỗi nhóm có 25 người của 25 quốc qia khác nhau và không có ai cùng nhóm ngồi cạnh nhau trên bàn tròn.

2)Để giải bài toán này lehoan sử dụng bài toán sau: CMR với k chiếc hộp.Mỗi hộp có 2 hòn bi.Các hòn bi được tô bởi 1 trong k màu sao cho mỗi màu được tô cho 2 viên bi.CMR ta có thể lấy từ mỗi hộp một viên bi sao cho có tât cả k màu khác nhau
Đây chỉ là 1 bài toán riêng của bài toán tổng quát có trong quyển graph hữu hạn của VĐH

[pascal]

Nếu ở đây nói là "chứng minh rằng có thể chia ..." thì chỉ cần chỉ ra 1 trường hợp chia được là xong rồi .

Bài viết đã được chỉnh sửa nội dung bởi pascal: 17-06-2005 - 12:48

[chuyentoan]

ở đây là chứng minh với mọi cách chia đều có thể chọn được !!!!!!!!

[LNH]

1)Có 100 người đến từ 25 quốc gia.Mỗi nước 4 người và họ ngồi trên một cái bàn tròn .CMR ta có thể chia họ thành 4 nhóm sao cho mỗi nhóm có 25 người của 25 quốc qia khác nhau và không có ai cùng nhóm ngồi cạnh nhau trên bàn tròn.

Bổ đề: Cho 100 người đến từ 50 QG, mỗi QG có 2 người xếp thành một vòng tròn. CMR: có thể chia 100 người này thành 2 nhóm, mỗi nhóm có 50 người sao cho không có 2 người nào cùng một QG và không có 2 người nào đứng kề nhau trên vòng tròn

(bạn đọc tự chứng minh)

Trở lại bài toán:

Trong mỗi bộ 4 người ở một QG, ta chia làm 2 tỉnh, mỗi tỉnh có 2 người. Ta có tất cả 50 tỉnh. Theo bổ đề trên thì ta có thể chia 100 người này thành 2 nhóm, mỗi nhóm có 50 người sao cho không có 2 người nào cùng một tỉnh và không có 2 người nào đứng kề nhau trên vòng tròn.

Có thể thấy rằng trong 50 người của nhóm 1 sẽ có 25 cặp có cùng một quốc gia. Ta chia 50 người này thành 2 nhóm sao cho không có 2 người nào cùng một cặp ở chung một nhóm nữa là ok.

Làm tương tự với nhóm 2

Suy ra đpcm

Bài viết đã được chỉnh sửa nội dung bởi lenhathoang1998: 22-08-2013 - 17:25