Massachusetts Institute of Technology Handout 31 6.042J/18.062J: Mathematics for Computer Science October 16, 1998 Professors Nancy Lynch and Srini Devadas

Problems for Recitation 6

Problem 1. Life and Death. In ancient Mars, cannibalism was an essential way of life. The Marons and the Batons were two species that lived for several thousand years in close contact. Every year, first all the Marons sustained themselves by first consuming Batons: two Marons ate one Baton between them. Then they reproduced: one-year-old Marons doubled in number while Marons that were two or older tripled in number. Then the surviving Batons consumed one Maron each and then all the Batons reproduced to quadruple in number. This cycle repeated every year. After 1 year there were two 1-year old Marons and two 1-year old Batons. After 2 years there were two 1-year olds and two 2-year olds in each of the two species. How many of each will there be of each species at the end of n years?

Problem 2. Stepping up. Alice the “elegant” climbs up a flight of stairs one or two stairs in one stride. Bob the “elongated beast” on the other hand clambers up 2, 4, 6 or any even number of stairs in one stride. Who can climb a flight of n stairs in more ways? (Assume n is even. A way of climbing a flight of n stairs is the sequence of strides taken to get to the top. E.g. to climb up 4 stairs, Alice can go 1,1,1,1 or 1,1,2, or 1,2,1, or 2,1,1 or 2,2 i.e., in 5 different ways in all.)