CombinatoricsDifficulty 5.3AIME, harderFind the answer
Let A1,A2,…,Am be finite sets of size 2012 and let B1,B2,…,Bm be finite sets of size 2013 such that Ai∩Bj=∅ if and only if i=j. Find the maximum value of m.
A number or a short expression. Spacing and $ signs are ignored.
Solution
In general, we will show that if each of the sets Ai contain a elements and if each of the sets Bj contain b elements, then the maximum value for m is (aa+b). Let U denote the union of all the sets Ai and Bj and let ∣U∣=n. Consider the n ! orderings of the elements of U. Note that for any specific ordering, there is at most one value of i such that all the elements in Ai come before all the elements in Bi in this ordering; this follows since Aj shares at least one element with Bi and Bj shares at least one element with Ai for any other j=i. On the other hand, the number of ways to permute the (a+b) elements in Ai∪Bi so that all the elements in Ai come first is equal to a!b!. Therefore, the number of permutations of U where all the elements in Ai come before all the elements in Bi is equal to: n!⋅(a+b)!a!b!=(aa+b)n! Summing over all m values of i, the total number of orderings where, for some i, the elements in Ai come before Bi is equal to (aa+b)n!m But there are at most u ! such orderings, since there are u ! total orderings, so it follows that m≤(aa+b). Equality is attained by taking U to be a set containing (a+b) elements, letting Ai range over all a-element subsets of U, and letting Bi=U\Ai for each i.
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.