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

Problem Set 7 Solutions

2:35pm in lecture, Tuesday, October 31, 2000

Be sure to indicate your TA’s name clearly on the solutions your turn in.

—————————————————————————–

Self-study Read: Rosen Sections 1.6, 4.1, 4.2, and 4.3 Self-study problems (not to be handed in): Section 1.6: 19 Section 4.1: 1, 8, 29 Section 4.2: 4, 14

—————————————————————————–

Reading: Lecture notes; Rosen 4.1, 4.2, and 4.3

Policy on collaboration If you collaborated with someone on the problem sets, you should mention their names on top of the problem set. If you did not collaborate with anyone, you should explicitly say so. As a reminder, the write-up of your solutions should be entirely your own.

Problem 1 Find closed-form solutions to the following homogenous linear recurrences.

(a) x_{n} = 5x_{n−1} − 6x_{n−2} (x_{0} = 0, x_{1} = 1)

(b) x_{n} = 5x_{n−1} − 8x_{n−2} + 4x_{n−3} (x_{0} = 1, x_{1} = 2, x_{2} = 3)

Problem 2 Find closed-form solutions to the following inhomogenous linear recurrences.

(a) (Fibonacci Plus) x_{n} = x_{n−1} + x_{n−2} + 1 (x_{0} = 0, x_{1} = 1)

(b) x_{n} = 3x_{n−1} − 2x_{n−2} + n (x_{0} = 0, x_{1} = 1)

Problem 3 The 6.042 staff recently received the following email.

From: grzzwk@xoros19.gammaquad.plnt
To: 6042-staff@theory.lcs.mit.edu
Subject: Pset 5 issue
Thank you for contributing the MergeSortX19 algorithm to our
``intellectually challenged'' society.  My, my-- we feel mentally
bloated by this sudden infusion of technological wizardry!

As a token of thanks, we launched a Doritofier missile on a straight
line toward Earth.  Suppose that p(t) denotes the distance between
Xoros 19 and the Doritofier after t days of flight.  At the moment of
launch, the Doritofier was here on Xoros 19, and so p(0) = 0.  After a
single day, the Doritofier had already traveled 100 units toward
Earth, so p(1) = 100.  In general, the position of the missle is given
by the following recurrence:
       p(t+1) = 1.99 * p(t) - p(t-1)
Earth happens to be 1010 units from Xoros 19.  Gotta run!  Seeya!
/Grzzwk

Find a closed-form solution to the recurrence for the distance between Xoros 19 and the Doritofier after t days of flight.

Problem 4 For each of the functions below, determine whether the function is injective, whether it is surjective, and whether it is bijective. No proofs are required.

(a) The function f : ℝ ↦ ℝ defined by f(x) = e^{x}

(b) The function f : ℝ ↦ ℝ^{+} defined by f(x) = e^{x}. (Here ℝ^{+} denotes the set of positive real numbers.)

(c) The function f : ℝ ↦ ℝ defined by (x + 1)/(x^{2} + 1)

(d) The function f : ℝ ↦ ℝ defined by

f(x) = \{ \begin{matrix}1/x & for x ≠ 0 \\ 0 & for x = 0. \end{matrix}

Problem 5 Multiple linear recurrences On a certain far away island, all men are either blond or brown-haired. Studies show that each man has exactly four sons. Every blond father has exactly three blond sons, while every brown-haired man has exactly two brown-haired sons. As soon as the father has his four sons, he moves to Florida to retire, and never returns to the island.

(a) Let a_{n} and b_{n} denote the number of blond and brown-haired men, respectively, after n generations. Write a system of recurrences for a_{n} and b_{n}.

(b) For which values of c ≠ 0 and d will we have a solution of the form a_{n} = c^{n}, b_{n} = dc^{n}?

(c) Show that there exist values for c_{1}, c_{2}, d_{1}, and d_{2} such that

\begin{aligned}a_{n} & = xc_{1}^{n} + yc_{2}^{n}, \\ b_{n} & = xd_{1}c_{1}^{n} + yd_{2}c_{2}^{n}, \end{aligned}

is a solution for all x and y.

(d) Suppose that the first generation consisted of ten blond and twenty brown-haired men on the island. How many of each group will there be after the nth generation?

Problem 6

(a) Theory Pig has often complained that the name “Pigeonhole Principle” is verbose and awkward. He proposes the more concise term “Pig Principle” for the same idea. Recently, he devised a problem involving this idea in order to promote his terminology.

Suppose that m pigs are lined up, and each pig is given one or more tasty treats. Prove that there is always a set of pigs that are consecutive in the lineup and that all together receive a number of treats that is a multiple of m.

For example, suppose that there are m = 5 pigs, and that they receive 1, 6, 2, 7, and 9 treats respectively. Then the claim holds in this case, because the second, third, and fourth pigs received 6 + 2 + 7 = 15 treats altogether, and 15 is a multiple of 5.

(b) A lattice point is a point in a coordinate plane for which both coordinates are integers. Prove that no matter what five lattice points might be chosen in the plane at least one of the segments that joins two of the chosen points must pass through some lattice point in the plane.