In a country every 2 cities are connected either by a direct bus route or a direct plane flight. A $clique$ is a set of cities such that every 2 cities in the set are connected by a direct flight. A $cluque$ 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 $claque$ 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
Problem
Source: Tuymaada 2017 Junior Level
Tags: combinatorics
17.07.2017 19:48
Am I missing something? The following solution seems too easy for Tuymaada P3. We let $C=\{ c_1,c_2,...,c_l\}$ be the set of cities in the largest clique. Consider the multi set $S$ consist of the number of cities connected to city $c_i$ by a bus route for each $i=1,2,...,l$. Suppose $S=\{ n_1\times b_1,n_2\times b_2,...,n_k\times b_k\}$ where $n_1,n_2,...,n_k\in \mathbb{Z}^+$ It's clear that we can select $k$ cities from $C$ to create a claque and we can select $\max_{i=1}^{k} \{ n_i\}$ cities in $C$ to create a cluque. So we want to prove that $k\times \max_{i=1}^{k} \{ n_i\} \geq l$ which is true since $LHS\geq n_1+n_2+...+n_k=l$.
17.07.2017 19:58
ThE-dArK-lOrD wrote: Am I missing something? Maybe, you missing that it is junior level ?
06.09.2020 19:42
Trivial!!!!!