6,825 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 ___________.

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

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

@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].

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

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.

1
5,751 views