CombinatoricsDifficulty 5.3AIME, harderFind the answer
A nonempty set S is called well-filled if for every m∈S, there are fewer than 21m elements of S which are less than m. Determine the number of well-filled subsets of {1,2,…,42}.
A number or a short expression. Spacing and $ signs are ignored.
Solution
Let an be the number of well-filled subsets whose maximum element is n (setting a0=1). Then it's easy to see that a2k+1=a2k+a2k−1+⋯+a0 and a2k+2=(a2k+1−Ck)+a2k+⋯+a0 where Ck is the number of well-filled subsets of size k+1 with maximal element 2k+1. We proceed to compute Ck. One can think of such a subset as a sequence of numbers 1≤s1<⋯<sk+1≤2k+1 such that si≥2i−1 for every 1≤i≤k+1. Equivalently, letting si=i+1+ti it's the number of sequences 0≤t1≤⋯≤tk+1≤k+1 such that ti≥i for every i. This gives the list of x-coordinates of steps up in a Catalan path from (0,0) to (k+1,k+1), so Ck=k+21((k+1)2(k+1)) is equal to the (k+1)th Catalan number. From this we can solve the above recursion to derive that an=(⌊(n−1)/2⌋n). Consequently, for even n, a0+⋯+an=an+1=(⌊n/2⌋n+1). Putting n=42 gives the answer, after subtracting off the empty set (counted in a0).
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.