edited by
514 views
0 votes
0 votes

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?

. The given solution to this example consists of 2 parts 

The first part includes finding the number of connections like the following:

Suppose that we label the workstations W1,W2,...,W15 and the servers S1,S2,...,S10. Furthermore, suppose that we connect Wk to Sk for k=1,2,...,10 and each of W11,,W12,W13,W14 and W15 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 ⌊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 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?

edited by

2 Answers

Best answer
4 votes
4 votes

Objectives :

We want to guarantee that "at any time", "any set of 10 or fewer workstations" can simultaneously access different servers via direct connections while keeping minimum number of direct connections.

Constraint : 

"For each server", only one direct connection to that server can be active at any time.


Pigeon Hole Principle informally works as "Do bare minimum things" or "Uniformly Distribute first". Same Concept You can apply here.

You could take small numbers of Workstations and Servers and see What the Idea is behind Solving this question. Say, solve it for 6 Workstations and 3 Servers and check for any set of 3 or fewer workstations. This will give you the idea to Solve this Question for even more Workstations and Servers. 

To make Minimum number of Connections, first Connect Workstations W1 to W10 with Servers S1 to S10 in one to one manner as W1 with S1, W2 with S2, W3 with S3 and so on W10 with S10. Now, You have to connect Remaining Workstations (W11 to W15)  with All the Servers in One to All manner i.e. W11 with All Servers, W12 with All Servers and so on W15 with All Servers. If You are thinking that Why should we connect W11 to W15 workstations with All the servers, then read the Objective statement in the Question "We want to guarantee that at any time any set of 10 or fewer workstations can simultaneously access different servers via direct connections.

So, Let's assume that at least one workstation from W11 to W15 is Not connected to at least one Server. Say, W11 is Not connected to S1 by direct connection. Then You pick the set of Workstations $\{ W2, W3, W4,....,W11\}$, now, this set is of size $10$ and according to the objective Any Set of Workstations of Size less than or equal to 10 must be active at any point of time. But Since, "For each server", only one direct connection to that server can be active at any time, We will have that at least one of the workstations in the set $\{ W2, W3, W4,....,W11\}$ will Not be able to access the server. Which is a Contradiction to the objective. So, W11 to W15 have to be connected to All the Servers whereas $W_i$ in the set  W1 to W10 can only be connected to $S_i$ in the set $S1 \,\,to\,\,S10.$ 

So, the answer for the asked question will be = 10 connections (W1 to W10) +  5 * 10 connections (for  W11 to W15) = 60 Connections. Thus, Minimum 60 Connections to Guarantee that at any time any set of 10 or fewer workstations can simultaneously access different servers via direct connections. 

