2009 AIME II Problems/Problem 6
Problem
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
.
Solution
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
.
See Also
2009 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 5 |
Followed by Problem 7 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.