Bariz - Problem

Source:

Tags: geometry, geometric transformation, combinatorics proposed, combinatorics

WakeUp

01.11.2010 21:59

Some of the $n + 1$ cities in a country (including the capital city) are connected by one-way or two-way airlines. No two cities are connected by both a one-way airline and a two-way airline, but there may be more than one two-way airline between two cities. If $d_A$ denotes the number of airlines from a city $A$, then $d_A \le n$ for any city $A$ other than the capital city and $d_A + d_B \le n$ for any two cities $A$ and $B$ other than the capital city which are not connected by a two-way airline. Every airline has a return, possibly consisting of several connected flights. Find the largest possible number of two-way airlines and all configurations of airlines for which this largest number is attained.

I think below translation is more accurate. There are round trips (flights in both directions) between some of the $n + 1$ cities (including the capital city) in a country. A round trip $A$ and $B$ is a flight pair from $A$ to $B$ and from $B$ to $A$ within the day. There is no non-round trip (one way) flights between any two cities. There may be more than one round trip within the day. Let $d_A$ denotes the number of planes departed from the city $A$. For each city $A$ except the capital, we have $d_A \leq n$, and again any two cities $A$ and $B$ other than the capital city, we have $d_A +d_B \leq n$. There is no restriction about the number of flights from the capital city within the day. In this country, determine the maximum number of round trip flights in a day. Find all flight tables that make possible this maximal number of round trip flights.