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