Difference between revisions of "2008 AIME II Problems/Problem 12"
(→Solution 2) |
(→Solution 2) |
||
| Line 20: | Line 20: | ||
Case 1 - Both poles have blue flags: | Case 1 - Both poles have blue flags: | ||
| − | There are 9 ways to place the 10 blue flags on the poles. In each of these configurations, there are 12 spots that a green flag could go. (either in between two blues or at the tops or | + | There are 9 ways to place the 10 blue flags on the poles. In each of these configurations, there are 12 spots that a green flag could go. (either in between two blues or at the tops or bottoms of the poles) Then, since there are 9 green flags, all of which must be used, there are <math>{12\choose9}</math> possiblities for each of the 9 ways to place the blue flags. Total: <math>{12\choose9}*9</math> possibilities. |
Case 2 - One pole has no blue flags: | Case 2 - One pole has no blue flags: | ||
| − | Since each pole | + | Since each pole is non empty, the pole without a blue flag must have one green flag. The other pole has 10 blue flags and, by the argument used in case 1, there are <math>{11\choose8}</math> possibilities, and since the poles are distinguishable, there are a total of <math>2*{11\choose8}</math> possiblities for this case. |
| − | Finally, we have <math>{12\choose9}+2*{11\choose8}=2310 \equiv \boxed{310} \pmod{1000}</math> as our answer. | + | Finally, we have <math>9*{12\choose9}+2*{11\choose8}=2310 \equiv \boxed{310} \pmod{1000}</math> as our answer. |
== See also == | == See also == | ||
Revision as of 17:11, 5 March 2015
Problem
There are two distinguishable flagpoles, and there are 
flags, of which 
are identical blue flags, and 
are identical green flags. Let 
be the number of distinguishable arrangements using all of the flags in which each flagpole has at least one flag and no two green flags on either pole are adjacent. Find the remainder when is divided by 
.
Solution
Solution 1
The well known problem of ordering 
elements of a string of 
elements such that none of the elements are next to each other has 
solutions. (1)
We generalize for 
blues and 
greens. Consider a string of 
elements such that we want to choose the greens such that none of them are next to each other. We would also like to choose a place where we can divide this string into two strings such that the left one represents the first pole, and the right one represents the second pole, in order up the pole according to position on the string.
However, this method does not account for the fact that the first pole could end with a green, and the second pole could start with a green, since the original string assumed that no greens could be consecutive. We solve this problem by introducing an extra blue, such that we choose our divider by choosing one of these 
blues, and not including that one as a flag on either pole.
From (1), we now have 
ways to order the string such that no greens are next to each other, and ways to choose the extra blue that will divide the string into the two poles: or 
orderings in total.
However, we have overcounted the solutions where either pole has no flags, we have to count these separately. This is the same as choosing our extra blue as one of the two ends, and ordering the other blues and greens such that no greens are next to each other: for a total of 
such orderings.
Thus, we have 
orderings that satisfy the conditions in the problem: plugging in 
and 
, we get 
.
Solution 2
Split the problem into two cases:
Case 1 - Both poles have blue flags:
There are 9 ways to place the 10 blue flags on the poles. In each of these configurations, there are 12 spots that a green flag could go. (either in between two blues or at the tops or bottoms of the poles) Then, since there are 9 green flags, all of which must be used, there are 
possiblities for each of the 9 ways to place the blue flags. Total: 
possibilities.
Case 2 - One pole has no blue flags:
Since each pole is non empty, the pole without a blue flag must have one green flag. The other pole has 10 blue flags and, by the argument used in case 1, there are 
possibilities, and since the poles are distinguishable, there are a total of 
possiblities for this case.
Finally, we have 
as our answer.
See also
| 2008 AIME II (Problems • Answer Key • Resources) | ||
| Preceded by Problem 11 |
Followed by Problem 13 | |
| 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. 
