, 2014

Solution:

Answer: $\frac{n(n+1)}{2}$

We represent the problem as a graph with vertices $G_{1}, \ldots, G_{n}, B_{1}, \ldots, B_{n}$ such that there is an edge between vertices $G_{i}$ and $B_{j}$ if and only if $(G_{i}, B_{j})$ is suitable, so we want to maximize the number of edges while having a unique matching.

We claim the answer is $\frac{n(n+1)}{2}$. First, note that this can be achieved by having an edge between $G_{i}$ and $B_{j}$ for all pairs $j \leq i$, because the only possible matching in this case is pairing $G_{i}$ with $B_{i}$ for all $i$.

To prove that this is maximal, we first assume without loss of generality that our unique matching consists of pairing $G_{i}$ with $B_{i}$ for all $i$, which takes $n$ edges. Now, note that for any $i, j$, at most one of the two edges $G_{i} B_{j}$ and $G_{j} B_{i}$ can be added, because if both were added, we could pair $G_{i}$ with $B_{j}$ and $G_{j}$ with $B_{i}$ instead to get another valid matching. Therefore, we may add at most $\binom{n}{2} \cdot 1 = \frac{n(n-1)}{2}$ edges, so the maximal number of edges is $n + \frac{n(n-1)}{2} = \frac{n(n+1)}{2}$ as desired.