1. Limited time only! Sign up for a free 30min personal 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!

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