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

Revision as of 18:06, 20 September 2007

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 $S_{n + 1}$ can be divided into two subsets:

Those containing $n + 1$ . This is $S_{n - 2}$ , since removing $n + 1$ from any of these sets produces a spacy set with maximal element $n - 2$ .
Those not containing $n + 1$ . This is $S_{n}$ .

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

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 10: / Line 10: @@
 Let <math>S_{n}</math> denote the number of spacy subsets of <math>\{ 1, 2, ... n \}</math>.  We have <math>S_{0} = 1, S_{1} = 2, S_{2} = 3</math>.
-The spacy subsets <math>S_{n + 1}</math> can be divided into the subsets containing <math>n + 1</math> and the ones not containing <math>n + 1</math>.  The latter is just <math>S_{n}</math>, whereas the former is <math>S_{n - 2}</math> (since removing <math>n + 1</math> from any of these sets produces a spacy set with maximal element <math>n - 2</math>). Hence,
+The spacy subsets <math>S_{n + 1}</math> can be divided into two subsets:
+*Those containing <math>n + 1</math>. This is <math>S_{n - 2}</math>, since removing <math>n + 1</math> from any of these sets produces a spacy set with [[maximum|maximal]] element <math>n - 2</math>.
+*Those not containing <math>n + 1</math>.  This is <math>S_{n}</math>.
+Hence,
 <div style="text-align:center;"><math>S_{n + 1} = S_{n} + S_{n - 2}</math></div>
-From this recursion, we find that
+From this [[recursion]], we find that
-{| class="wikitable"
+{| class="wikitable" border="1px solid"
 |-
-| S(1) || S(2) || S(3) || S(4) || S(5) || S(6) || S(7) || S(8) || S(9) || S(10) || S(11) || S(12) ||
+| <math>S(0)</math> || <math>S(1)</math> || <math>S(2)</math> || <math>S(3)</math> || <math>S(4)</math> || <math>S(5)</math> || <math>S(6)</math> || <math>S(7)</math> || <math>S(8)</math> || <math>S(9)</math> || <math>S(10)</math> || <math>S(11)</math> || <math>S(12)</math> ||
 |-
 | 1 || 2 || 3 || 4 || 6 || 9 || 13 || 19 || 28 || 41 || 60 || 88 || 129

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