2009 AIME II Problems/Problem 6
Let be the number of five-element subsets that can be chosen from the set of the first natural numbers so that at least two of the five numbers are consecutive. Find the remainder when is divided by .
We can use complementary counting. We can choose a five-element subset in ways. We will now count those where no two numbers are consecutive. We will show a bijection between this set, and the set of 10-element strings that contain 5 s and 5 s, thereby showing that there are such sets.
Given a five-element subset of in which no two numbers are consecutive, we can start by writing down a string of length 14, in which the -th character is if and otherwise. Now we got a string with 5 s and 9 s. As no two numbers were consecutive, we know that in our string no two s are consecutive. We can now remove exactly one from between each pair of s to get a string with 5 s and 5 s. And clearly this is a bijection, as from each string with 5 s and 5 s we can reconstruct one original set by reversing the construction.
Hence we have , and the answer is .
Let be the number of ways in which distinct numbers can be selected from the set of the first natural numbers, and let be the number of ways in which distinct numbers, no two of which are consecutive, can be selected from the same set. Then . Because , the problem is reduced to finding . Consider the natural numbers . If no two of them are consecutive, the numbers , , , and are distinct numbers from the interval . Conversely, if are distinct natural numbers from the interval , then , , , , and are from the interval , and no two of them are consecutive. Therefore counting is the same as counting the number of ways of choosing distinct numbers from the set of the first natural numbers. Thus . Hence and the answer is .
|2009 AIME II (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|