Maths Olympiad Prep

Track / Stage 5 / 198 of 400 #798 of 1964

Problem 798

AIME late
Combinatorics Difficulty 5.5 Find the answer

6. Let n3,bnn \geqslant 3, b_{n} be the number of subsets of the set {1,2,,n}\{1, 2, \cdots, n\} that have the following property: any two elements in these subsets (which must contain at least two elements) have an absolute difference greater than 1. Then the value of b10b_{10} is \qquad

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

Official solution

6. 133

Let Tn,kT_{n, k} be the number of kk-element subsets of {1,2,,n}\{1,2, \cdots, n\} that satisfy the given conditions, denoted as a1a2ak\mid a_{1} a_{2} \cdots a_{k} \mid. For such a kk-element subset, let b1=a1,b2=a21,b3=a32,,bk=ak(k1)b_{1}=a_{1}, b_{2}=a_{2}-1, b_{3}=a_{3}-2, \cdots, b_{k}=a_{k}-(k-1).

We establish a one-to-one mapping {a1a2ak}{b1b2bk}\left\{a_{1} a_{2} \cdots a_{k}\right\} \rightarrow\left\{b_{1} b_{2} \cdots b_{k}\right\}. Since a1a2ak\left|a_{1} a_{2} \cdots a_{k}\right| has the property that {b1b2bk\left\{b_{1} b_{2} \cdots b_{k} \mid\right. is a kk-element subset of {1,2,,nk+1}\{1,2, \cdots, n-k+1\}, and for every kk-element subset of {1,2,,nk+1}\{1,2, \cdots, n-k+1\}, there corresponds a subset {a1a2ak}\left\{a_{1} a_{2} \cdots a_{k}\right\} that meets the requirements, we have Tn,k=Cnk+1kT_{n, k}=C_{n-k+1}^{k}, and bn=k=2[n+12]Cnk+1kb_{n}=\sum_{k=2}^{\left[\frac{n+1}{2}\right]} C_{n-k+1}^{k}.

Therefore, b10=k=25C11kk=C92+C83+C74+C65=133b_{10}=\sum_{k=2}^{5} C_{11-k}^{k}=C_{9}^{2}+C_{8}^{3}+C_{7}^{4}+C_{6}^{5}=133.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.