Massachusetts Institute of Technology Handout 34 6.042J/18.062J: Mathematics for Computer Science October 27, 2000 Professors Nancy Lynch and Srinivas Devadas

Tutorial 8 Problems

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?

Solution: Let g(n) be the number of Marons after n years, and f(n) the number of Batons.

After n − 1 years, we have g(n − 1) Marons and f(n − 1) Batons. Then in the n^{th} year, from the rules of sustenance, the population of Batons drops to f(n − 1) − (1/2)g(n − 1). The number of 1-year old Marons is g(n − 1) − g(n − 2). Their population goes up to 2(g(n − 1) − g(n − 2)). Meanwhile the number of older Marons goes up from g(n − 2) to 3g(n − 2). Then it is the Batons turn. The survivors consume a Maron each. So the population of Marons after n years is

g(n) = 2(g(n − 1) − g(n − 2)) + 3g(n − 2) − (f(n − 1) − \frac{1}{2}g(n − 1))

That is,

g(n) = \frac{5}{2}g(n − 1) + g(n − 2) − f(n − 1)

The Batons then quadruple. So the number of Batons after n years is:

f(n) = 4(f(n − 1) − \frac{1}{2}g(n − 1))

We know that f(1) = g(1) = 2 and f(2) = g(2) = 4. Substituting these values in the recurrences, we get f(3) = g(3) = 8 and f(4) = g(4) = 16.

We guess that g(n) = f(n) = 2^{n}. We can verify this by strong double induction. Note that there is only 1 variable, n, the number of years, but we will argue inductively about both f(n) and g(n).

I.H. : P (n) : f(n) = g(n) = 2^{n}.

Base: n = 1: f(1) = g(1) = 2 and

n = 2: f(2) = g(2) = 4.

Ind. Step.: Assume P (k) is true for 1 ≤ n. To prove P (n + 1) consider f(n + 1), g(n + 1).

f(n + 1) = 4(f(n) − \frac{1}{2}g(n)) = 4(2^{n} − 2^{n−1})

= 4(2^{n−1}) = 2^{n+1}

And,

g(n + 1) = \frac{5}{2}g(n) + g(n − 1) − f(n) = \frac{5}{2}(2^{n}) + 2^{n−1} − 2^{n} = 2^{n+1}

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.)

Solution: Let A(n) be the number of ways Alice can climb up a flight of n stairs. Then, using the fact that her last stride is a 1-step or a 2-step,

A(n) = A(n − 1) + A(n − 2)

where A(1) = 1, A(2) = 2, . . .. This is the familiar Fibonacci recurrence, So A(n) = F_{n+1}, the (n + 1)^{th} Fibonacci number.

Similarly Let B(n) be the number of ways Bob can climb n stairs. Assume n is even.

B(n) = B(n − 2) + B(n − 4) + … + B(2)

From this we can say that for n ≥ 4,

B(n − 2) = B(n − 4) + … + B(2)

Subtracting the latter equation from the former,

B(n) − B(n − 2) = B(n − 2)
B(n) = 2B(n − 2)

We can solve this by expanding the recurrence relation repeatedly:

B(n) = 2B(n − 2) = 4B(n − 4) = 2^{3}B(n − 6) = 2^{k}B(n − 2k) = 2^{n/2−1}B(2)
B(n) = 2^{n/2−1}

But then B(n) ≤ F_{n+1} = A(n).

Problem 3 Let S be the set of numbers 7, 77, 777, . . .. Prove that there is an element of S that is divisible by 1997.

We use the pigeonhole principle. Let the pigeons be the elements s ∈ S, and the holes be the numbers 0 … 1996. Let s be placed in s mod 1997.

Since there are more than 1997 elements of S, some hole must have two numbers, say s_{i} and s_{j}, with i and j 7’s respectively. Without loss of generality, assume that i < j.

Then, s_{j} − s_{i} = 77 … 700 … 0 where there are j − i 7’s and i 0’s. So, s_{j} − s_{i} = s_{j−i} · 10^{i}. Since s_{j} mod 1997 = r = s_{i} mod 1997, s_{j} − s_{i} mod 1997 = 0, so 1997 | (s_{j} − s_{i}). But gcd(1997, 10^{i}) = 1, so 1997 must divide s_{j−i}.