## 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
34.

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

800-503-530-233-251-701-710-413-440

```

-- RobbieMoll - 16 Oct 2006

Topic revision: r1 - 2006-10-16 - RobbieMoll    Copyright © 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