Question

A Street has 13 houses in a row as shown in the figure. Some residents in the first house tested positive for COVID-19. The virus spreads in two ways: it can spread to the next house, or jump directly to the third house. Residents of house number 2 can get infection in only one way, the house number 3 in two ways, the house number 4 in 3 ways, the house number 5 in 5 ways and so on. If the virus only progresses from Left to Right direction, in how many ways can the residents of the house number 13 get infected?

Answer 1

Correct Answer: 233

To determine the number of ways the virus can infect the residents of the 13th house, given it spreads by moving to the next house or jumping directly to the third house, we observe a pattern similar to the Fibonacci sequence. Let's denote the number of ways the residents of house n can get infected as \( a_n \). The rules are as follows:

• House 1 is initially infected, so \( a_1 = 1 \).
• House 2 can only be infected from house 1, so \( a_2 = 1 \).
• For subsequent houses, the residents can get infected from either the previous house or from the house two places before:

\( a_n = a_{n-1} + a_{n-2} \) for \( n \geq 3 \).
We compute the sequence up to house 13:

• \( a_3 = a_2 + a_1 = 1 + 1 = 2 \)
• \( a_4 = a_3 + a_2 = 2 + 1 = 3 \)
• \( a_5 = a_4 + a_3 = 3 + 2 = 5 \)
• \( a_6 = a_5 + a_4 = 5 + 3 = 8 \)
• \( a_7 = a_6 + a_5 = 8 + 5 = 13 \)
• \( a_8 = a_7 + a_6 = 13 + 8 = 21 \)
• \( a_9 = a_8 + a_7 = 21 + 13 = 34 \)
• \( a_{10} = a_9 + a_8 = 34 + 21 = 55 \)
• \( a_{11} = a_{10} + a_9 = 55 + 34 = 89 \)
• \( a_{12} = a_{11} + a_{10} = 89 + 55 = 144 \)
• \( a_{13} = a_{12} + a_{11} = 144 + 89 = 233 \)

Thus, the number of ways the residents of house number 13 can get infected is 233, which fits the expected range of 233,233.