Câu hỏi 181
Trên một hành tinh có $M$ quốc gia và $N$ thị trấn. Một số thị trấn được nối với nhau bởi các con đường. Biết rằng:
(1) mỗi quốc gia có ít nhất ba thị trấn;
(2) mỗi thị trấn trong một quốc gia được nối bằng đường với ít nhất một nửa số thị trấn của quốc gia đó;
(3) mỗi thị trấn được nối bằng đường với đúng một thị trấn ở quốc gia khác;
(4) giữa các thị trấn của hai quốc gia có nhiều nhất hai con đường;
(5) nếu hai quốc gia có tổng cộng ít hơn $2M$ thị trấn thì có ít nhất một con đường nối hai quốc gia này.
Chứng minh rằng tồn tại một hành trình khép kín đi qua ít nhất $M + \frac{N}{2}$ thị trấn.
(1) mỗi quốc gia có ít nhất ba thị trấn;
(2) mỗi thị trấn trong một quốc gia được nối bằng đường với ít nhất một nửa số thị trấn của quốc gia đó;
(3) mỗi thị trấn được nối bằng đường với đúng một thị trấn ở quốc gia khác;
(4) giữa các thị trấn của hai quốc gia có nhiều nhất hai con đường;
(5) nếu hai quốc gia có tổng cộng ít hơn $2M$ thị trấn thì có ít nhất một con đường nối hai quốc gia này.
Chứng minh rằng tồn tại một hành trình khép kín đi qua ít nhất $M + \frac{N}{2}$ thị trấn.