Telegraphic Answers to Homework Assignment Five

1. 3.1.2 21

2. 3.1.18  use the fact that if c1 and c2 are centers, 
and b1 and b2 are leaves that witness for the 
respective longest paths, and c1->b1 and c2->b2 are 
the same lengths, then c2 must lie on c1->b1, and 
visa versa. Then a third center must also fall along 
the same line, and the center in the middle would be 
better than the others.

3. 3.1.24 n cans = n entrants.  One can used per game. 
And one can left over at the end of the final match.

4. 3.1.26 L= 5**6, I = (5**6-1)/4, n-1 = num of edges = 
num of stamps = m*I = 5*(5**6-1)/4. Multiply this by 

5. 3.1.28 (a) 20 coins require 3 weighings; (b) base: 3 coins, 1 weighing;
induction step: divide into 3 equal groups. One weighing identifies which group 
has the light coin, and by induction that group requires n-1 weighings.

6. 3.1.30 no picture..

7. 3.2.6 Need to show that such a set of vertices must be connected (and thus will 
be a spanning tree). If not connected, then look at connected components. Each of 
these must be a spanning tree, and thus each has k-1 edges in a component with k 
vertices. But then there are n-j edges altogether, where j is the number of 
components. But j is 1 by assumption, and so the original set of edges must be a 
spanning tree.

8. 3.2 - 16-a


-- RobbieMoll - 16 Oct 2006

Topic revision: r1 - 2006-10-16 - RobbieMoll
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UMass CS EdLab? Send feedback

mersin escort adana escort izmir escort gaziantep escort