I was going through my Discrete Mathematics (Discrete Mathematics and Its Applications by Kenneth Rosen) textbook when I came across this problem.
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. Although we could do this by connecting every workstation directly to every server (using 150 connections), what is the minimum number of direct connections needed to achieve this goal?
I tried to understand what the question was telling us to find, however, I face some issues in understanding the statement, "We want to guarantee that at any time any set of 10 or fewer workstations can simultaneously access different servers via direct connections."
Then, I peeked at the solution to get a better understanding of the question. The solution says:
Suppose that we label the workstations $W_1$, $W_2$, ... , $W_{15}$ and the servers $S_1$, $S_2$, ... , $S_{10}$. First, we would like to find a way for there to be far fewer than 150 direct connections between workstations and servers to achieve our goal. One promising approach is to directly connect $W_k$ to $S_k$ for $k$ = 1,2,...,10 and then to connect each of $W_{11}$, $W_{12}$, $W_{13}$, $W_{14}$, and $W_{15}$ to all 10 servers. This gives us a total of 10 + 5 ⋅ 10 = 60 direct connections. We need to determine whether with this configuration any set of 10 or fewer workstations can simultaneously access different servers. We note that if workstation $W_j$ is included with 1 ≤ $j$ ≤ 10, it can access server $S_j$, and for each workstation $W_k$ with $k$ ≥ 11 included, there must be a corresponding workstation $W_j$ with 1 ≤ $j$ ≤ 10 not included, so $W_k$ can access server $S_j$. (This follows because there are at least as many available servers $S_j$ as there are workstations $W_j$ with 1 ≤ $j$ ≤ 10 not included.) So, any set of 10 or fewer workstations are able to simultaneously access different servers.
But can we use fewer than 60 direct connections? Suppose there are fewer than 60 direct connections between workstations and servers. Then some server would be connected to at most ⌊59∕10⌋ = 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 for the other 10 or more workstations to simultaneously access different servers. Consequently, at least 60 direct connections are needed. It follows that 60 is the answer.
I don't recall the number of times I've read the solution but each time I read it, I couldn't understand the logic behind each step. Moreover, I couldn't understand why 10 direct connections from each workstation to server plus 5 direct connections for the remaining workstations to any server (resulting in a total of 15 connections) was the answer. If anybody has a simpler way to express the same solution or alternate solutions, that would be highly appreciated.
Where did you get this "15 connections" concept? The problem clearly states that the solution has 60 connections, not 15.
The 10 servers $W_1$ through $W_{10}$ each have only one connection: $W_i$ is connected to $S_i$. This gives $10$ connections total. But the remaining five workstations are each connected to every server, not just one server. That means 10 connections for each of the five workstations, for $50$ connections. Adding in the original $10$ connections, this gives $60$ connections total, not $15$.
For any group $G$ of ten workstations, you can break $G$ up into two subsets: $$G_s = \{W_i : W_i \in G\text{ and }i \le 10\}\\G_a = \{W_i : W_i \in G\text{ and }i > 10\}$$ If there are $k$ workstations in $G_s$, then there are $10 - k$ workstations in $G_a$. Each workstation in $G_s$ will occupy a specific server, so those $k$ servers are not available for the workstations in $G_a$. But that still leaves $10 - k$ servers that are unused by the workstations in $G_s$. So you can just choose any pairing of those $10-k$ servers with the $10 - k$ workstations in $G_a$. So the condition that any group of $10$ workstations can access distinct servers is satisfied.
Conversely, if there are fewer than $60$ connections, then as noted at least one of the servers is connected to five or fewer workstations. Thus you can pick a set of ten workstations none of which are connected to this particular server. But that means that this set of workstations are connected to at most nine servers. So they cannot access $10$ distinct servers. Thus no set of $59$ or fewer connections can meet the access condition. Which means $60$ is the minimum.