4,790 views

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 ___________.

@Zxy123 i had also solved the same way you did.

The reason why the answer given by @Zxy123 is wrong is that it has lots of redundant counting involved.

Because when suppose you distribute job-2 to C2 (Job-1 being the hardest given to C1 and job-6 being the easiest given to C3.). And then distribute rest of the 3 jobs in $3^{3}$ ways, then suppose we distribute the 3 jobs such that J3 & J4 are given to C1, and J5 to C2. Then this will be recounted when we initially allot J5 to C2 and then distribute rest of the 3 jobs in $3^{3}$ ways.

So the point to be Noted is that:

Whenever you select only few objects from the group to distribute among the boxes and then again decide to distribute the left over objects to the same set of boxes then there is a chance of redundant counting.

Please note that the answer is obtained by assuming “a single job can be assigned to multiple computers”.

If it is the case that, “a single job can be assigned to a single computer”, then answer would be $\binom{4}{1} \times \binom{3+3-1}{3} = 40$

edited
this formula only used for when jobs are same and computer are different

but  in this case jobs are different okkk

### Subscribe to GO Classes for GATE CSE 2022

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.$
by

Sir, I think this question is asking for number of Onto mappings from process set to computer sets (as all are distinct) provided that easiest process and most difficult process is already mapped to slowest and fastest computers respectively.Hence we need to map only 4 distinct  process to 3 distinct computers

$3^{4} - _{1}^{3}\textrm{C} * 2^{4} + _{2}^{3}\textrm{C} * 1^{4} = 81 - 48 +3 = 36$

A similar question was also asked in GO test series(number of ways to distribute properties question). Kindly verify this.

reshown
Out of 6 jobs 3 are already assigned. So we are remaining with 3 jobs only. Those 3 jobs can be assigned to 3 computers in 5C3 ways.i,e 10 ways
@Sherringford: There is no requirement to map every computers here. So, it is not an onto mapping. If this step is wrong, all further calculation become a waste :)
@Sherringford: its onto mapping but already given in the question that two jobs are already assigned to two computers then no need to assign the jobs to them with compulsion.
@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.

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$

by

perfect!

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

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.