Sign in
12thPass logo
New chatPYQ LibraryDoubtsRank report
Sign in to see Recents

Your guest activity stays on this device

Sign in to save progress →
Sign in

Permutations and Combinations question

2014 · Shift 2 · Q30
Guest · filters and generic practice availableBrowsing as a guest · PYQ filters and generic practice are available. Sign in only for personalised features and saved progress.
  1. PYQ Library
  2. /JEE Advanced
  3. /Mathematics
  4. /Permutations and Combinations
  5. /2014 · Shift 2 · Q30

Permutations and Combinations question

2014 · Shift 2 · Q30

JEE AdvancedMathematicsPermutations and CombinationsMCQ+3 / −1
Six cards and six envelopes are numbered 1, 2, 3, 4, 5, 6 and cards are to be placed in envelopes so that each envelope contains exactly one card and no card is placed in the envelope bearing the same number and moreover the card numbered 1 is always placed in envelope numbered 2. Then the number of ways it can be done is
  1. A
    264
  2. B
    265
  3. C
    53
  4. D
    67
View written solutionFree

Correct answer: C

Problem Analysis

We are given six cards (C1 to C6) and six envelopes (E1 to E6). We need to place one card in each envelope subject to three conditions:

  1. Each envelope contains exactly one card.
  2. No card is placed in the envelope with the same number, i.e., card CiC_iCi​ cannot be in envelope EiE_iEi​ for any iextfrom1to6i ext{from 1 to 6}iextfrom1to6. This is a derangement problem.
  3. Card C1 is always placed in envelope E2. This is an additional constraint.

Let's find the number of ways to satisfy all these conditions.

Step-by-step Solution

  1. Apply the fixed condition: The condition that card C1 is always placed in envelope E2 is fixed. So, we place C1 in E2. Now, we are left with 5 cards: {C2, C3, C4, C5, C6} and 5 envelopes: {E1, E3, E4, E5, E6}.

  2. Formulate the remaining problem: We need to place the remaining 5 cards into the remaining 5 envelopes such that the derangement condition (CiotinEiC_i otin E_iCi​otinEi​) is met for all applicable cards. The remaining conditions are:

    • C2otinE2C_2 otin E_2C2​otinE2​ (This is automatically satisfied since E2 is already occupied by C1).
    • C3otinE3C_3 otin E_3C3​otinE3​.
    • C4otinE4C_4 otin E_4C4​otinE4​.
    • C5otinE5C_5 otin E_5C5​otinE5​.
    • C6otinE6C_6 otin E_6C6​otinE6​. So, the problem reduces to: Find the number of ways to place cards {C2, C3, C4, C5, C6} into envelopes {E1, E3, E4, E5, E6} such that C3otinE3C_3 otin E_3C3​otinE3​, C4otinE4C_4 otin E_4C4​otinE4​, C5otinE5C_5 otin E_5C5​otinE5​, and C6otinE6C_6 otin E_6C6​otinE6​.
  3. Use a case-based approach on the placement of Card C2: We analyze the placement of card C2, as it's the only card whose forbidden envelope (E2) is not in the available set of envelopes. The envelope E1 is special because its forbidden card (C1) is not in the set of cards we are placing.

    Case 1: Card C2 is placed in envelope E1.

    • We have placed C1 in E2 and C2 in E1.
    • The remaining cards are {C3, C4, C5, C6}.
    • The remaining envelopes are {E3, E4, E5, E6}.
    • The conditions are that CiotinEiC_i otin E_iCi​otinEi​ for iextfrom3to6i ext{from 3 to 6}iextfrom3to6.
    • This is a classic derangement problem of 4 items. The number of ways is denoted by D4D_4D4​.
    • The formula for the number of derangements of nnn items is Dn=n!∑k=0n(−1)kk!D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}Dn​=n!∑k=0n​k!(−1)k​.
    • D4=4!(12!−13!+14!)=24(12−16+124)=12−4+1=9D_4 = 4! \left(\frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!}\right) = 24 \left(\frac{1}{2} - \frac{1}{6} + \frac{1}{24}\right) = 12 - 4 + 1 = 9D4​=4!(2!1​−3!1​+4!1​)=24(21​−61​+241​)=12−4+1=9.
    • So, there are 9 ways in this case.

    Case 2: Card C2 is NOT placed in envelope E1.

    • We need to place cards {C2, C3, C4, C5, C6} into envelopes {E1, E3, E4, E5, E6}.
    • The restrictions are:
      • C2otinE1C_2 otin E_1C2​otinE1​
      • C3otinE3C_3 otin E_3C3​otinE3​
      • C4otinE4C_4 otin E_4C4​otinE4​
      • C5otinE5C_5 otin E_5C5​otinE5​
      • C6otinE6C_6 otin E_6C6​otinE6​
    • This is equivalent to finding a bijection (a one-to-one mapping) π\piπ from the set of cards SC={2,3,4,5,6}S_C = \{2, 3, 4, 5, 6\}SC​={2,3,4,5,6} to the set of envelopes SE={1,3,4,5,6}S_E = \{1, 3, 4, 5, 6\}SE​={1,3,4,5,6} such that π(2)≠1\pi(2) \neq 1π(2)=1, π(3)≠3\pi(3) \neq 3π(3)=3, π(4)≠4\pi(4) \neq 4π(4)=4, π(5)≠5\pi(5) \neq 5π(5)=5, π(6)≠6\pi(6) \neq 6π(6)=6.
    • Let's relabel envelope E1 as E2. Now we are mapping cards from SC={2,3,4,5,6}S_C = \{2, 3, 4, 5, 6\}SC​={2,3,4,5,6} to the relabeled set of envelopes SE′={2,3,4,5,6}S'_E = \{2, 3, 4, 5, 6\}SE′​={2,3,4,5,6}. The conditions become π(i)≠i\pi(i) \neq iπ(i)=i for all i∈{2,3,4,5,6}i \in \{2, 3, 4, 5, 6\}i∈{2,3,4,5,6}.
    • This is exactly the problem of deranging 5 items. The number of ways is D5D_5D5​.
    • D5=5!(12!−13!+14!−15!)=120(12−16+124−1120)=60−20+5−1=44D_5 = 5! \left(\frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!}\right) = 120 \left(\frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120}\right) = 60 - 20 + 5 - 1 = 44D5​=5!(2!1​−3!1​+4!1​−5!1​)=120(21​−61​+241​−1201​)=60−20+5−1=44.
    • So, there are 44 ways in this case.
  4. Calculate the total number of ways: The total number of ways is the sum of the ways from the two mutually exclusive cases. Total ways = (Ways in Case 1) + (Ways in Case 2) Total ways = D4+D5=9+44=53D_4 + D_5 = 9 + 44 = 53D4​+D5​=9+44=53.

