GATE CSE 2021 Set 1 | Question: 19

Question

There are $6$ jobs with distinct difficulty levels, and $3$ computers with distinct processing speeds. Each job is assigned to a computer such that:

• The fastest computer gets the toughest job and the slowest computer gets the easiest job.
• Every computer gets at least one job.

The number of ways in which this can be done is ___________.

Comments

Why is it 3^4? As we cannot assign the same jobs to two different computers?? Where am I getting it wrong??

---

same doubt

---

@amitarp818 here we are given 6 jobs - suppose named 1,2,3,4,5,6 and their value represents their toughness(higher value = tougher) so computer 1 will definitely get job 6 and computer 3 will get 1 . remaining 4 jobs will be distributed between these 3 computers . if we count total cases of distributing 4 jobs to 3 computers they come as 3^4 and we subtract 2^4 from them cuz all the computers get at least one job.

Answer 1

Let $C_1$ be the fastest and $C_3$ be the slowest computers.

These two are assigned two jobs. Now out of the remaining $4$ jobs we need to ensure $C_2$ gets at least $1.$ Without this constraint we can assign $4$ jobs to $3$ computers in $3^4=81$ ways. Out of these $81$ ways $2^4=16$ will be having no jobs for $C_2.$

So, number of possible ways so that $C_2$ gets at least one job $=81-16=65.$

Comments

@rohan.ladhar  bro the total number is 6 and since 2 are already mapped hence im only mapping rest 4

---

What should be the generalized approach to solve this question?

I solved this question using “Distribution o Distinct objects without restriction”

but this gives some redundant distribution.

---

Those who are thinking why it’s, “ Out of these 81 ways 2^4=16 will be having no jobs for C2.” is because each of the 4 jobs have only two options : either go to C1 or go to C3 [because they can’t go to C2].

Answer 2

First let me assume that the computers are $C_1,C_2,C_3$ having computing power in the increasing order as shown below:

And let me assume that the jobs are $J_1,J_2,J_3,J_4,J_5.J_6$ with increasing difficulty level as shown below:

Now as per the condition “The fastest computer gets the toughest job and the slowest computer gets the easiest job.” the situation is as follows:

Which means that $J_1$ is assigned to $C_1$ and $J_6$ is assigned to $C_3$.

Now note the second condition: “Every computer gets at least one job.”

Based on the above condition, at least one of the jobs $J_2,J_3.J_4,J_5$ must be assigned to $C_2$, or else $C_2$ computer shall remain vacant!!!

Now to calculate the number of ways in which at least one of $J_2,J_3.J_4,J_5$ is assigned to $C_2$, we find the all ways in which the above $4$ jobs can be assigned to computers and from that we subtract the cases in which no job is assigned to $C_2$.

The total number of possible ways= $3^4 =81$ [As each of the above $4$ jobs in the yellow bubble can be assigned to either computer $C_1,C_2,C_3$]

The number of ways in which in the above $4$ jobs are assigned only to $C_1$ or $C_3$=$2^4$ =16[as each of the jobs has $2$ choices]

So required number=$81-16=65$

Comments

how 3^4 came?

---

We’ve 4 distinct jobs remaining and we have to distribute them to 3 CPUs. This is an order partition so each job has 3 choices to go to cpu1,cpu2, cpu3. same for job2,3 and 4. So 3*3*3*3 = 3^4.

---

Just amazing and appreciate the time taken in illustrating this.

Answer 3

According to given conditions, we have to find number of onto function with certain condition (i.e., The fastest computer gets the toughest job and the slowest computer gets the easiest job.),

Therefore, we have remaining 4 jobs to assign these 3 computer such that Every computer gets at least one job.

Since, fasted and slowest computer has already atleast one-one job, we assigned.
Only Computer with medium speed has no job yet, so we need to remove combination of with no job in Computer with medium speed.

Therefore,
= $3^4$ – 1*$(3-1)^4$
= 81 – 16
= 65

Comments

formula is wrong.. m^n – mC1(m-1)^n + mC2(m-2)^n-…

= 3^4 – (3C1)(2^4) + (3C2)(1^4)

= 36

which is not the answer.. so

---

This formula can’t be used here because in this it is not necessary to map all the elements of set A with set B, since fastest and slowest computers already have been assigned jobs. This is exactly not onto type but seems like onto.

We have to use the formula :

Total functions- Number of functions not onto

= $3^4-2^4$

=65

These 2^4=16 cases are those cases which won’t be onto because all the four jobs have been assigned to fastest or slowest computer and the medium speed computer has no job assigned.