GateAI
Combinatorics

GATE CSE 2021 Set 1 · Q19

NAT1 markMedium

Time

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

Your answerNumerical answer

Enter a value to check

Solution

Step-by-step verified solution

Official answer: 65

Combinatorics

Let the 3 distinct computers be:

  • C1C_1: fastest computer

  • C2C_2: medium-speed computer

  • C3C_3: slowest computer

Let the 6 distinct jobs ordered by difficulty be J1,J2,J3,J4,J5,J6J_1, J_2, J_3, J_4, J_5, J_6, where J1J_1 is the toughest and J6J_6 is the easiest.

  1. Fixed Assignments:

    • J1J_1 must be assigned to C1C_1.

    • J6J_6 must be assigned to C3C_3.

    • Because of this, both C1C_1 and C3C_3 already have at least one job.

  2. Remaining Jobs:

    • There are 44 remaining jobs: {J2,J3,J4,J5}\{J_2, J_3, J_4, J_5\}.

    • Each of these 44 jobs can be independently assigned to any of the 33 computers (C1,C2,C3C_1, C_2, C_3).

    • Total unrestricted assignments for the 44 jobs = 34=813^4 = 81.

  3. Condition that every computer gets at least one job:

    • Since C1C_1 and C3C_3 already have at least one job, we only need to ensure that C2C_2 gets at least one job.

    • The invalid cases are those where C2C_2 gets 00 jobs (i.e., all 44 jobs are assigned only to C1C_1 or C3C_3).

    • Number of such invalid assignments = 24=162^4 = 16.

  4. Total Valid Assignments:

    Number of ways=34−24=81−16=65\text{Number of ways} = 3^4 - 2^4 = 81 - 16 = 65

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Combinatorics previous year question is Q19 of the GATE CSE 2021 Set 1 paper. Find more GATE CSE PYQs on Combinatorics in Engineering Mathematics, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Combinatorics PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Combinatorics in GATE CSE

Combinatorics has 19 GATE CSE PYQs across 15 papers from 2012 to 2025. 5 of them are 1-mark NAT questions like this one, and it is the only one in GATE CSE 2021 Set 1.

How GATE tests Combinatorics

More from GATE CSE 2021 Set 1

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2021 Set 1 · Q19 · NAT

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 …

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.