Difference between revisions of "2007 AMC 12A Problems/Problem 25"

Revision as of 22:38, 18 February 2012

Problem

Call a set of integers spacy if it contains no more than one out of any three consecutive integers. How many subsets of $\{1,2,3,\ldots,12\},$ including the empty set, are spacy?

$\mathrm{(A)}\ 121 \qquad \mathrm{(B)}\ 123 \qquad \mathrm{(C)}\ 125 \qquad \mathrm{(D)}\ 127 \qquad \mathrm{(E)}\ 129$

Solution

Solution 1

Let $S_{n}$ denote the number of spacy subsets of $\{ 1, 2, ... n \}$ . We have $S_{0} = 1, S_{1} = 2, S_{2} = 3$ .

The spacy subsets of $S_{n + 1}$ can be divided into two groups:

$A =$ those not containing $n + 1$ . Clearly $|A|=S_{n}$ .
$B =$ those containing $n + 1$ . We have $|B|=S_{n - 2}$ , since removing $n + 1$ from any set in $B$ produces a spacy set with all elements at most equal to $n - 2,$ and each such spacy set can be constructed from exactly one spacy set in $B$ .

Hence,

$S_{n + 1} = S_{n} + S_{n - 2}$

From this recursion, we find that

$S(0)$	$S(1)$	$S(2)$	$S(3)$	$S(4)$	$S(5)$	$S(6)$	$S(7)$	$S(8)$	$S(9)$	$S(10)$	$S(11)$	$S(12)$
1	2	3	4	6	9	13	19	28	41	60	88	129

Solution 2

Since each of the elements of the subsets must be spaced at least two apart, a divider counting argument can be used.

From the set $\{1,2,3,4,5,6,7,8,9,10,11,12\}$ we choose at most four numbers. Let those numbers be represented by balls. Between each of the balls there are at least two dividers. So for example, o | | o | | o | | o | | represents ${1,4,7,10}$ .

For subsets of size $k$ there must be $2(k - 1)$ dividers between the balls, leaving $12 - k - 2(k - 1) = 12 - 3k + 2$ dividers to be be placed in $k + 1$ spots between the balls. The number of way this can be done is $\binom{(12 - 3k + 2) + (k + 1) - 1}k = \binom{12 - 2k + 2}k$ .

Therefore, the number of spacy subsets is $\binom 64 + \binom 83 + \binom{10}2 + \binom{12}1 + \binom{14}0 = 129$ .

Solution 3

A shifting argument is also possible, and is similiar in spirit to Solution 2. Clearly we can have at most $4$ elements. Given any arrangment, we subract $2i-2$ from the $i-th$ element in our subset, when the elements are arranged in increasing order. This creates a bijection with the number of size $k$ subsets of the set of the first $14-2k$ positive integers. For instance, the arrangment o | | o | | o | | | o | corresponds to the arrangment o o o | o |. Notice that there is no longer any restriction on consectutive numbers. Therefore, we can easily plug in the possible integers 0, 1, 2, 3, 4, 5 for $k$ : ${14 \choose 0} + {12 \choose 1} + {10 \choose 2} + {8 \choose 3} + {6 \choose 4} = \boxed{129}$

In general, the number of subsets of size $n$ with no $k$ consecutive numbers is $\sum^{\floor{\frac{n}{k}}}_{i=0}{{(k-1)(i-1) \choose i}}$ (Error compiling LaTeX. Unknown error_msg).

Solution 4

As a last resort, we can brute force the result by repeated casework. Luckily, 12 is not a very large number, so solving it this way is still possible.

@@ Line 34: / Line 34: @@
 Therefore, the number of spacy subsets is <math>\binom 64 + \binom 83 + \binom{10}2 + \binom{12}1 + \binom{14}0 = 129</math>.
+=== Solution 3 ===
+A shifting argument is also possible, and is similiar in spirit to Solution 2. Clearly we can have at most <math>4</math> elements. Given any arrangment, we subract <math>2i-2</math> from the <math>i-th</math> element in our subset, when the elements are arranged in increasing order. This creates a [[bijection]] with the number of size <math>k</math> subsets of the set of the first <math>14-2k</math> positive integers. For instance, the arrangment o | | o | | o | | | o | corresponds to the arrangment o o o | o |. Notice that there is no longer any restriction on consectutive numbers. Therefore, we can easily plug in the possible integers 0, 1, 2, 3, 4, 5 for <math>k</math>: <math>{14 \choose 0} + {12 \choose 1} + {10 \choose 2} + {8 \choose 3} + {6 \choose 4} = \boxed{129}</math>
-=== Solution 3 ===
+In general, the number of subsets of size <math>n</math> with no <math>k</math> consecutive numbers is <math>\sum^{\floor{\frac{n}{k}}}_{i=0}{{(k-1)(i-1) \choose i}}</math>.
+=== Solution 4 ===
 As a last resort, we can [[brute force]] the result by repeated [[casework]]. Luckily, 12 is not a very large number, so solving it this way is still possible.

2007 AMC 12A (Problems • Answer Key • Resources)
Preceded by Problem 24	Followed by Last question
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

Page

Toolbox

Search