1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cards and envelopes permutation problem

  1. May 4, 2015 #1
    1. The problem statement, all variables and given/known data
    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
    264
    265
    53
    67

    2. Relevant equations
    There are many permutations formulas. Some say to learn it not telling the reason behind it.

    3. The attempt at a solution
    I think here some formula is applicable of degenerate theorem of permutation but what is the intuition behind it?
    It is better to analyse a formula before applying it anywhere.
     
  2. jcsd
  3. May 4, 2015 #2

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Hello Raghav.

    No general formulas here.

    But your part so far has only been to reproduce the problem statement.
    No equations, no effort. Just some musing. Not good enough by PF standards ! And I know you can do better !

    You'll have to do some thinking !
     
  4. May 4, 2015 #3
    Okay,
    So since card 1 is placed in envelope number 2. It is fixed,
    so we have 5 envelopes and 5 cards left in which we can do some arrangements.
    Envelopes are 1, 3,4,5,6
    And cards 2,3,4,5,6.
    Now same card can't go in same envelope and one envelope must contain one card.
    Suppose we put 2 card in 1 envelope, then 3rd in 4 etc. so many cases!
    Also nCr = n!/(n-r)!r!
     
  5. May 4, 2015 #4

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Very good. Card 1 into envelope 1 can only be done 1 way.

    You have an equation that tells you the number nCr of ways to make a group of size r from n items.
    You can learn it by heart or you can understand it:
    For the first member of the group you have n choices
    For the 2nd member of the group you have n-1 choices
    For the 3rd member of the group you have n-2 choices
    ...
    For the r th member of the group you have n-r + 1 choices

    Product is n!/(n-r)!
    But you have overcounted by the number of ways to order r items, so a factor 1/r!​
    But in this exercise you only put one card in one envelope, so not much use for your formula !?!

    Number of ways to order your five remaining cards is only 5! Which already eliminates half of your answer options!
    There are more conditions to fulfil, so 120 isn't one of the answers (but 67 + 53 = 120 !!!).

    For the rest of the cards, card #2 can go in five places, but the others can't go into their own envelope, only in four places.

    So there's a distinction between #2 in envelope 1 and #2 in one of the other envelopes. Those last four should each give the same number of possibilities, so you only have to find that number for e.g. #2 in envelope 3. Still work, but not that much any more. And who knows, you discover a smarter way !

    (I cheated, so I know the answer now...)
     
  6. May 4, 2015 #5
    Yeah, there was a pattern.
    When I place #2 in 1st envelope I get 9 ways.
    When I place #2 in other envelopes for example in 3 , I get 11 ways. Now placing that in 4 we will get same ways, till 6th envelope. So 4*11 = 44.
    Total ways = 44 + 9 = 53.
    Thanks BvU. ( You have been helpful to me in many threads ).
    Now how we can apply it to larger number of cards?
    And what was your cheating?
     
  7. May 4, 2015 #6

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Well done !
    I think a larger number of cards would be just as messy.
    My cheating was that I simply made the list of 120 numbers (in Excel ?:) ) and checked which ones qualified and which ones didn't ....
    There's even a name for that method: it's called brute force :wink:
     
  8. May 4, 2015 #7

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    This is an example of a derangement. You can apply the principle of inclusion and exclusion.
    Forget the '1 goes in 2' constraint for the moment.
    The total permutations are n! From that, we need to subtract those where 1 goes in 1, (n-1)!, and similiarly for 2 in 2 etc., giving n!-(n-1)!n. But we've subtracted the 1 in 1 and 2 in 2 twice, so we need to add those back in, and similarly the other pairs: +(n-2)!*n(n-1)/2. Continuing this process we get n!-n!+n!/2!-n!/3!..... = n!(1/0!-1/1!+1/2!-1/3!...1/n!). In the limit, that tends to n!/e. Note that if we take it to be exactly n!/e then the error is O(1/n), so we can cheat by simply rounding n!/e to the nearest integer. For n=6, 264.8 or so rounds to 265.

    Now to bring in the 1 goes in 2 constraint. I'll pose that as an exercise: what does that constraint do to the 265?
     
  9. May 5, 2015 #8
    I'm not understanding this proof correctly.In that bold part how we have subtracted 1 in 1 and 2 in 2 twice?
     
  10. May 5, 2015 #9

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I subtracted all perms in which card 1 ends up in envelope 1, and all perms in which card 2 ends up in envelope 2. So any perm in which both of those happen has been subtracted twice.
    Google principle of inclusion and exclusion.
     
  11. May 5, 2015 #10
    Okay.
    Now when we have put 1 in 2 constraint, the 5 more cases are gone.
    So total ways = 265/5 = 53.
    Thanks.
     
  12. May 5, 2015 #11

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Bravo Haru ! Very elegant and much more scalable than a brute force approach. I fell for the attractive reduction by a factor of 6 far too early and it became messy. Much better to postpone as you did. Awesome.:smile:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Cards and envelopes permutation problem
  1. Cards problem (Replies: 1)

  2. Permutations Problems (Replies: 1)

  3. Permutation Problem (Replies: 2)

  4. Permutations problem (Replies: 2)

Loading...