edited by
751 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. 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?

Please Explain in this question how pigeonhole principle is applied .
edited by

2 Answers

1 votes
1 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. 

edited 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

0 votes
0 votes
0 answers
1
0 votes
0 votes
1 answer
2
admin asked Apr 29, 2020
6,069 views
What is the minimum number of students, each of whom comes from one of the $50$ states, who must be enrolled in a university to guarantee that there are at least $100$ wh...
0 votes
0 votes
1 answer
3
admin asked Apr 29, 2020
4,038 views
Show that among any group of five (not necessarily consecutive) integers, there are two with the same remainder when divided by $4.$
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.