Question 181
There are $M$ countries and $N$ towns on a planet. Some of the towns are connected by roads. It is known that:
(1) there are at least three towns in any country;
(2) any town in a country is connected by roads with at least half of the towns in this country;
(3) any town is connected with road to exactly one town in another country;
(4) there are at most two roads between towns in two countries;
(5) if in two countries there are less than $2M$ towns then there exists at least one road between these countries.
Prove that there exists a round trip having at least $M + \frac{N}{2}$ towns.
(1) there are at least three towns in any country;
(2) any town in a country is connected by roads with at least half of the towns in this country;
(3) any town is connected with road to exactly one town in another country;
(4) there are at most two roads between towns in two countries;
(5) if in two countries there are less than $2M$ towns then there exists at least one road between these countries.
Prove that there exists a round trip having at least $M + \frac{N}{2}$ towns.