[ Official answer by CMI]
Model this as a graph problem, we are looking for a graph without a triangle. We show that the maximum number of edges that a triangle-free graph on 2n vertices can have is n 2 . The proof by induction on n. The base cases n = 1, 2 are easy to see by inspection. For the inductive step, let n ≥ 3. If the graph G has no edges then there is nothing to prove. Otherwise, take an edge {x, y}, and consider the graph G0 on 2(n − 1) vertices obtained by deleting both the vertices {x, y} from G. By the inductive hypothesis, G0 has at most (n − 1)2 edges. Since graph G is trianglefree and {x, y} is an edge in G, there is no vertex v in G0 such that both {v, x} and {v, y} are edges in G. So the number of edges with one end-point in the set {x, y} and the other in the set of vertices of G0 is at most the number of vertices in G0 , namely 2(n − 1). Now the set of edges of G consists of (i) all the edges in G0 , plus (ii) the one edge {x, y}, plus (iii) the at most 2(n − 1) edges with exactly one end-point in {x, y}. So the number of edges of G is at most (n − 1)2 + 1 + 2(n − 1) ≤ n 2 .