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
.
Solution 2
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
.
Solution 3
We will approach this problem using complementary counting. First it is obvious, there are total sets. To find the number of sets with NO consecutive elements, we do a little experimentation. Consider the following:
Start of with any of the numbers, say WLOG,
. Then we cannot have
. So again WLOG, we may pick
. Then we cannot have
, so again WLOG, we may pick
. Then not
, but
, then not
, but
. Now we have the set
, and we had to remove
digits from the
total amount, so there wasn't any consecutive numbers. So we have that the number of non-consecutive cardinality
sets, is
. Now you already read the solutions above, and if you are here, you are either confused, or looking for more. So now the answer is simply
, which is
(
).
~th1nq3r
(To get a feel for my solution, draw the set ${_,_,_,_,_,}$ (Error compiling LaTeX. Unknown error_msg), list all the numbers on the side, and fill up the set starting with
and doing the steps I used for my solution).
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.