Alternative Method (using derangement recurrence)

This problem is equivalent to finding the number of derangements of nnn items where item 1 is mapped to item 2. Let this be AnA_nAn​. The argument in Step 3 is a proof for the recurrence relation An=Dn−1+Dn−2A_n = D_{n-1} + D_{n-2}An​=Dn−1​+Dn−2​. We also know the standard recurrence for derangements: Dn=(n−1)(Dn−1+Dn−2)D_n = (n-1)(D_{n-1} + D_{n-2})Dn​=(n−1)(Dn−1​+Dn−2​). From these two relations, we can see that An=Dnn−1A_n = \frac{D_n}{n-1}An​=n−1Dn​​. For this problem, n=6n=6n=6. The number of ways is A6=D66−1=D65A_6 = \frac{D_6}{6-1} = \frac{D_6}{5}A6​=6−1D6​​=5D6​​. First, calculate D6D_6D6​: D6=5(D5+D4)=5(44+9)=5(53)=265D_6 = 5(D_5 + D_4) = 5(44 + 9) = 5(53) = 265D6​=5(D5​+D4​)=5(44+9)=5(53)=265. Then, the required number of ways is 2655=53\frac{265}{5} = 535265​=53. This confirms the result.

Conclusion

The total number of ways to place the cards according to the given conditions is 53. This corresponds to option C.

PreviousNext

More from Permutations and Combinations

  • Consider the set of eight vectors V={ai^+bj^​+ck^:a,b,c∈{−1,1}}. Three non-coplanar vectors can be chosen from v in 2p ways. Then p is2013 · Numerical
  • The total number of ways in which 5 balls of different colours can be distributed among 3 persons so that each person gets at least one ball is2012 · MCQ
  • Let an​ denote the number of all n-digit positive integers formed by the digits 0, 1 or both such that no consecutive digits in them are 0.Let bn​= the number of such n-digit integers ending with digit 1 and cn​=the…2012 · MCQ
  • Let an​ denote the number of all n-digit positive integers formed by the digits 0, 1 or both such that no consecutive digits in them are 0.Let bn​= the number of such n-digit integers ending with digit 1 and cn​ =the…2012 · MCQ
  • The number of seven digit integers, with sum of the digits equal to 10 and formed by using the digits 1, 2 and 3 only, is2009 · MCQ
  • Let (x,y,z) be points with integer coordinates satisfying the system of homogeneous equation: 3x−y−z=0−3x+z=0−3x+2y+z=0​ Then the number of such…2009 · Numerical
  • Consider all possible permutations of the letters of the word ENDEANOEL. Match the Statements/Expressions in Column I with the Statements/Expressions in Column II. Includes table2008 · MCQ
  • Let the set of all relations R on the set {a,b,c,d,e,f}, such that R is reflexive and symmetric, and R contains exactly 10 elements, be denoted by S. Then the number of elements in S is ​…2025 · Numerical