A social club has members, each of whom is fluent in the same languages. Any pair of members always talk to each other in only one language. Suppose that there were no three members such that they use only one language among them. Let be the number of three-member subsets such that the three distinct pairs among them use different languages. Find the maximum possible value of .
Solution
The answer is , or .
We will treat the social club as a complete graph on vertices, where each language corresponds to one color of edge between pairs of vertices. Let be the set of vertices, be the set of languages or colors, and let correspond to the number of edges of color out of vertex .
First, we show that this is the maximum. Call a triangle in the graph of members isosceles if two of its edges are the same color. We can count the number of isosceles triangle by looking at the vertex shared by the two edge of the same color, so that the number of isosceles triangles at a vertex is equal to . By Cauchy's inequality, we have
Summing over all vertices, we obtain that there are at least
isosceles triangles. By the conditions of the problem, there does not exist a monochromatic triangle; consequently, every triangle is either isosceles or has edges of three different colors (of which there are such triangles). Therefore, we conclude that
Now, we give a construction for . We note that equality holds in the inequality above when for all and . Thus, it suffices to show that any complete graph on vertices can be decomposed into disjoint Hamiltonian cycles, since we can then assign one color to each cycle.
For this, start with the cycle constructed by starting at and alternately going to vertices in the two lists and . Then, construct the cycles so that cycle is constructed by adding to the subscript of each vertex in (where we set ). If we look at the set of edges for , we note that exactly two occur in each and that each occurs as the first vertex index exactly once, so these cycles are disjoint, completing the construction. (More precisely, for even this edge occurs at and in , and consequently the edge occurs in one of , , or , depending on which of these subscripts lies in . A similar argument holds for odd .)