Maths Olympiad Prep

Library / /22 of 22

Combinatorics Difficulty 9.2 IMO level Prove it United States

A social club has 2k+12k + 1 members, each of whom is fluent in the same kk 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 AA be the number of three-member subsets such that the three distinct pairs among them use different languages. Find the maximum possible value of AA.

Solution

The answer is (2k+13)k(2k+1)\binom{2k+1}{3} - k(2k+1), or 2k(k2)(2k+1)3\frac{2k(k-2)(2k+1)}{3}.

We will treat the social club as a complete graph on 2k+12k+1 vertices, where each language corresponds to one color of edge between pairs of vertices. Let V={v1,,v2k+1}V = \{v_1, \dots, v_{2k+1}\} be the set of vertices, L={l1,,lk}L = \{l_1, \dots, l_k\} be the set of languages or colors, and let degi(v)\deg_i(v) correspond to the number of edges of color lil_i out of vertex vv.

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 vv is equal to (deg1(v)2)++(degk(v)2)\binom{\deg_1(v)}{2} + \dots + \binom{\deg_k(v)}{2}. By Cauchy's inequality, we have
(deg1(v)2)++(degk(v)2)=12i=1k(degi(v))212i=1kdegi(v)12(112++12)(1deg1(v)++1degk(v))2=k. \begin{aligned} \binom{\deg_1(v)}{2} + \dots + \binom{\deg_k(v)}{2} &= \frac{1}{2} \sum_{i=1}^{k} (\deg_i(v))^2 - \frac{1}{2} \sum_{i=1}^{k} \deg_i(v) \\ &\geq \frac{1}{2} \left( \frac{1}{1^2 + \dots + 1^2} \right) (1 \cdot \deg_1(v) + \dots + 1 \cdot \deg_k(v))^2 \\ &= k. \end{aligned}

Summing over all vertices, we obtain that there are at least
vVi=1k(degi(v)2)vVk=k(2k+1) \sum_{v \in V} \sum_{i=1}^{k} \binom{\deg_i(v)}{2} \geq \sum_{v \in V} k = k(2k+1)
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 AA such triangles). Therefore, we conclude that
A(2k+13)k(2k+1). A \leq \binom{2k+1}{3} - k(2k+1).

Now, we give a construction for A=(2k+13)k(2k+1)A = \binom{2k+1}{3} - k(2k+1). We note that equality holds in the inequality above when degi(v)=2\deg_i(v) = 2 for all ii and vv. Thus, it suffices to show that any complete graph on 2n+12n+1 vertices can be decomposed into kk disjoint Hamiltonian cycles, since we can then assign one color to each cycle.

For this, start with the cycle C0=(v0,v1,v2k,v2,v2k1,v3,v2k2,,vk,vk+1,v0)C_0 = (v_0, v_1, v_{2k}, v_2, v_{2k-1}, v_3, v_{2k-2}, \dots, v_k, vk+1, v_0) constructed by starting at v0v_0 and alternately going to vertices in the two lists v1,v2,,vkv_1, v_2, \dots, v_k and v2k,v2k1,,vk+1v_{2k}, v_{2k-1}, \dots, v_{k+1}. Then, construct the cycles C1,,Ck1C_1, \dots, C_{k-1} so that cycle CiC_i is constructed by adding ii to the subscript of each vertex in C0C_0 (where we set vi=vi+2k+1v_i = v_{i+2k+1}). If we look at the set of edges (vi,vi+n)(v_i, v_{i+n}) for 1n<k1 \le n < k, we note that exactly two occur in each CiC_i and that each ii occurs as the first vertex index exactly once, so these cycles are disjoint, completing the construction. (More precisely, for even nn this edge occurs at (vn/2,vn/2)(v_{-n/2}, v_{n/2}) and (vk+1n/2,vk+1+n/2)(v_{k+1-n/2}, v_{k+1+n/2}) in C0C_0, and consequently the edge (vi,vi+n)(v_i, v_{i+n}) occurs in one of Ci+n2C_{i+\frac{n}{2}}, Ci+n2k1C_{i+\frac{n}{2}-k-1}, or Ci+n2(2k+1)C_{i+\frac{n}{2}-(2k+1)}, depending on which of these subscripts lies in [0,k1][0, k-1]. A similar argument holds for odd nn.)

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.