In a country, there are $28$ cities and between some cities there are two-way flights. In every city there is exactly one airport and this airport is either small or medium or big. For every route which contains more than two cities, doesn't contain a city twice and ends where it begins; has all types of airports. What is the maximum number of flights in this country?
Problem
Source: 2021 Turkey JBMO TST P3
Tags: combinatorics, combinatorics proposed
Marinchoo
09.06.2021 07:54
Divide the set into two groups - one subgraph of the big cities and the other - all the small cities. Now if we call those sets $A$ and $B$ respectively, then $A$ must be a collection of trees. Therefore there are no more than $|A|-1$ segments in $A$. Anallogically for $B$. Obviously there are no more than $|A|\times |B|$ flights from a small to a big city. So there are no more than $$|A|.|B|+|A|-1+|B|-1=x(28-x)+26\leq \boxed{222} $$segments in this graph. An example of a graph that satisfies this upper bound is easy to construct: Take 14 big cities, say $x_{1}, \dots, x_{14}$ and draw the segments $x_{i} x_{i+1}$, do the same for the 14 small cities and draw every segment between a small and a big city. This problem is very easy for a P3 in my opinion.
roughlife
15.12.2021 15:00
The Answer is $53$
In graph translation, let $M$ be the maximum number of edges in $G=(V,E)$
1) $M \le 53$
Each vertex is partitioned to subset $B$,$M$,$S$. By the condition, The number of edges in subgraph consists of $B \cup M$ is at most $|B \cup M|-1$. So we obtain the folloing results : $|E| \le 2 \times 28-3-(e_{B}+e_{M}+e_{S})$, where definition of $e_{B}$ is the number of edges between vertices in $B$
2) $M \ge 53$
The construction follows : $|B|=|M|=9, |S|=10$, any union set of two substets has a Tree which is bipartite graph with them. For exmaple, $s_{1}-b_{1}- \cdots -s_{10}$