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? Prove that anything less than this number is inadequate as well. If possible, apply the pigeonhole principle.

Explanation / Answer

In our problem, 15 workstations and 10 servers we have...

At a time .. 10 workstations are directly connected by servers... But we don't know which 10 out of 15 are directly connected... So rest 5 are free... So we connect these 5 workstations to all 10 stations because we need gurantee connection between all the workstations..

So firstly 10 direct connections...

Then 5 *10 = 50 connections ...

So total number of 60 connections required to achieve this goal with gurranty.

Any doubt then comment below..

If less than 60 then problem is face....

Let us assume there are 59 direct connections....

And we have 10 servers name A1,A2,A3 ,....,A10... this implies that by pigenhole principal... There is 1 server which have 5 connections.... let it is A1... So A1 have 5 direct connections...

We have 15 work stations naming as B1 , B2 , ..... , B15....

For simplifications let A1 is connected to first five workstations B1 , B2, B3 , B4 , B5 by direct connections.....

So remaining we have 9 servers and 10 workstations.....so it implies that remaining 10 workstations connected directly toh 9 servers.... This is contradiction because it is given that 10 workstations is direclty connected with different signal....

Our assumptions is wrong....

So less than 60 not possible

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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