selected by
0 votes
0 votes
Server 1 Server 2 Server 3 Server 4 Server 5 Server 6 Server 7 Server 8 Server 9 Server 10
${\color{Red} W}{\color{Red} S{\color{Red} 1}}$ ${\color{Grey}W }{\color{Grey} S}{\color{Grey} 2}$ ${\color{Yellow} W}{\color{Yellow} S{\color{Yellow} 3}}$ ${\color{Brown} W}{\color{Brown} S{\color{Brown} 4}}$ ${\color{Cyan} W}{\color{Cyan} S{\color{Cyan} 5}}$ ${\color{Teal}W }{\color{Teal}S }{\color{Teal}6 }$  ${\color{DarkOrange}W }{\color{DarkOrange} S}{\color{DarkOrange} 7}$ ${\color{Golden} W}{\color{Golden}S }{\color{Golden} 8}$ ${\color{Orchid} W}{\color{Orchid}S }{\color{Orchid} 9}$ ${\color{Emerald} W}{\color{Emerald} S}{\color{Emerald} 1}{\color{Emerald} 0}$
${\color{Green} W}{\color{Green} S}{\color{Green} 1}{\color{Green} 1}$ ${\color{Green} W}{\color{Green} S}{\color{Green} 1}{\color{Green} 1}$ ${\color{Green} W}{\color{Green} S}{\color{Green} 1}{\color{Green} 1}$ ${\color{Green} W}{\color{Green} S}{\color{Green} 1}{\color{Green} 1}$ ${\color{Green} W}{\color{Green} S}{\color{Green} 1}{\color{Green} 1}$ ${\color{Green} W}{\color{Green} S}{\color{Green} 1}{\color{Green} 1}$ ${\color{Green} W}{\color{Green} S}{\color{Green} 1}{\color{Green} 1}$ ${\color{Green} W}{\color{Green} S}{\color{Green} 1}{\color{Green} 1}$ ${\color{Green} W}{\color{Green} S}{\color{Green} 1}{\color{Green} 1}$ ${\color{Green} W}{\color{Green} S}{\color{Green} 1}{\color{Green} 1}$
${\color{Blue}W}{\color{Blue}S}{\color{Blue} 1}{\color{Blue} 2}$ ${\color{Blue}W}{\color{Blue}S}{\color{Blue} 1}{\color{Blue} 2}$ ${\color{Blue}W}{\color{Blue}S}{\color{Blue} 1}{\color{Blue} 2}$ ${\color{Blue}W}{\color{Blue}S}{\color{Blue} 1}{\color{Blue} 2}$ ${\color{Blue}W}{\color{Blue}S}{\color{Blue} 1}{\color{Blue} 2}$ ${\color{Blue}W}{\color{Blue}S}{\color{Blue} 1}{\color{Blue} 2}$ ${\color{Blue}W}{\color{Blue}S}{\color{Blue} 1}{\color{Blue} 2}$ ${\color{Blue}W}{\color{Blue}S}{\color{Blue} 1}{\color{Blue} 2}$ ${\color{Blue}W}{\color{Blue}S}{\color{Blue} 1}{\color{Blue} 2}$ ${\color{Blue}W}{\color{Blue}S}{\color{Blue} 1}{\color{Blue} 2}$
${\color{Magenta} W}{\color{Magenta} S}{\color{Magenta} 1}{\color{Magenta} 3}$ ${\color{Magenta} W}{\color{Magenta} S}{\color{Magenta} 1}{\color{Magenta} 3}$ ${\color{Magenta} W}{\color{Magenta} S}{\color{Magenta} 1}{\color{Magenta} 3}$ ${\color{Magenta} W}{\color{Magenta} S}{\color{Magenta} 1}{\color{Magenta} 3}$ ${\color{Magenta} W}{\color{Magenta} S}{\color{Magenta} 1}{\color{Magenta} 3}$ ${\color{Magenta} W}{\color{Magenta} S}{\color{Magenta} 1}{\color{Magenta} 3}$ ${\color{Magenta} W}{\color{Magenta} S}{\color{Magenta} 1}{\color{Magenta} 3}$ ${\color{Magenta} W}{\color{Magenta} S}{\color{Magenta} 1}{\color{Magenta} 2}$ ${\color{Magenta} W}{\color{Magenta} S}{\color{Magenta} 1}{\color{Magenta} 2}$ ${\color{Magenta} W}{\color{Magenta} S}{\color{Magenta} 1}{\color{Magenta} 2}$
${\color{Purple} W}{\color{Purple}S }{\color{Purple}1 }{\color{Purple} 4}$ ${\color{Purple} W}{\color{Purple}S }{\color{Purple}1 }{\color{Purple} 4}$ ${\color{Purple} W}{\color{Purple}S }{\color{Purple}1 }{\color{Purple} 4}$ ${\color{Purple} W}{\color{Purple}S }{\color{Purple}1 }{\color{Purple} 4}$ ${\color{Purple} W}{\color{Purple}S }{\color{Purple}1 }{\color{Purple} 4}$ ${\color{Purple} W}{\color{Purple}S }{\color{Purple}1 }{\color{Purple} 4}$ ${\color{Purple} W}{\color{Purple}S }{\color{Purple}1 }{\color{Purple} 4}$ ${\color{Purple} W}{\color{Purple}S }{\color{Purple}1 }{\color{Purple} 4}$ ${\color{Purple} W}{\color{Purple}S }{\color{Purple}1 }{\color{Purple} 4}$ ${\color{Purple} W}{\color{Purple}S }{\color{Purple}1 }{\color{Purple} 4}$
${\color{Orange}W }{\color{Orange}S}{\color{Orange} 1}{\color{Orange}5 }$ ${\color{Orange}W }{\color{Orange}S}{\color{Orange} 1}{\color{Orange}5 }$ ${\color{Orange}W }{\color{Orange}S}{\color{Orange} 1}{\color{Orange}5 }$ ${\color{Orange}W }{\color{Orange}S}{\color{Orange} 1}{\color{Orange}5 }$ ${\color{Orange}W }{\color{Orange}S}{\color{Orange} 1}{\color{Orange}5 }$ ${\color{Orange}W }{\color{Orange}S}{\color{Orange} 1}{\color{Orange}5 }$ ${\color{Orange}W }{\color{Orange}S}{\color{Orange} 1}{\color{Orange}5 }$ ${\color{Orange}W }{\color{Orange}S}{\color{Orange} 1}{\color{Orange}5 }$ ${\color{Orange}W }{\color{Orange}S}{\color{Orange} 1}{\color{Orange}5 }$ ${\color{Orange}W }{\color{Orange}S}{\color{Orange} 1}{\color{Orange}5 }$

SOLUTION :-

$\rightarrow$ We have $15$ work stations and $10$ servers.

$\rightarrow$ Select $10$ WorkStations ( $WS$ ) and then connect them with $1$ server each like  ${\color{Red} W}{\color{Red} S{\color{Red} 1}}$ to Server1 $,  ${\color{Grey}W }{\color{Grey} S}{\color{Grey} 2}$ to Server 2$,  ${\color{Yellow} W}{\color{Yellow} S{\color{Yellow} 3}}$ to Server 3 and so on.

