MathDB

There is a group of more than three airports. For any two airports

A, B

belonging to this group, if there is an aircraft from

A

B

, there is an aircraft from

B

A

. For a list of different airports

A_0,A_1,...A_n

, define this list as a '[color=#00f]route' if there is an aircraft from

A_i

A_{i+1}

for each

i=0,1,...,n-1

. Also, define the beginning of this [color=#00f]route as

A_0

, the end as

A_n

, and the length as

n

. (

n\in \mathbb N

)

Now, let's say that for any three different pairs of airports

(A,B,C)

, there is always a [color=#00f]route

P

that satisfies the following condition.

Condition:

P

begins with

A

and ends with

B

, and does not include

C

When the length of the longest of the existing [color=#00f]routes is

M

(

\ge 2

), prove that any two [color=#00f]routes of length

M

contain at least two different airports simultaneously.

Problem Statement