The zoo director's face was green with anger. The new animal guard had put some of the wild animals in the wrong cages. "Bring them back in the right cages" ordered the director, "but take care that at no time two animals are in the same cage." (see: "99 Logeleien von Zweistein", Hamburg 1968)
Note that between adjacent cages there are doors. You can move the animals by going with the mouse over a full cage (thereby catching the animal) and moving it to an adjacent free cage (dragging it to the new cage). Note also that moving a tiger takes usually 10 minutes, whereas moving a fox takes only 1 minute. The number of steps and minutes used so far can be seen below the picture. To the right is the desired final configuration.
If you like this kind of game, try also a related one where you can even automatically find best solutions to move animals.


a) How many ways are there to distribute the animals on the cages? Note that the two tigers, as well as the three foxes are indistinguishable.
b) Now consider the (huge) graph who has all these configurations in (a) as vertices. Twi such configurations are adjacent in the graph if one can be derived from the other in one move. Why do we get an undirected graph in this way?
c) What is the degree (in this graph in (b)) of the initial configuration (which only shows after reloading, make sure to print this configuration since it changes whenever you move the mouse over the picture)
d) What is the maximum degree of the graph in (b)?
e) What is the shortest cycle in the graph obtained in (b)?
f) Use Breadth First Search to find all configurations (vertices of the graph in (b)) that have distance 2 to the vertex of the initial configuration.
g) In how many steps can you transform the initial configuration into the final configuration shown to the right?
h) What is the shortest time needed (remember: 10 minutes for each tiger move, 1 minute for each fox move) to transform the initial configuration into the final configuration shown to the right? If you cannot show that your method is optimal, list it to me anyway for partial credit.
i) Show that the diameter of the graph in (b) is larger than 4!
a) Find a large (12 vertices or more) graph with diameter 3 where each vertex has degree at most 3.
b) (Challenge, Extra Credit) Show (convince me) that there is no graph of diameter 3 with 54 vertices where each vertex has degree smaller or equal than 4.
Go back to Project # 5.