Problem 16 Recursion
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Problem 16 Recursion as PDF for free.
More details
- Words: 233
- Pages: 1
Problem 16: Recursion
AIME 2001 #14
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? Solution: Consider n-digit strings of zeros and ones, which represent no mail and mail, respectively. Such a sequence is called acceptable if it contains no occurrence of 11 or 000. Let fn be the number of acceptable n-digit strings, let an be the number of acceptable n-digit strings in which 00 follows the leftmost 1, and let bn be the number of acceptable n-digit strings in which 01 follows the leftmost 1. Notice that fn = an + bn for n ≥ 5. Deleting the leftmost occurrence of 100 shows that an = fn−3 , and deleting 10 from the leftmost occurrence of 101 shows that bn = fn−2 . It follows that fn = fn−2 + fn−3 for n ≥ 5. It is straightforward to verify the values f1 = 2, f2 = 3, f3 = 4, and f4 = 5. Then the recursion can be used to find that f19 = 351.
This is the official solution, compiled from Art of Problem Solving Forums.
AIME 2001 #14
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? Solution: Consider n-digit strings of zeros and ones, which represent no mail and mail, respectively. Such a sequence is called acceptable if it contains no occurrence of 11 or 000. Let fn be the number of acceptable n-digit strings, let an be the number of acceptable n-digit strings in which 00 follows the leftmost 1, and let bn be the number of acceptable n-digit strings in which 01 follows the leftmost 1. Notice that fn = an + bn for n ≥ 5. Deleting the leftmost occurrence of 100 shows that an = fn−3 , and deleting 10 from the leftmost occurrence of 101 shows that bn = fn−2 . It follows that fn = fn−2 + fn−3 for n ≥ 5. It is straightforward to verify the values f1 = 2, f2 = 3, f3 = 4, and f4 = 5. Then the recursion can be used to find that f19 = 351.
This is the official solution, compiled from Art of Problem Solving Forums.
Related Documents
Problem 16 Recursion
November 2019 14
Problem 3 Recursion
November 2019 11
Recursion
April 2020 14
Recursion
November 2019 17
Wacc Problem 16
December 2019 14