Maths Olympiad Prep

Library / /634 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

Let A1,A2,,AmA_{1}, A_{2}, \ldots, A_{m} be finite sets of size 2012 and let B1,B2,,BmB_{1}, B_{2}, \ldots, B_{m} be finite sets of size 2013 such that AiBj=A_{i} \cap B_{j}=\emptyset if and only if i=ji=j. Find the maximum value of mm.

A number or a short expression. Spacing and $ signs are ignored.

Solution

In general, we will show that if each of the sets AiA_{i} contain aa elements and if each of the sets BjB_{j} contain bb elements, then the maximum value for mm is (a+ba)\binom{a+b}{a}. Let UU denote the union of all the sets AiA_{i} and BjB_{j} and let U=n|U|=n. Consider the nn ! orderings of the elements of UU. Note that for any specific ordering, there is at most one value of ii such that all the elements in AiA_{i} come before all the elements in BiB_{i} in this ordering; this follows since AjA_{j} shares at least one element with BiB_{i} and BjB_{j} shares at least one element with AiA_{i} for any other jij \neq i. On the other hand, the number of ways to permute the (a+b)(a+b) elements in AiBiA_{i} \cup B_{i} so that all the elements in AiA_{i} come first is equal to a!b!a!b!. Therefore, the number of permutations of UU where all the elements in AiA_{i} come before all the elements in BiB_{i} is equal to: n!a!b!(a+b)!=n!(a+ba)n!\cdot \frac{a!b!}{(a+b)!}=\frac{n!}{\binom{a+b}{a}} Summing over all mm values of ii, the total number of orderings where, for some ii, the elements in AiA_{i} come before BiB_{i} is equal to n!m(a+ba)\frac{n!m}{\binom{a+b}{a}} But there are at most uu ! such orderings, since there are uu ! total orderings, so it follows that m(a+ba)m \leq\binom{ a+b}{a}. Equality is attained by taking UU to be a set containing (a+b)(a+b) elements, letting AiA_{i} range over all aa-element subsets of UU, and letting Bi=U\AiB_{i}=U \backslash A_{i} for each ii.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.