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

m (Solution 1)
m (minor edit)
(5 intermediate revisions by 4 users not shown)
Line 3: Line 3:
 
 
 
<math>\mathrm{(A)}\ 121 \qquad \mathrm{(B)}\ 123 \qquad \mathrm{(C)}\ 125 \qquad \mathrm{(D)}\ 127 \qquad \mathrm{(E)}\ 129</math>
 
<math>\mathrm{(A)}\ 121 \qquad \mathrm{(B)}\ 123 \qquad \mathrm{(C)}\ 125 \qquad \mathrm{(D)}\ 127 \qquad \mathrm{(E)}\ 129</math>
 
__TOC__
 
  
 
== Solution ==
 
== Solution ==
Line 25: Line 23:
 
| 1 || 2 || 3 || 4 || 6 || 9 || 13 || 19 || 28 || 41 || 60 || 88 || 129
 
| 1 || 2 || 3 || 4 || 6 || 9 || 13 || 19 || 28 || 41 || 60 || 88 || 129
 
|}
 
|}
And so the answer is <math>E</math>, <math>129</math>.
+
And so the answer is <math>(E)</math> <math>129</math>.
  
 
=== Solution 2 ===
 
=== Solution 2 ===
Line 34: Line 32:
 
For subsets of size <math>k</math> there must be <math>2(k - 1)</math> dividers between the balls, leaving <math>12 - k - 2(k - 1) = 12 - 3k + 2</math> dividers to be be placed in <math>k + 1</math> spots between the balls. The number of way this can be done is <math>\binom{(12 - 3k + 2) + (k + 1) - 1}k = \binom{12 - 2k + 2}k</math>.
 
For subsets of size <math>k</math> there must be <math>2(k - 1)</math> dividers between the balls, leaving <math>12 - k - 2(k - 1) = 12 - 3k + 2</math> dividers to be be placed in <math>k + 1</math> spots between the balls. The number of way this can be done is <math>\binom{(12 - 3k + 2) + (k + 1) - 1}k = \binom{12 - 2k + 2}k</math>.
  
Therefore, the number of spacy subsets is <math>\binom 64 + \binom 83 + \binom{10}2 + \binom{12}1 + \binom{14}0 = 129</math>.
+
Therefore, the number of spacy subsets is <math>\binom 64 + \binom 83 + \binom{10}2 + \binom{12}1 + \binom{14}0 = \boxed{129} </math>.
 +
 
 
=== Solution 3 ===
 
=== Solution 3 ===
 
A shifting argument is also possible, and is similar 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>
 
A shifting argument is also possible, and is similar 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>
  
In general, the number of subsets of a set with <math>n</math> element and with no <math>k</math> consecutive numbers is <math>\sum^{\lfloor{\frac{n}{k}}\rfloor}_{i=0}{{n-(k-1)(i-1) \choose i}}</math>.
+
In general, the number of subsets of a set with <math>n</math> elements and with no <math>k</math> consecutive numbers is <math>\sum^{\lfloor{\frac{n}{k}}\rfloor}_{i=0}{{n-(k-1)(i-1) \choose i}}</math>.
  
== See also ==
+
=== Solution 4 (Casework) ===
 +
Let us consider each size of subset individually. Since each integer in the subset must be at least <math>3</math> away from any other integer in the subset, the largest spacy subset contains <math>4</math> elements.
 +
 
 +
First, it is clear that there is <math>1</math> spacy set with <math>0</math> elements in it, the empty set. Next, there are <math>12</math> spacy subsets with <math>1</math> element in them, one for each integer <math>1</math> through <math>12</math>.
 +
 
 +
Now, let us consider the spacy subsets with <math>2</math> elements in them. If the smaller integer is <math>1</math>, the larger integer is any of the <math>9</math> integers from <math>4</math> to <math>12</math>. If the smaller integer is <math>2</math>, the larger integer is any of the <math>8</math> integers from <math>5</math> to <math>12</math>. This continues, up to a smaller integer of <math>9</math> and <math>1</math> choice for the larger integer, <math>12</math>. This means that there are <math>9 + 8 + \cdots + 1 = 45</math> spacy subsets with <math>2</math> elements.
 +
 
 +
For spacy subsets with <math>3</math> elements, we first consider the middle integer. The smallest such integer is <math>4</math>, and it allows for <math>1</math> possible value for the smaller integer (<math>1</math>) and possible <math>6</math> values for the larger integer (<math>7</math> through <math>12</math>), for a total of <math>1 \cdot 6 = 6</math> possible subsets. The next middle integer, <math>5</math>, allows for <math>2</math> smaller integers and <math>5</math> larger integers, and this pattern continues up until the middle integer of <math>9</math>, which has <math>6</math> values for the smaller integer and <math>1</math> value for the larger integer. This means that there are <math>1 \cdot 6 + 2 \cdot 5 + \cdots + 6 \cdot 1 = 56</math> spacy subsets with <math>3</math> elements.
 +
 
 +
Lastly, there are <math>3</math> main categories for spacy subsets with <math>4</math> elements, defined by the difference between their smallest and largest values. The difference ranges from <math>9</math> to <math>11</math>. If it is <math>9</math>, there is only <math>1</math> set of places to put the two middle values (<math>n + 3</math> and <math>n + 6</math>, where <math>n</math> is the smallest value). Since there are <math>3</math> possible sets of smallest and largest values, there are <math>1 \cdot 3 = 3</math> sets in this category. If the difference is <math>10</math>, there are now <math>3</math> sets of places to put the two middle values (<math>n + 3</math> and <math>n + 6</math> or <math>7</math>, and <math>n + 4</math> and <math>n + 7</math>). There are <math>2</math> possible sets of smallest and largest values, so there are <math>3 \cdot 2 = 6</math> sets in this category. Finally, if the difference is <math>11</math>, there are <math>6</math> possible sets of places to put the two middle values (<math>n + 3</math> and <math>n + 6</math>, <math>7</math>, or <math>8</math>, <math>n + 4</math> and <math>n + 7</math> or <math>8</math>, and <math>n + 5</math> and <math>n + 8</math>) and one possible set of smallest and largest values, meaning that there are <math>6 \cdot 1 = 6</math> sets in this category. Adding them up, there are <math>3 + 6 + 6 = 15</math> spacy subsets with <math>4</math> elements.
 +
 
 +
Adding these all up, we have a total of <math>1 + 12 + 45 + 56 + 15 = \boxed{\mathrm{(E)}\ 129}</math> spacy subsets. ~[[User:emerald_block|emerald_block]]
 +
 
 +
== See Also ==
 
{{AMC12 box|year=2007|ab=A|num-b=24|after=Last question}}
 
{{AMC12 box|year=2007|ab=A|num-b=24|after=Last question}}
 
 
[[Category:Intermediate Combinatorics Problems]]
 
[[Category:Intermediate Combinatorics Problems]]
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 01:51, 19 October 2020

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

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^{\lfloor{\frac{n}{k}}\rfloor}_{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

See Also

2007 AMC 12A (ProblemsAnswer KeyResources)
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png