2007 AMC 12A Problems/Problem 25

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 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

And so the answer is $(E)$ $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 = \boxed{129}$ .

Solution 3

A shifting argument is also possible, and is similar 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 a set with $n$ elements and with no $k$ consecutive numbers is $\sum^{\lceil{\frac{n}{k}}\rceil}_{i=0}{{n-(k-1)(i-1) \choose i}}$ .

Solution 4 (Casework)

Let us consider each size of subset individually. Since each integer in the subset must be at least $3$ away from any other integer in the subset, the largest spacy subset contains $4$ elements.

First, it is clear that there is $1$ spacy set with $0$ elements in it, the empty set. Next, there are $12$ spacy subsets with $1$ element in them, one for each integer $1$ through $12$ .

Now, let us consider the spacy subsets with $2$ elements in them. If the smaller integer is $1$ , the larger integer is any of the $9$ integers from $4$ to $12$ . If the smaller integer is $2$ , the larger integer is any of the $8$ integers from $5$ to $12$ . This continues, up to a smaller integer of $9$ and $1$ choice for the larger integer, $12$ . This means that there are $9 + 8 + \cdots + 1 = 45$ spacy subsets with $2$ elements.

For spacy subsets with $3$ elements, we first consider the middle integer. The smallest such integer is $4$ , and it allows for $1$ possible value for the smaller integer ( $1$ ) and possible $6$ values for the larger integer ( $7$ through $12$ ), for a total of $1 \cdot 6 = 6$ possible subsets. The next middle integer, $5$ , allows for $2$ smaller integers and $5$ larger integers, and this pattern continues up until the middle integer of $9$ , which has $6$ values for the smaller integer and $1$ value for the larger integer. This means that there are $1 \cdot 6 + 2 \cdot 5 + \cdots + 6 \cdot 1 = 56$ spacy subsets with $3$ elements.

Lastly, there are $3$ main categories for spacy subsets with $4$ elements, defined by the difference between their smallest and largest values. The difference ranges from $9$ to $11$ . If it is $9$ , there is only $1$ set of places to put the two middle values ( $n + 3$ and $n + 6$ , where $n$ is the smallest value). Since there are $3$ possible sets of smallest and largest values, there are $1 \cdot 3 = 3$ sets in this category. If the difference is $10$ , there are now $3$ sets of places to put the two middle values ( $n + 3$ and $n + 6$ or $7$ , and $n + 4$ and $n + 7$ ). There are $2$ possible sets of smallest and largest values, so there are $3 \cdot 2 = 6$ sets in this category. Finally, if the difference is $11$ , there are $6$ possible sets of places to put the two middle values ( $n + 3$ and $n + 6$ , $7$ , or $8$ , $n + 4$ and $n + 7$ or $8$ , and $n + 5$ and $n + 8$ ) and one possible set of smallest and largest values, meaning that there are $6 \cdot 1 = 6$ sets in this category. Adding them up, there are $3 + 6 + 6 = 15$ spacy subsets with $4$ elements.

Adding these all up, we have a total of $1 + 12 + 45 + 56 + 15 = \boxed{\mathrm{(E)}\ 129}$ spacy subsets. ~emerald_block

Solution 5

We build a modified version of Markov's chain to solve this problem. First, start off by representing each element of the chosen subset with a $1$ , and every other element $0$ . The possible states are as follows; if the restriction was broken previously or not. For the sake of not over counting, we let the former be its own state (call it "C"), and the latter will be split up into more states. The previous two digits can either be $00$ , $10$ , or $01$ . If a previous digit doesn't exist, it is $0$ for obvious reasons. We know that we start off at state " $00$ ". We have two options; include the first digit ( $1$ ) or not ( $0$ ). Thus, state $00$ transitions to state $01$ in $1$ case and state $00$ in $1$ case. State $01$ transitions to $10$ in $1$ case and the "C" state in $1$ case. State $10$ transitions to $00$ in $1$ case and state "C" in $1$ case. Since it doesn't matter where or how many times the restriction is broken for the subset to fail, state "C" can transition to itself in $2$ cases.

Notice how this corresponds to a transition matrix of $\begin{bmatrix} 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1\\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 2 \\ \end{bmatrix}$ . Since we start off on state $00$ , our starting state matrix is $\begin{bmatrix} 1 & 0 & 0 & 0\\ \end{bmatrix}$ . We wish to compute the value $a+b+c = 4096-d$ when given $f^{12}(\begin{bmatrix} 1 & 0 & 0 & 0\\ \end{bmatrix})=\begin{bmatrix} a & b & c & d\\ \end{bmatrix}$ , where $f(x)$ is $x\times\begin{bmatrix} 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1\\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 2 \\ \end{bmatrix}$ Through repeated applications of matrix multiplication, we obtain the output matrix of $\begin{bmatrix} 60 & 41 & 28 & 3967\\ \end{bmatrix}$ . Our answer is thus $60+41+28=\boxed{129}$ . Remark: Markov's Chain is more commonly used to calculate probabilities, but it also can be very useful for counting problems with a uniform requirement. -SigmaPiE

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