Five letters are to be placed into five addressed envelopes.If the let

Number of derangement if there are total n objects \(= n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+..........+(-1)^n \frac{1}{n!})\)

Number of ways in which none of the letters put in its corresponding envelope
\(= 5!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}) \)

\(= 120(\frac{1}{2} - \frac{1}{6} +\frac{1}{24} - \frac{1}{120})\)

\(= \frac{120}{120} (60-20+5-1)\)

=44

This is a case of derangement(Nothing is in the right envelope)

Number of ways so that none of the letters is in its corresponding envelope = n! (1 - 1/1! + 1/2! -1/3! + .....(-1)^n/n!)

n here is 5 and hence

5! (1 - 1/1! + 1/2! - 1/3! + 1/4! -1/5!)

= 120 (1/2 - 1/6 + 1/24 -1/120)

= 44

(option a)

D.S
GMAT SME
_________________

No, you'd literally never need the derangement formula on the GMAT. As soon as you have 5 or more objects, derangement problems become extremely complicated, and the GMAT would never test something like that. I have seen one official question (and only one, among several thousand questions) that tested derangements, but in that question there were only four objects, and in a situation like that you can solve the problem just using basic principles, with no need of a formula.
_________________

You calculated "1 letter is placed correctly" wrong

Suppose ABCDE is the right order

Number of ways to put only A in the right place

i)When B is at 3rd place - ACBED, ADBEC, AEBCD

ii)When B is at 4th place - ACEBD, ADEBC, AEDBC

iii) When B is at 5th place - ACEDB, ADECB, AEDCB

There are total 9 ways (Not 3)


2) 1 letter is placed correctly = 5C1*9 = 45


Total no. of ways in which none of the letters are placed correctly = 120 - (1+45+20+10+0) = 44 ways

Logic is not correct at all, that's why it's working for only few cases.


If we put only first 2 letter in correct envelopes, that doesn't mean that we have 2 options for each of the remaining spots (If it were, then our answer would be 2*2*2=8 not 2) , because filling each spot is dependent on other in this question.(We need inclusion-exclusion principle to calculate)

Suppose ABCDE is the correct order. Let's see the cases in which only AB is at correct place.


Case 1- when C is at 4th place - ABECD (1 arrangement)
Case 2- when C is at 5th place- ABDEC (1 arrangement)

Total possible arrangements 1+1=2(right way to solve it)

Since there is only 1 arrangement possible in each case, that false logic works(2*1).If the arrangements are more than 1 in each case, then this logic fails(as in the following case.)

Suppose ABCDE is the right order

Number of ways to put only A in the right place

i)When B is at 3rd place - ACBED, ADBEC, AEBCD

ii)When B is at 4th place - ACEBD, ADEBC, AEDBC

iii) When B is at 5th place - ACEDB, ADECB, AEDCB

We have 3 arrangements possible in each case. (total possible arrangements is 3+3+3, not 3*1)


If you still have any doubt, you can ask.

None of the letters should be placed in it's right envelope.

This means that for the first envelope, I have 4 wrong letters to choose from and then for the second envelope, I have 3 wrong letters to choose from. For the third envelope, I have only 2 wrong letters & then for the last two, I have only one way, I can place it wrongly.

So, it is 4*3*2*1 = 24.

Why is the answer 44. Where am I going wrong ?

Bunuel can you please help ?

The problem is actually a lot more complicated than it might first seem. You could begin, as you did, by saying "I have four wrong letters for the first envelope". Then when you move on to the second envelope, it's true that you often have only three 'wrong' letters you could use. But what if you put the second envelope's letter in the first envelope? Then you have 4 letters left, and they're all 'wrong' for the second envelope. So sometimes you have 3 choices for the second envelope, and sometimes you have 4. You'd normally need, at least in a simpler problem, to divide the question into cases when this happens, but the case analysis in derangement problems like this one can get thorny, which is why the solutions above use a formula (that you'll never need on the GMAT).
_________________

Hello,

Here is a short conceptual video to help you with solving such questions on the GMAT.

The concept of derangements taught in 5 minutes.



Hope this helps.

Thanks.



_________________

To find the no. of cases in which none of the letters are placed in their corresponding envelopes, we have to subtract all the cases when at least one of the letter is correctly placed from the total no. of cases.
No letter is placed correctly = Total - (all letters are placed correctly) - (1 letter is placed correctly) - (2 letters are placed correctly) - (3 letters are placed correctly) - (4 letters are placed correctly)

Lets say there are letters La, Lb, Lc, Ld, Le and their corresponding envelopes Ea, Eb, Ec, Ed, Ee respectively.
Total no. of ways to assign each letter to its corresponding address = 5! = 5*4*3*2*1 = 120

1) All letters are placed correctly
All letters have 1 corresponding envelope. So each letter can be placed correctly in only 1 way.

