MathDB

There are

k

cities in Belarus and

k

cities in Armenia, between some cities there are non-directed flights. From any Belarusian city there are exactly

n

flights to Armenian cities, and for every pair of Armenian cities exactly two Belarusian cities have flights to both of the Armenian cities. a) Prove that from every Armenian city there are exactly

n

flights to Belarusian cities. b) Prove that there exists a flight route in which every city is visited at most once and that consists of at least

\lfloor \frac{(n+1)^2}{4} \rfloor

cities in both countries. D. Gorovoy

Problem Statement