$\rightarrow$ So total Workstations  ( WS ) selected till now $= 10$ and in each server we have $1$ Workstation connected and is active.

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.

$\rightarrow$ This means that we should always try that 10 workstations are active and running. However if say 7 workstation are not active i.e. only 8 work station are running then that that is not our fault because we have only 15 work sations available.

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Now suppose ${\color{Red} W}{\color{Red} S{\color{Red} 1}}$ which is connected to server 1 that connection is not active

$\rightarrow$ This means that only 9 work stations are active and are accessing the servers.

$\rightarrow$ so in place of   ${\color{Red} W}{\color{Red} S{\color{Red} 1}}$'s connection we  could activate connection of  ${\color{Green} W}{\color{Green} S}{\color{Green} 1}{\color{Green} 1}$ or  ${\color{Blue}W}{\color{Blue}S}{\color{Blue} 1}{\color{Blue} 2}$ or  ${\color{Magenta} W}{\color{Magenta} S}{\color{Magenta} 1}{\color{Magenta} 3}$ or ${\color{Purple} W}{\color{Purple}S }{\color{Purple}1 }{\color{Purple} 4}$ or ${\color{Orange}W }{\color{Orange}S}{\color{Orange} 1}{\color{Orange}5 }$ .

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

$\rightarrow$  SImilarly we can repeat the above step for workstations ${\color{Grey}W }{\color{Grey} S}{\color{Grey} 2}$,  ${\color{Yellow} W}{\color{Yellow} S{\color{Yellow} 3}}$ , ${\color{Brown} W}{\color{Brown} S{\color{Brown} 4}}$ , ${\color{Cyan} W}{\color{Cyan} S{\color{Cyan} 5}}$ , ${\color{Teal}W }{\color{Teal}S }{\color{Teal}6 }$ , ${\color{DarkOrange}W }{\color{DarkOrange} S}{\color{DarkOrange} 7}$, ${\color{Golden} W}{\color{Golden}S }{\color{Golden} 8}$, ${\color{Orchid} W}{\color{Orchid}S }{\color{Orchid} 9}$ and ${\color{Emerald} W}{\color{Emerald} S}{\color{Emerald} 1}{\color{Emerald} 0}$ in case they are not active.

$\rightarrow$ For doing this we have to connect each of  ${\color{Green} W}{\color{Green} S}{\color{Green} 1}{\color{Green} 1}$ or  ${\color{Blue}W}{\color{Blue}S}{\color{Blue} 1}{\color{Blue} 2}$ or  ${\color{Magenta} W}{\color{Magenta} S}{\color{Magenta} 1}{\color{Magenta} 3}$ or ${\color{Purple} W}{\color{Purple}S }{\color{Purple}1 }{\color{Purple} 4}$ or ${\color{Orange}W }{\color{Orange}S}{\color{Orange} 1}{\color{Orange}5 }$  with all the servers.

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

$\because$ We need $1$ connection for each of  ${\color{Red} W}{\color{Red} S{\color{Red} 1}}$ , ${\color{Grey}W }{\color{Grey} S}{\color{Grey} 2}$,  ${\color{Yellow} W}{\color{Yellow} S{\color{Yellow} 3}}$ , ${\color{Brown} W}{\color{Brown} S{\color{Brown} 4}}$ , ${\color{Cyan} W}{\color{Cyan} S{\color{Cyan} 5}}$ , ${\color{Teal}W }{\color{Teal}S }{\color{Teal}6 }$ , ${\color{DarkOrange}W }{\color{DarkOrange} S}{\color{DarkOrange} 7}$, ${\color{Golden} W}{\color{Golden}S }{\color{Golden} 8}$, ${\color{Orchid} W}{\color{Orchid}S }{\color{Orchid} 9}$ and ${\color{Emerald} W}{\color{Emerald} S}{\color{Emerald} 1}{\color{Emerald} 0}$ and $10$ connections for each of  ${\color{Green} W}{\color{Green} S}{\color{Green} 1}{\color{Green} 1}$ or  ${\color{Blue}W}{\color{Blue}S}{\color{Blue} 1}{\color{Blue} 2}$ or  ${\color{Magenta} W}{\color{Magenta} S}{\color{Magenta} 1}{\color{Magenta} 3}$ or ${\color{Purple} W}{\color{Purple}S }{\color{Purple}1 }{\color{Purple} 4}$ or ${\color{Orange}W }{\color{Orange}S}{\color{Orange} 1}{\color{Orange}5 }$

$\therefore$ Total connections required  $= 10 + (5*10) = 60.$

Related questions

1 votes
1 votes
1 answer
1
himgta asked Feb 24, 2019
1,709 views
Show that every sequence of $n^2$+1 distinct real numbers contains a subsequence of length n+1 that is either strictly increasing or strictly decreasing.
0 votes
0 votes
0 answers
3
1 votes
1 votes
1 answer
4
tusharp asked Jul 5, 2018
1,701 views
I am not getting this condition. Can someone please explain that condition with that example.