There are $36$ gangsters bands.And there are war between some bands. Every gangster can belongs to several bands and every 2 gangsters belongs to different set of bands. Gangster can not be in feuding bands. Also for every gangster is true, that every band, where this gangster is not in, is in war with some band, where this gangster is in. What is maximum number of gangsters in city?
Problem
Source: Moscow Math Olympiad 2017, Grade 11, P6
Tags: combinatorics
math90
25.04.2017 20:46
The problem actually asks to find the maximal number of maximal cliques in a graph of $36$ vertices.
For each positive integer $n$, let $a_n$ be the maximal number of maximal cliques in a graph of $n$ vertices.
Let $x$ be a vertex which belongs to a maximal number of gangsters. Let $S$ be the set of $x$'s friends and let $T$ be the set of $x$'s enemies. A maximal clique cannot be contained in $S$, since $x$ is a friend of all of its members. Hence each clique contains a member of $T\cup\{x\}$. For each vertex $v$, let $A_v$ be the set of gangsters which contain $v$. Also, there is a bijection between cliques which contain $x$ and maximal cliques in $S$. Hence
$a_{36}=|\bigcup_{v\in T\cup\{x\}}A_v|\leq\sum_{v\in T\cup\{x\}}|A_v|\leq(|T|+1)A_x\leq(|T|+1)a_{35-|T|}=ka_{36-k}$
where $k=|T|+1$.
Continuing in this manner, we get that $a_{36}\leq\prod_{i=1}^n b_i$, where all $b_i$ are positive integers such that $\sum_{i=1}^n b_i=36$.
So now we have to solve another problem: What is the maximal product of positive integers whose sum is $36$?
If one of the numbers is at least $4$, splitting it into $2+(n-2)$ will yield a larger product.
If one of the numbers is $1$, joining it with another number will yield a larger product.
If we have $3$ appearances of $2$, it's better to replace it with $2$ appearances of $3$.
Hence a maximal product is achieved when all numbers are $2$ or $3$, and at most $2$ of them are $2$. Since $36$ is divisible by $3$, this happens when all numbers are $3$. Hence the maximal product is $3^{12}$.
Construction: Take $12$ sets of $3$, and two people are friends if and only if they are in different sets.
So the answer is $3^{12}$.