Difference between revisions of "2009 AIME II Problems/Problem 6"
(→Solution 2) |
Mathgeek2006 (talk | contribs) m (→Solution 2) |
||
Line 12: | Line 12: | ||
== Solution 2 == | == Solution 2 == | ||
− | Let A be the number of ways in which 5 distinct numbers can be selected | + | Let <math>A</math> be the number of ways in which <math>5</math> distinct numbers can be selected |
− | from the set of the first 14 natural numbers, and let B be the number of | + | from the set of the first <math>14</math> natural numbers, and let <math>B</math> be the number of |
− | ways in which 5 distinct numbers, no two of which are consecutive, can | + | ways in which <math>5</math> distinct numbers, no two of which are consecutive, can |
− | be selected from the same set. Then m = A | + | be selected from the same set. Then <math>m = A -B</math>. Because <math>A = \dbinom{14}{5}</math>, the |
− | problem is reduced to finding B. | + | problem is reduced to finding <math>B</math>. |
Consider the natural numbers <math>1 \leq a_1 < a_2 < a_3 < a_4 < a_5 \leq 14</math>. If no | Consider the natural numbers <math>1 \leq a_1 < a_2 < a_3 < a_4 < a_5 \leq 14</math>. If no | ||
two of them are consecutive, the numbers <math>b_1 = a_1, b_2 = a_2 - 1</math>, <math>b_3 = a_3 - 2</math>, | two of them are consecutive, the numbers <math>b_1 = a_1, b_2 = a_2 - 1</math>, <math>b_3 = a_3 - 2</math>, | ||
− | <math>b_4 = a_4 - 3</math>, and <math>b_5 = a_5 - 4</math> are distinct numbers from the interval [1, 10]. | + | <math>b_4 = a_4 - 3</math>, and <math>b_5 = a_5 - 4</math> are distinct numbers from the interval <math>[1, 10]</math>. |
Conversely, if <math>b_1 < b_2 < b_3 < b_4 < b_5</math> are distinct natural numbers from | Conversely, if <math>b_1 < b_2 < b_3 < b_4 < b_5</math> are distinct natural numbers from | ||
− | the interval [1, 10], then <math>a_1 = b_1</math>, <math>a_2 = b_2 + 1</math>, <math>a_3 = b_3 + 2</math>, <math>a_4 = b_4 + 3</math>, and | + | the interval <math>[1, 10]</math>, then <math>a_1 = b_1</math>, <math>a_2 = b_2 + 1</math>, <math>a_3 = b_3 + 2</math>, <math>a_4 = b_4 + 3</math>, and |
− | <math>a_5 = b_5 + 4</math> are from the interval [1, 14], and no two of them are consecutive. | + | <math>a_5 = b_5 + 4</math> are from the interval <math>[1, 14]</math>, and no two of them are consecutive. |
− | Therefore counting B is the same as counting the number of ways of | + | Therefore counting <math>B</math> is the same as counting the number of ways of |
− | choosing 5 distinct numbers from the set of the first 10 natural numbers. | + | choosing <math>5</math> distinct numbers from the set of the first <math>10</math> natural numbers. |
− | Thus | + | Thus <math>B = \dbinom{10}{5}</math>. Hence <math>m = A - B = \dbinom{14}{5} - \dbinom{10}{5} |
= 2002 - 252 = 1750</math> and | = 2002 - 252 = 1750</math> and | ||
the answer is <math>750</math>. | the answer is <math>750</math>. |
Revision as of 20:16, 13 March 2015
Contents
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 .
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.