Suppose that a computer science laboratory has 15 workstations and 10 servers. A

Question

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? I understand the answer is 60 but I'm confused how the pigeonhole principle specifically applies. Identify where and how the pigeonhole principle applies and why at most 5 workstations per server is unacceptable.

Explanation / Answer

1) First we need to ensure that an any point in time up to 10 workstations must be directly connected to servers .

We connect 10 workstations to 10 servers using 10 direct connections.

But the 10 workstations at any time can come from any of the 15, but the direct connections are available only by a select 10.The 5 extra workstations should have connections to all the servers as we dont know which of the ten direct connections is free hence we must each of the extra five workstations should be connected to all the servers that is 5*10 =50 connections more. Hence we get a total of 10+50 = 60 connections.

We have 15 workstations and we are selecting 10 at a time out of them. We also have 10 workstations connected to the servers already.So after 5 workstations the 6th one requesting a server must be a directly connected one.So the pigeons are the workstations that need a server and the pigeonholes are the workstations that are not directly connected to the server.

5 workstations per server implying for 15 workstations you use only 3 servers but you need to be able to handle 10 requests hence you need 10 servers to work with.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.