How Many Ways Can a Postman Deliver 4 Wrong Letters to 4 Houses?

[kashan123999]

Homework Statement

A notorious postman delivered 4 letters to four houses in such a way that no house will get the correct letter...in how many ways he delivered the letter ? Please explain it

Homework Equations

I think this is permutation question...using fundamental law of counting

The Attempt at a Solution

I don't know where to start,i think they can be delivered in 7 ways cause first letter will be delivered in 3 ways,because 1 house is correct..after that 2nd letter can be arranged in 2 ways...3rd and 4th in 1 1 way..so 3+2+1+1=7 ways...

 

[Fredrik]

Are you sure you're supposed to be adding those numbers?

 

[CAF123]

The first letter can be delivered to the first house in 3 ways, as you noted. However depending on what this letter is, there may or may not be 2 choices for the second house. For example, denote the four houses by A,B,C,D and their correct letters by a,b,c,d. If we have b going to house A, then we have 3 choices for the letter in B. While if we have,say, c in A, then we can only have two choices for B(a and d).

 

[Fredrik]

Ah, I didn't notice that. Here's a slightly different way of looking at it. Let's say that he delivers the letters a,b,c,d in alphabetical order. There are 3 houses where he can leave a. If he leaves a at B, there are now 3 houses where he can leave b. But if he leaves a at C or D, there are now only 2 houses where he can leave b.

 

[lurflurf]

There are only 24 permutations, it might be instructive to write them all out. Another approach is to consider that there are three choices for the first slot (ie 2,3,4 not one), one can go any where else (ie slot 2,3,4 not one) but where ever 1 goes determines where the other numbers go. So each choice is a choice of what slot one goes in and what goes in slot one so it is easy to see the possibilities.

 

[kashan123999]

so what is the answer?

 

[Ray Vickson]

so what is the answer?

Forum rules require you to work that out for yourself. You have received several hints, and that should be sufficient.

 

[agoogler]

so what is the answer?

As lurflurf said , write all the choices. It might take some time but it is a good way to understand problems like this.

 

[TimeToShine]

How about you try and find the probability that the postman does deliver to the right house? This should be basic enough. Subtract your answer from 1, and use this to compare to your answer using permutations.

 

[Ray Vickson]

How about you try and find the probability that the postman does deliver to the right house? This should be basic enough. Subtract your answer from 1, and use this to compare to your answer using permutations.

That won't work: he wants the number of permutations in which every element is in the wrong place, but your method will get him the number in which at least one (hence at least two) are in the wrong place. The OP wants to find the number if derangements, although he may not know that.

 

[lurflurf]

!4
done!
Why didn't we do that sooner?
We can do {delivers all to wrong houses}={all}-{delivers to the right house)
delivers to the right house in this case means at least one letter.
As you point out we cannot have 3 right
so we have
{0 right}={all}-{4 right}-{2 right}-{1 right}

Summary of Methods suggested
A)
pick one slot ie 1
choose which what to put there (in 1)
chose where to put what was there before (where 1 goes)
B)
!4
done!
C)
{0 right}={all}-{4 right}-{2 right}-{1 right}
D)
Enumerate (write out or draw) all possibilities