Maths Olympiad Prep

Library / /570 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

A nonempty set SS is called well-filled if for every mSm \in S, there are fewer than 12m\frac{1}{2}m elements of SS which are less than mm. Determine the number of well-filled subsets of {1,2,,42}\{1,2, \ldots, 42\}.

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

Solution

Let ana_{n} be the number of well-filled subsets whose maximum element is nn (setting a0=1a_{0}=1). Then it's easy to see that a2k+1=a2k+a2k1++a0a_{2k+1}=a_{2k}+a_{2k-1}+\cdots+a_{0} and a2k+2=(a2k+1Ck)+a2k++a0a_{2k+2}=(a_{2k+1}-C_{k})+a_{2k}+\cdots+a_{0} where CkC_{k} is the number of well-filled subsets of size k+1k+1 with maximal element 2k+12k+1. We proceed to compute CkC_{k}. One can think of such a subset as a sequence of numbers 1s1<<sk+12k+11 \leq s_{1}<\cdots<s_{k+1} \leq 2k+1 such that si2i1s_{i} \geq 2i-1 for every 1ik+11 \leq i \leq k+1. Equivalently, letting si=i+1+tis_{i}=i+1+t_{i} it's the number of sequences 0t1tk+1k+10 \leq t_{1} \leq \cdots \leq t_{k+1} \leq k+1 such that tiit_{i} \geq i for every ii. This gives the list of xx-coordinates of steps up in a Catalan path from (0,0)(0,0) to (k+1,k+1)(k+1, k+1), so Ck=1k+2(2(k+1)(k+1))C_{k}=\frac{1}{k+2}\binom{2(k+1)}{(k+1)} is equal to the (k+1)(k+1)th Catalan number. From this we can solve the above recursion to derive that an=(n(n1)/2)a_{n}=\binom{n}{\lfloor(n-1) / 2\rfloor}. Consequently, for even nn, a0++an=an+1=(n+1n/2)a_{0}+\cdots+a_{n}=a_{n+1}=\binom{n+1}{\lfloor n / 2\rfloor}. Putting n=42n=42 gives the answer, after subtracting off the empty set (counted in a0a_{0}).

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.