Maths Olympiad Prep

Library / /235 of 377

Combinatorics Difficulty 5.2 AIME, harder Prove it United States

Problem:
Let Bk(n)B_{k}(n) be the largest possible number of elements in a 2-separable kk-configuration of a set with 2n2n elements (2kn2 \leq k \leq n). Find a closed-form expression (i.e. an expression not involving any sums or products with a variable number of terms) for Bk(n)B_{k}(n).

Solution

Solution:
First, a lemma: For any aa with 0a2n0 \leq a \leq 2n, (ak)+(2nak)2(nk)\binom{a}{k} + \binom{2n-a}{k} \geq 2\binom{n}{k}. (By convention, we set (ak)=0\binom{a}{k} = 0 when a<ka < k.)

Proof: We may assume ana \geq n, since otherwise we can replace aa with 2na2n-a. Now we prove the result by induction on aa. For the base case, if a=na = n, then the lemma states that 2(nk)2(nk)2\binom{n}{k} \geq 2\binom{n}{k}, which is trivial. If the lemma holds for some a>0a > 0, then by the familiar identity,
[(a+1k)+(2na1k)][(ak)+(2nak)]= [(a+1k)(ak)][(2nak)(2na1k)]= (ak1)(2na1k1)>0 \begin{aligned} & \left[\binom{a+1}{k} + \binom{2n-a-1}{k}\right] - \left[\binom{a}{k} + \binom{2n-a}{k}\right] \\ =\ & \left[\binom{a+1}{k} - \binom{a}{k}\right] - \left[\binom{2n-a}{k} - \binom{2n-a-1}{k}\right] \\ =\ & \binom{a}{k-1} - \binom{2n-a-1}{k-1} > 0 \end{aligned}
(since a>2na1a > 2n-a-1), so (a+1k)+(2na1k)>(ak)+(2nak)2(nk)\binom{a+1}{k} + \binom{2n-a-1}{k} > \binom{a}{k} + \binom{2n-a}{k} \geq 2\binom{n}{k}, giving the induction step. The lemma follows.

Now suppose that the elements of AA are labeled such that aa elements of the set AA receive the number 1 and 2na2n-a elements receive the number 2. Then the kk-configuration can include all kk-element subsets of AA except those contained among the aa elements numbered 1 or the 2na2n-a elements numbered 2. Thus, we have at most (2nk)(ak)(2nak)\binom{2n}{k} - \binom{a}{k} - \binom{2n-a}{k} elements in the kk-configuration, and by the lemma, this is at most
(2nk)2(nk) \binom{2n}{k} - 2\binom{n}{k}
On the other hand, we can achieve (2nk)2(nk)\binom{2n}{k} - 2\binom{n}{k} via the recipe above—take all the kk-element subsets of AA, except those contained entirely within the first nn elements or entirely within the last nn elements. Then, labeling the first nn elements with the number 1 and the last nn elements with the number 2 shows that the configuration is 2-separable. So,
Bk(n)=(2nk)2(nk) B_{k}(n) = \binom{2n}{k} - 2\binom{n}{k}

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.