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?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.