0
$\begingroup$

One lays down a deck of $52$ cards face up on a $4 \times 13$ array .One tries to select $13$ cards one from each column with different denominations (not necessarily of different suites)

Find the probability that the selection is possible. Justify your answer I am getting $\frac{4^{13}}{\binom{52}{13}}$.

Don't know wrong or right please help

$\endgroup$
9
  • $\begingroup$ It's hard to help if you don't explain how you got your answer. $\endgroup$
    – saulspatz
    Mar 7, 2018 at 16:26
  • $\begingroup$ When you said 52 cards in 4 x 13 array, Are you arranging it in certain way or does this choice belongs to us????? $\endgroup$
    – NewGuy
    Mar 7, 2018 at 16:29
  • $\begingroup$ I have 4 possible choices for every 13 denominations which is the numerator $\endgroup$ Mar 7, 2018 at 16:30
  • $\begingroup$ The choice is random, at least from what I read. $\endgroup$ Mar 7, 2018 at 16:30
  • $\begingroup$ The choice belongs to the person dealing the cards $\endgroup$ Mar 7, 2018 at 16:30

1 Answer 1

3
$\begingroup$

This is always possible, by Hall's Marriage Theorem. The problem is a bipartite matching problem, with one set being the ranks, and the other set being the columns. There is an edge between a given rank and a given column if and only if the column contains a card of that rank. We seek a complete matching, that is, a set of edges such that each vertex is on exactly one of them.

Given a set $S$ of $r$ ranks, let $s$ be the number of columns that contain a card of at least one of the ranks in $S$. We cannot have $s < r$ for there are $4r$ cards of the given ranks, and only $4s < 4r$ cards in the columns of $S$. By Hall's Marriage Theorem, there exists a complete matching, which proves the theorem.

So the probability is 1. I wonder what the expected number of solutions is?

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .