Q: Suppose that a computer science laboratory has 15 workstations and 10 servers. A cable can be used to directly connect a workstation
to a server. For each server, only one direct connection to that
server can be active at any time. We want to guarantee that at any
time any set of 10 or fewer workstations can simultaneously access
different servers via direct connections. What is the minimum number
of direct connections needed to achieve this goal?
This is an example from Rosen's Discrete Mathematics and Its Applications. The given solution to this example consists of 2 parts if I understood correctly.
The first part includes finding the number of connections like the following:
Suppose that we label the workstations $W_1, W_2, …, W_{15}$ and the
servers $S_1, S_2, …, S_{10}$. Furthermore, suppose that we connect
$W_k$ to $S_k$ for $k = 1,2, …, 10$ and each of $W_{11}, W_{12}$,
$W_{13}, W_{14}$, and $W_{15}$ to all 10 servers. We have a total of 60
direct connections.
Then I guess some kind of proof by contradiction is given to show that less than 60 connections is impossible.
Now suppose there are fewer than 60 direct connections between
workstations and servers. Then some server would be connected to at
most $\lfloor 59/10\rfloor= 5 $ workstations.(If all servers were
connected to at least six workstations, there would be at least $6.10$
$= 60$ direct connections.) This means that the remaining nine servers are not enough to allow the other 10 workstations to simultaneously
access different servers. Consequently, at least 60 direct connections
are needed.
But I can't understand this part. How is it concluded that remaining nine servers are insufficient when at most 59 connections are used?
Best Answer
I’m assuming that you understood why there must be a server connected to at most $5$ workstations if there are only $59$ direct connections.
There’s no harm in labelling the servers so that server $S_1$ is connected to $5$ or fewer workstations, and there’s no harm in assuming that the workstations to which $S_1$ is directly connected are among the last five, $W_{11},W_{12},W_{13},W_{14}$, and $W_{15}$, so that $S_1$ is not directly connected to any of the ten workstations $W_1,W_2,\ldots,W_{10}$. In other words, every direct connection from one of these ten workstations is to one of the nine servers $S_2,S_3,\ldots,S_{10}$. This means that the ten workstations $W_1,W_2,\ldots,W_{10}$ cannot simultaneously directly access all ten servers: none of them has a direct connection to $S_1$, so if they all directly access a server simultaneously, two of them must access the same server. This contradicts our guarantee that every set of ten (or fewer) workstations can simultaneously directly access all ten servers.