Question 1: Linear algebra and graph theory -------------------------------------------- In this problem we are considering "paths" in a graph that are allowed to use edges multiple times, unlike in the rest of the course where the book says that a "path" can use any edge ony once. Suppose v_a and v_b are two vertices of a graph G (whose n vertices have been numbered v_1,...,v_n). We want to count the number of paths in the graph from v_a to v_b that have length exactly k (length=number of edges participating in the graph). We denote N(k,a,b) this number of paths of length k. For example, if G is a triangle then N(1,a,b)=N(2,a,b)=1 if a is different from b, but N(3,a,a)=2 (you can go both ways). a) Explain why N(1,a,b) can easily be found from the adjacency matrix of G. b) Express N(2,a,b) in terms of the entries of the adjacency matrix. Hint: a path of length 2 from v_a to v_b is the result of combining a path of length 1 from v_a to an intermediate vertex X with a path of length 1 from X to v_b. c) For extra points, guess and explain a general formula for N(k,a,b) in terms of the adjacency matrix. Question 2: Euler vs Hamilton ----------------------------- Let N be a natural number at least equal to 3. Find a graph with N vertices that has an Euler and a Hamilton circuit and where these two circuits are identical. Prove that only one such graph exists for each N. Question 3: Enumerating spanning trees in complete graphs ------------------------------------------------------ a) Find the tree that corresponds to the Pruefer sequence (3,3,7,5,9,1,3). b) Consider the following path in the complete graph K_10: 4->2->10->5->1->8->9->6->3->7. Since it uses 9=10-1 edges, it is a spanning tree in K_10. Find its Pruefer sequence. Question 4: solving recurrences ------------------------------- The number a_n of mice in a certain population obeys the rule a_n=7*a_{n-1} - 10*a_{n-2} ("n" indicates the month counted from the start of the experiment. The first term comes from reproduction; the second term is due to natural death and the house cat). If a_0 is 2 and a_1 is 13, determine a_n. Question 5: rigid motions in the plane -------------------------------------- Suppose T is an affine transformation T(v)=A*v+b of the plane. You are given that T moves (2,3) to (0,3). Describe as much as possible T, A and b if T is a) a translation b) a rotation c) a reflection. How do the answers change if you are told in addition that (1,5) is a fixed point of T? Question 6: Markov chains ------------------------- Pavlov's dog is trained to live in a house with three rooms A, B and C. There are no doors to the outside, three doors between rooms A and B, two doors between rooms A and C, and one between rooms B and C. Each time a bell rings, the dog goes through a door to look for food in a neighboring room. The bells ring at regular intervals. What percentage of his life does an immortal dog spend in each room? Question 7: geometric distribution --------------------------------------- Suppose you flip a coin with p(H)=alpha, p(T)=1-alpha until you get a H, then you stop. The question is: if you repeat this experiment over and over again, what is the average of the number of times you have to flip? You will need to figure out what is the sample space, the random variable, and set up the expected value. And then it's a tricky bit of computing. The probability space with base set 1,2,3,... and p(i)=alpha*(1-alpha)^{i-1} is the "geometric distribution". Question 8: switching stations ------------------------------- This is a lesson on how discrete is different from continuous. The city of Happyville is aligned on a perfectly square street grid, going North-South and East-West. The main arteries of the grid are 1 mile apart each time. If drawn in an x-y-plane, the airport is at (1,8), the town hall at (6,7), the football stadium at (7,4) and the university at (2,1). The city plans to build a lightrail system connecting these four. The rail must go along main arteries of the grid. The graid may contain switching stations (where different trainlines come together) Each mile of rail costs 2 million $. Each switching station costs 1 million $. a) Determine the best number and location for the switching stations and compute the overall price. ("Best" means that the total rail network has minimal cost. That involves overall length of the network and cost of the switching stattions. There might be several optimal locations.) b) Now suppose your railways are allowed to go cross-country, do not have to go along the main arteries. Find out the cheapest network that has no switching station. c) See if you can lower the price in b) if you introduce one switching station at one of the main artery intersections. Question 9: Fibonacci relations ------------------------------- In this exercise we use the convention that F_0=1, F_1=1. a) Prove: the sum of the n-th and the (n+3)-rd Fibonacci number is double of the (n+2)-nd Fibonacci number. b) Prove: the Fibonacci number F_{5k-1} is always divisble by 5. Question 10: symmetries ------------------------- For the symmetry types D_5, D_6, Z_1 and Z_2 find both a natural object (plant, animal, mineral) and a man-made object (loge, gadget, consumer product) with that symmetry type. Question 11: Thinking --------------------- 10 pirates have been captured by the Good Guys. The chief Good Guy announces the following verdict: on the coming morning, all 10 pirates will be lined up facing East, one behind the other, ordered by size with the smallest up front and the tallest last. Then an assistant to the chief Good Guy will place one hat each (either red or blue) on the head of each pirate in such manner that the hat of any given pirate can only be seen by those pirates standing behind him. Then, starting with the tallest pirate, each pirate in order announces a color. If the color matches the one he wears, he goes free. If not, he is executed. (If any pirate tries to turn or cheat in other ways, all are executed). Question: assuming that the pirates have their wits together and can communicate over night, what number of pirates will certainly die, what number will certainly not die, and what number is expected to die (mathematically speaking).