Problem

Source: Mongolian Mathematical Olympiad P3

Tags: combinatorics, Extremal, graph



Five girls and five boys took part in a competition. Suppose that we can number the boys and girls $1, 2, 3, 4, 5$ such that for each $1 \leq i,j \leq 5$, there are exactly $|i-j|$ contestants that the girl numbered $i$ and the boy numbered $j$ both know. Let $a_i$ and $b_i$ be the number of contestants that the girl numbered $i$ knows and the number of contestants that the boy numbered $i$ knows respectively. Find the minimum value of $\max(\sum\limits_{i=1}^5a_i, \sum\limits_{i=1}^5b_i)$. (Note that for a pair of contestants $A$ and $B$, $A$ knowing $B$ doesn't mean that $B$ knows $A$ and a contestant cannot know themself.)