The number of ways to choose 7 distinct natural numbers from the set of first 100 natural numbers such that any two chosen numbers differ at least by 7 can be expressed as ${n \choose 7}$. Find the value of $n.$
My attempt: According to me we have to select any of the $7$ numbers of our choice, so $n = 100$.
Best Answer
If $n$ were to be $100$, one would be able to pick $1$ and $2$, which do not match the condition that the numbers must differ at least by $7$. In fact, this problem comes down to a stars-and-bars problem, where the bars are the indices of the numbers chosen, and at least $6$ numbers must be in between each bar. If we select $7$ numbers, $7$ places must be reserved for the bars and an additional $(7-1) (7-1) = 36$ places must be reserved for the intermediate numbers. This leaves $100 - 43 = 57$ free places which need to be distributed among the $8$ slots, and the total number of valid combinations thus equals:
$${57 + 8 - 1 \choose 8 - 1} = {64 \choose 7}$$