MathDB
Problems
Contests
International Contests
Tuymaada Olympiad
2017 Tuymaada Olympiad
3
3
Part of
2017 Tuymaada Olympiad
Problems
(1)
Clique, cluque, claque
Source: Tuymaada 2017 Junior Level
7/17/2017
In a country every 2 cities are connected either by a direct bus route or a direct plane flight. A
c
l
i
q
u
e
clique
c
l
i
q
u
e
is a set of cities such that every 2 cities in the set are connected by a direct flight. A
c
l
u
q
u
e
cluque
c
l
u
q
u
e
is a set of cities such that every 2 cities in the set are connected by a direct flight, and every 2 cities in the set are connected to the same number of cities by a bus route. A
c
l
a
q
u
e
claque
c
l
a
q
u
e
is a set of cities such that every 2 cities in the set are connected by a direct flight, and every 2 numbers of bus routes from a city in the set are different. Prove that the number of cities of any clique is at most the product of the biggest possible number of cities in a cluque and the the biggest possible number of cities in a claque.Tuymaada 2017 Q3 Juniors
combinatorics