Difference between revisions of "2001 AIME I Problems/Problem 14"
Mathgeek2006 (talk | contribs) m (→Solution) |
(→Solution) |
||
Line 2: | Line 2: | ||
A mail carrier delivers mail to the nineteen houses on the east side of Elm Street. The carrier notices that no two adjacent houses ever get mail on the same day, but that there are never more than two houses in a row that get no mail on the same day. How many different patterns of mail delivery are possible? | A mail carrier delivers mail to the nineteen houses on the east side of Elm Street. The carrier notices that no two adjacent houses ever get mail on the same day, but that there are never more than two houses in a row that get no mail on the same day. How many different patterns of mail delivery are possible? | ||
− | == Solution == | + | == Solutions== |
+ | ==Solution 1== | ||
Let <math>0</math> represent a house that does not receive mail and <math>1</math> represent a house that does receive mail. This problem is now asking for the number of <math>19</math>-digit strings of <math>0</math>'s and <math>1</math>'s such that there are no two consecutive <math>1</math>'s and no three consecutive <math>0</math>'s. | Let <math>0</math> represent a house that does not receive mail and <math>1</math> represent a house that does receive mail. This problem is now asking for the number of <math>19</math>-digit strings of <math>0</math>'s and <math>1</math>'s such that there are no two consecutive <math>1</math>'s and no three consecutive <math>0</math>'s. | ||
Line 26: | Line 27: | ||
c_n&1&1&2&2&3&4&5&7&9&12&16&21&28&37&49&65&86&114\\\hline | c_n&1&1&2&2&3&4&5&7&9&12&16&21&28&37&49&65&86&114\\\hline | ||
\end{array}</cmath> | \end{array}</cmath> | ||
+ | ==Solution 2== | ||
+ | Let's call the number of sequences that start with a house getting mail and of length <math>n</math> as <math>A_n</math> and call <math>B_n</math> the opposite(first house gets no mail). We get <math>A_n=B_{n-1}</math> and <math>B_{n}=B_{n-1}+ | ||
− | Therefore, the number of <math>19< | + | Therefore, the number of </math>19<math>-digit strings is </math>a_{19}+b_{19}+c_{19} = 86+151+114 = \boxed{351}.$ |
== See also == | == See also == |
Revision as of 15:28, 28 May 2017
Problem
A mail carrier delivers mail to the nineteen houses on the east side of Elm Street. The carrier notices that no two adjacent houses ever get mail on the same day, but that there are never more than two houses in a row that get no mail on the same day. How many different patterns of mail delivery are possible?
Solutions
Solution 1
Let represent a house that does not receive mail and
represent a house that does receive mail. This problem is now asking for the number of
-digit strings of
's and
's such that there are no two consecutive
's and no three consecutive
's.
The last two digits of any -digit string can't be
, so the only possibilities are
,
, and
.
Let be the number of
-digit strings ending in
,
be the number of
-digit strings ending in
, and
be the number of
-digit strings ending in
.
If an -digit string ends in
, then the previous digit must be a
, and the last two digits of the
digits substring will be
. So
If an -digit string ends in
, then the previous digit can be either a
or a
, and the last two digits of the
digits substring can be either
or
. So
If an -digit string ends in
, then the previous digit must be a
, and the last two digits of the
digits substring will be
. So
Clearly, . Using the recursive equations and initial values:
Solution 2
Let's call the number of sequences that start with a house getting mail and of length as
and call
the opposite(first house gets no mail). We get
and $B_{n}=B_{n-1}+
Therefore, the number of$ (Error compiling LaTeX. Unknown error_msg)19a_{19}+b_{19}+c_{19} = 86+151+114 = \boxed{351}.$
See also
2001 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 13 |
Followed by Problem 15 | |
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.