2) 1 letter is placed correctly
Let’s first select the one letter out of 5 that must be put in its correct envelope. This can be done in 5C1 = 5 ways.
If 1 letter is placed correctly, we have to arrange remaining 4 letters in 4 envelopes such that they are not placed in their corresponding envelopes. Say La is placed in Ea. Now Lb cannot go into Eb. So Lb has remaining 3 envelopes as options. Similarly, Lc has remaining 3 options. Thus, all the remaining 4 letters each has 3options for envelopes such that they all are incorrectly placed.
Total ways in which 1 letter is placed correctly = 5*3 = 15

2) 2 letters are correctly placed
2 correctly placed letters can be selected in 5C2 = 10 ways
We have to place remaining 3 letters in 3 envelopes incorrectly. Since each letter cannot go in their respective addressed envelope, each letter has 2 options of envelopes (Since the third envelope would be their correct envelope).
Total no. of ways 2 letters are correctly placed = 10*2 = 20

3) 3 letters are correctly placed
3 correctly placed letters can be selected in 5C3 = 10 ways
We have to place remaining 2 letters in 2 envelopes incorrectly. Since each letter cannot go in their respective addressed envelope, each letter has just 1 option of envelope to go in(Since the other envelope would be their correct envelope).
Total no. of ways 3 letters are correctly placed = 10*1 = 10

4) 4 letters are correctly placed
This case is impossible since if 4 letters are put correctly in their envelopes, the last letter has to go in its designated envelope. So no. of ways = 0

Total no. of ways in which none of the letters are placed correctly = 120 - (1+15+20+10+0) = 74 ways

Where am I going wrong?

Hi Nick,
Could you please explain why the logic here is not working? The same procedure works for the other scenarios, I'm unable to arrive at 5*9 using the logic that works for the other scenarios.

@nick816
are we supposed to remember this formula for the gmat

Now, I got what is missed. Thank you

But, I am still puzzled how could there not be a simpler way to solve this without using the formula.

Best to do this by subtracting the number of cases where any letter is inserted correctly from total cases.

Total ways is 5!= 120

Any correct = All correct+4 correct+3 correct+2 correct+1 correct

All correct is 1 case, but 4 correct is indistinguishable from all correct, so 1 case

For 3 correct, there are 5!/3!2!= 10 ways to select which 3. There are two ways to insert the remaining two letters but only one is correct, leaving one incorrect way, so a total of 10*1=10 ways.

For 2 correct there are 5!/2!3!=10 ways to select which 2.

For the remaining 3 to be inserted incorrectly, there are only two ways to insert a letter incorrectly, in which case the other two have only one way. Here is where drawing a diagram will help you visualize.

So a total of 10*2=20 ways.

There are 5!/1!4!=5 ways to select which letter gets placed correctly in the final case with the other 4 incorrectly.

So a preliminary count is:


120-[1+10+20+5(All 4 incorrect)] =

89 - 5[All 4 incorrect]


Unfortunately, determining how many ways the remaining 4 are placed incorrectly requires that the process above be repeated, viz:

Total ways - [All correct+3 correct+2 correct+1 correct]

So starting with 4!=24 ways

All correct and 3 correct are the same, 1 way.

Two letters to be inserted correctly can be selected

4!/2!2! = 6 ways

The remaining two letters can be inserted incorrectly just 1 way, so a total of 6*1=6 ways.

One letter to be inserted correctly can be selected

4!/3!1!= 4 ways. The three letters to be inserted incorrectly are 2 ways, seen from the discussion above, for a total of 4*2= 8 ways

So the 4 letters can be inserted incorrectly

24-[1+6+8] = 9 ways

These 9 are then applied to the preliminary count above:

89-5[9] = 89-45 = 44 ways

Posted from my mobile device

D(5)=5!(1/0!-1/1!...1/4!-1/5!)= 5k-1 format

Only 44 holds true