Difference between revisions of "2001 AIME I Problems/Problem 14"
Mathlegend27 (talk | contribs) |
Mathlegend27 (talk | contribs) |
||
Line 31: | Line 31: | ||
==Solution 2 ( Less recursion than solution 1) == | ==Solution 2 ( Less recursion than solution 1) == | ||
− | Let <math>M_n</math> represent the number of mail delivery patterns that end with the last house receiving mail. This is <math>b_n</math> in Solution 1. Similarly define <math>A_n</math> to be the number of mail delivery patterns that end with last house not receiving mail. Let <math>T_n</math> be the total number of mail delivery patterns. | + | Let <math>M_n</math> represent the number of mail delivery patterns that end with the last house receiving mail. This is <math>b_n</math> in Solution 1. Similarly define <math>A_n</math> to be the number of mail delivery patterns that end with last house not receiving mail. This is just <math>a_n</math> and <math>c_n</math> in solution 1. Let <math>T_n</math> be the total number of mail delivery patterns. |
Here are the possible ending cases: the string ends in <math>1, 10,</math> or <math>100</math>. The first case is just <math>M_n</math>. The second case is <math>M_{n-1}</math>. The third case is <math>M_{n-2}</math>. So we have <math>T_n = M_n + M_{n-1} + M_{n-2}</math>. Since we want <math>T_{19}</math>, it is just <math> M_{18} + M_{17} + M_{16}</math>. | Here are the possible ending cases: the string ends in <math>1, 10,</math> or <math>100</math>. The first case is just <math>M_n</math>. The second case is <math>M_{n-1}</math>. The third case is <math>M_{n-2}</math>. So we have <math>T_n = M_n + M_{n-1} + M_{n-2}</math>. Since we want <math>T_{19}</math>, it is just <math> M_{18} + M_{17} + M_{16}</math>. | ||
− | Now using the same logic as above we can find <math>M_n = M_{n-2} + | + | Now using the same logic as above we can find <math>M_n = M_{n-2} + M_{n-3}</math> ( the cases are 01 and 001). We can refer back to solution 1's table and only keep track of <math>b_n</math>, ignoring both <math>a_n</math> and <math>c_n</math>. |
+ | - MathLegend27 | ||
== See also == | == See also == |
Revision as of 19:08, 8 November 2018
Contents
[hide]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:
As a result .
Solution 2 ( Less recursion than solution 1)
Let represent the number of mail delivery patterns that end with the last house receiving mail. This is in Solution 1. Similarly define to be the number of mail delivery patterns that end with last house not receiving mail. This is just and in solution 1. Let be the total number of mail delivery patterns.
Here are the possible ending cases: the string ends in or . The first case is just . The second case is . The third case is . So we have . Since we want , it is just . Now using the same logic as above we can find ( the cases are 01 and 001). We can refer back to solution 1's table and only keep track of , ignoring both and . - MathLegend27
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.