One robot on the moon gathers resources to build more robots for 3 months, then he builds robots at the rate of one per month for two months and repeats the process. The robots made do the same thing. How long will it take for the population to grow to 200?



closed as off-topic by Xander Henderson, Brahadeesh, Delta-u, José Carlos Santos, Michael Hoppe Oct 18 '18 at 10:44

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Xander Henderson, Brahadeesh, Delta-u, José Carlos Santos, Michael Hoppe
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Welcome to MSE. It will be more likely that you will get an answer if you show us that you made an effort. This should be added to the question rather than in the comments. $\endgroup$ – José Carlos Santos Aug 31 '18 at 8:49

Every robot works on a five month cycle. For months 1, 2, and 3, they are effectively inactive, and for months 4 and 5 they effectively make a copy of themselves. Suppose that after $n$ months, there are $a_n$ robots on the first month of their cycle, $b_n$ on the second, $c_n$ on their third, and $d_n$ on their fourth and $e_n$ on their fifth. The total number of robots is $r_n=a_n+b_n+c_n+d_n+e_n$.

Now, what happens on the $(n+1)^\text{th}$ month? Each of the $d_n+e_n$ robots in their active months creates one new robot, which must get placed into the first month bucket. Also, each of the $e_n$ robots in their fifth month, moves back into the first month of their next cycle. Thus, $a_{n+1}=d_n+e_n+e_n$. Otherwise, the robots "cycle up a letter": $b_{n+1}=a_n$, because each of the $a_n$ robots in their first month before, are now in their second month. Similarly, we obtain the relationships $$ \left\{ \begin{array}[rcl]{} a_{n+1} &=& d_n+2e_n \\ b_{n+1} &=& a_n \\ c_{n+1} &=& b_n \\ d_{n+1} &=& c_n \\ e_{n+1} &=& d_n \\ \end{array} \right.$$ So $r_{n+1}=a_n+b_n+c_n+2d_n+2e_n$. Ultimately, the goal is to eliminate all of these extra categories ($a,b,c,d,e$) and describe $r_n$ in terms of $r_k$ for smaller $k$. Since we know that each robot is on a five-day cycle, perhaps the entire system is also on a five-day cycle of some sort. Let's see what happens if we calculate $r_{n+5}$. We have to go step-by-step, since we don't have any better way yet:

$$ \left\{ \begin{array}[rcl]{} a_{n+2} &=& c_n+2d_n \\ b_{n+2} &=& d_n+2e_n \\ c_{n+2} &=& a_n \\ d_{n+2} &=& b_n \\ e_{n+2} &=& c_n \\ \end{array} \right.$$

$$ \left\{ \begin{array}[rcl]{} a_{n+3} &=& b_n+2c_n \\ b_{n+3} &=& c_n+2d_n \\ c_{n+3} &=& d_n+2e_n \\ d_{n+3} &=& a_n \\ e_{n+3} &=& b_n \\ \end{array} \right.$$

$$ \left\{ \begin{array}[rcl]{} a_{n+4} &=& a_n+2b_n \\ b_{n+4} &=& b_n+2c_n \\ c_{n+4} &=& c_n+2d_n \\ d_{n+4} &=& d_n+2e_n \\ e_{n+4} &=& a_n \\ \end{array} \right.$$

Almost there...

$$ \left\{ \begin{array}[rcl]{} a_{n+5} &=& d_n+2e_n+2a_n \\ b_{n+5} &=& a_n+2b_n \\ c_{n+5} &=& b_n+2c_n \\ d_{n+5} &=& c_n+2d_n \\ e_{n+5} &=& d_n+2e_n \\ \end{array} \right.$$

So $r_{n+5}=3a_n+3b_n+3c_n+4d_n+4e_n$. Notice that this is almost $3r_n$, except that there's an extra copy of $d_n$ and $e_n$. This, in turn, is very similar to the situation in $r_{n+1}$, and we can use this to our advantage: check that $r_{n+5}=2r_n + r_{n+1}$.

In retrospect, this formula isn't so surprising; it has some superficial similarity to $a_n=2e_n+d_n$. If you trace back through the steps, you will see that this is no accident at all. After doing enough of these problems, you can develop some intuition for how these formulas will be formed, without going through the hard work that we did above.

We need one more step in order to finish the calculation: so far, we have determined the recurrence $r_{n+5}=2r_n+r_{n+1}$. However, notice that we implicitly assumed above that $n\geq 0$ (because we ask that $n$ months have passed), and so this formula doesn't let you calculate $r_0, r_1, r_2, r_3$, or $r_4$ in terms of earlier values. You must manually supply these yourself; fortunately, they are easy. Check that $$r_0=r_1=r_2=r_3=1; \qquad r_4=2.$$

Finally, we calculate:

  • $r_5=2r_0+r_1 = 3$
  • $r_6=2r_1+r_2 = 3$
  • $r_7=2r_2+r_3 = 3$
  • $r_8=2r_3+r_4 = 4$
  • $r_9=2r_4+r_5 = 7$

  • $r_{10}=2r_5+r_6 = 9$

  • $r_{11}=2r_6+r_7 = 9$
  • $r_{12}=2r_7+r_8 = 10$
  • $r_{13}=2r_8+r_9 = 15$
  • $r_{14}=2r_9+r_{10} = 23$

  • $r_{15}=2r_{10}+r_{11} = 27$

  • $r_{16}=2r_{11}+r_{12} = 28$
  • $r_{17}=2r_{12}+r_{13} = 35$
  • $r_{18}=2r_{13}+r_{14} = 53$
  • $r_{19}=2r_{14}+r_{15} = 73$

  • $r_{20}=2r_{15}+r_{16} = 82$

  • $r_{21}=2r_{16}+r_{17} = 91$
  • $r_{22}=2r_{17}+r_{18} = 123$
  • $r_{23}=2r_{18}+r_{19} = 179$
  • $r_{24}=2r_{19}+r_{20} = 228$. Whew!

Conclusion: it will take $24$ months for the population to reach (at least) 200.

Remark: This last bit of calculation cannot really be avoided or learned intuitively, although it can be automated. Automation is a good idea because any erroneously calculated $r_n$ will be used to calculate later values, which means that even a single error, made early enough, may wildly affect the end result. (Indeed, I did all these calculations by hand, and I'm not totally confident that I've gotten the right answer.)

There do exist general formulas for solving recurrences like this one, but in practice these formulas don't let you solve by hand, because they require you to factor a polynomial of large degree (e.g. for this problem you must factor $x^5-x-2$). This is generally impossible to do exactly, and approximations are cumbersome and technical.

  • $\begingroup$ While MRobinson's answer is correct (this is similar to Fibonacci's rabbit problem), the similarity is somewhat abstract. A beginner may reasonably wonder about the relationship between these two problems, hence the detailed description. $\endgroup$ – aleph_two Oct 15 '18 at 1:26

This is similar to the "Rabbit" problem which lead Fibonacci to arrive at his famous sequence. Have a read up on this and see if that helps.





Not the answer you're looking for? Browse other questions tagged or ask your own question.