GATE CS 2021 Set 1 Q19 — Combinatorics: Counting, Recurrence Relations, Generating Functions

Let the $6$ jobs ordered by increasing difficulty be $J_1, J_2, J_3, J_4, J_5, J_6$, where $J_1$ is the easiest and $J_6$ is the toughest.

Let the $3$ computers ordered by increasing speed be $C_{ ext{slow}}, C_{ ext{med}}, C_{ ext{fast}}$.

According to the given conditions:

1. The fastest computer ($C_{ ext{fast}}$) must get the toughest job ($J_6$).
2. The slowest computer ($C_{ ext{slow}}$) must get the easiest job ($J_1$).

This pre-assigns $J_1$ to $C_{ ext{slow}}$ and $J_6$ to $C_{ ext{fast}}$. Now, both $C_{ ext{slow}}$ and $C_{ ext{fast}}$ already have at least one job assigned to them.

We have $4$ remaining jobs ($J_2, J_3, J_4, J_5$) to be distributed among the $3$ computers such that the remaining condition is satisfied: Every computer gets at least one job.

Since $C_{ ext{slow}}$ and $C_{ ext{fast}}$ already have jobs, this condition is satisfied as long as the medium computer ($C_{ ext{med}}$) gets at least one of the remaining $4$ jobs.

We can calculate this using the subtraction principle:

• Total ways to assign the $4$ remaining jobs to the $3$ computers without restriction: $$3^4 = 81$$
• Invalid ways where $C_{ ext{med}}$ gets $0$ jobs (i.e., the $4$ jobs are distributed only between $C_{ ext{slow}}$ and $C_{ ext{fast}}$): $$2^4 = 16$$

Therefore, the number of valid ways is: