MA-351 Homework 1

Due at 4:59pm in my mailbox in SAS 3151, Thursday, September 10, 2009


Calculations necessary for these problems may be done either by hand or with Maple. Solutions may be submitted in person in class, or you may email an ASCII text, Maple Worksheet (.mws), html, or postscipt/pdf-formatted document to me.
Note my office hours on my schedule.

    1. Derive the linear recurrence for Fibonacci's rabbits' problem with the change that each pair of rabbits gives birth to t pairs of rabbits instead of one, where t is an arbitrary integer.
    2. Derive a "closed form" solution in terms of t for the above recurrence.

  2. Consider the r-dimensional de Bruijn digraph with 2r vertices and 2r+1 arcs. Like in the hypercube, the vertices are r bit numbers. There is an arc from each vertex i1,i2,...,ir, where ij is either 0 or 1, to the vertex i2,i3,...,ir,0 and an arc to the vertex i2,i3,...,ir,1.
    1. Draw a nice picture of the digraph for r = 3.
    2. Prove that for r = 4 the digraph has the same diameter as the 4 dimensional hypercube, that is, the maximum distance between two vertices is 4. Your argument must both show that between any two vertices there is a path of length no more than 4, and that there exist two vertices whose distance is at least 4.

  3. Consider the 5-dimensional hypercube as presented in class. In class the vertices were the integers from 1 to 32. The task is to relabel the vertices in the drawing as 5-digit binary numbers (sequences of 5 integers in {0,1}) in such a way that the Hamming distance between adjacent vertices is exactly one.

    5-D Hypercube