\problemdata                                                             
        {Connectivity} % latex-friendly label for the prob.
        {counting, induction} % The topic(s) of the problem content.  
        {} % Source (if known)                                          
        {S01 Final, 15} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
MIT Information Services wants to put together a new computer cluster
involving $n$ computers.  They want to connect these computers to each
other with wires and a collection of hubs.  Each computer must have
exactly one wire attached to it, while each hub can have up to five
wires attached.  I.S. wants to minimize the number of hubs used to
build this network, in which every pair of computers must be connected
by a path of wires and hubs.

\begin{problemparts}
\problempart Supposing that I.S. uses $m$ hubs, what is the maximum
number of wires that can be attached to the hubs and computers without
leaving dangling ends?

\solution{ $(5m+n)/2$.}


\problempart Again supposing that I.S. uses $m$ hubs, and momentarily
ignoring the restriction on the number of wires that may be attached
to a hub, what is the minimum necessary number of wires needed to
connect all the computers and hubs to each other (such that there is a
path along the wires and hubs between any two hubs or computers?

\solution{ $m+n-1$.}


\problempart  Compare the previous two quantities to prove that at
least $\lceil \frac{n-2}{3}\rceil$ hubs are needed to hook up
the network.


\solution{ Algebra on the previous two parts.}

\problempart Prove by induction that $\lceil \frac{n-2}{3}\rceil$
hubs are sufficient to build the desired network (The previous part
shows this result is tight).

\solution{ The theorem is true for $n=1$ (no wires needed), for
  $n=2$ (connect directly to each other), and $n=3$ (use one hub in
  the obvious way).  To prove the theorem for $n>3$, consider an
  optimum network on $n-3$ computers; it used $\lceil
  \frac{n-2}{3}\rceil - 1$ hubs by induction.  Take some computer on
  this network, and replace it with a hub.  This decrease the number
  of computers by 1 and adds one hub with 4 unused connections.
  Attach 4 computers to these connections.  Overall we have added one
  hub and three computers (removed one and added four).  This proves
  the inductive step.}


\end{problemparts}
\end{problem}                 

