Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Forming pairs problem

  1. Jun 14, 2010 #1
    1. The problem statement, all variables and given/known data

    Suppose we have two decks with n distinct cards each. After we shuffle the decks, what is the probability that k cards are in the same position in the two decks?

    2. Relevant equations



    3. The attempt at a solution
    I have worked out that when n tends to infinity, the probability that 0 cards are in the same position is 1/e but I am having a lot of difficulties with the combinatorics aspect of the problem. Hope you guys could help me with that!
    Thanks!
     
  2. jcsd
  3. Jun 14, 2010 #2

    lanedance

    User Avatar
    Homework Helper

    i would start with k=1 first & see how you go
     
  4. Jun 14, 2010 #3

    lanedance

    User Avatar
    Homework Helper

    and maybe even one deck - always helps me to start simple, then generalise from there
     
  5. Jun 14, 2010 #4

    lanedance

    User Avatar
    Homework Helper

    you'll also have to decide if k cards means "only k cards" or "at least k cards"
     
  6. Jun 14, 2010 #5
    Thanks for the answer lanedance. First of all, the answer I am looking for is only k, and I dont see how this problem would make sense with only one deck, as the most important aspect of it are two cards in the same position.... I am still stuck....
     
  7. Jun 14, 2010 #6
    Let's say there are 4 cards, we are looking for 3 cards.

    positions:
    1 2 3 4
    1st deck.
    1 2 3 4
    1 2 4 3
    1 3 2 4
    1 3 4 2
    1 4 2 3
    1 4 3 2
    2 1 3 4
    2 1 4 3
    2 3 1 4
    2 3 4 1
    2 4 1 3
    2 4 3 1
    3 1 2 4
    3 1 4 2
    3 2 1 4
    3 2 4 1
    4 1 2 3
    4 1 3 2
    4 2 1 3
    4 2 3 1

    So if you shuffle the deck so that the cards are in this order:

    2 1 3 4

    Then for 2 cards to be same you need:

    2 1 3 4
    2 1 4 3
    2 4 3 1
    2 3 1 4
    4 1 3 2
    3 1 2 4
    1 2 3 4

    total of 7. so the probability is 7/16

    To get the things much clear. Let's say there are 5 cards. You need two cards two match:

    2 1 3 4 5

    2 1 . . . 3*2*1
    2 . 3 . . 2*2+2*2
    2 . . 4 . 2*2+1
    2 . . . 5 1+1

    . 1 3 . . 2*2+2*2
    . 1 . 4 . 2*2+1
    . 1 . . 5 1+1

    . . 3 4 . 2*2+1
    . . 3 . 4 1+1

    . . . 4 5 1+1
    -------------
    total: 1*(2*2+2*2+2*2) +2*(2*2+2*2)+3*(2*2+1)+4*(1+1)=45

    So the probability is 45/5!

    I hope you can follow this pattern and find a formula.

    Regards.
     
    Last edited: Jun 14, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook