Câu hỏi 154
Một thành phố có $M$ con đường và $N$ quảng trường, trong đó $M$ và $N$ là các số nguyên dương với $M \gt N$. Mỗi con đường nối hai quảng trường và không đi qua quảng trường nào khác.
Người dân muốn thay đổi diện mạo thành phố. Năm nay, mỗi con đường sẽ được tô màu lần đầu tiên, bằng màu đỏ hoặc màu xanh. Người ta cũng quy định rằng mỗi năm tiếp theo sẽ chọn một quảng trường và tất cả các con đường dẫn tới quảng trường đó đồng thời đổi màu từ xanh sang đỏ và ngược lại.
Chứng minh rằng người dân có thể chọn màu ban đầu cho các con đường sao cho không bao giờ xảy ra trường hợp tất cả các con đường cùng một màu.
(Russia 1994)
Người dân muốn thay đổi diện mạo thành phố. Năm nay, mỗi con đường sẽ được tô màu lần đầu tiên, bằng màu đỏ hoặc màu xanh. Người ta cũng quy định rằng mỗi năm tiếp theo sẽ chọn một quảng trường và tất cả các con đường dẫn tới quảng trường đó đồng thời đổi màu từ xanh sang đỏ và ngược lại.
Chứng minh rằng người dân có thể chọn màu ban đầu cho các con đường sao cho không bao giờ xảy ra trường hợp tất cả các con đường cùng một màu.
(Russia 1994)