6
$\begingroup$

I got this problem:

Given a $7\times 7$ grid, if we distribute $29$ disks on the grid such that each square cannot hold more than $1$ disk, what is the probability that there will be at least one row full of disks on the grid?

My first try:
$P(\{\text{there is at least one row full of disks}\}= \frac{7\times{42\choose 22}}{49\choose 29}$

Since we have $7$ ways to choose the row that we will fill by disks, and then we have remaining $22$ disks which we will distribute over the remaining $42$ squares. But this is obviously wrong since we count some combinations multiple times.

My second try:
$P(\{ \text{there is at least one row full of disks}\}= P(\{\text{there is exactly 1 row full of disks}\}\cup\{\text{there is exactly 2 rows full of disks}\}\cup\{\text{there is exactly 3 rows full of disks}\}\cup\{\text{there is exactly 4 rows full of disks}\})=P(\{\text{there is exactly 1 row full of disks}\}+P(\{\text{there is exactly 2 rows full of disks}\}+P(\{\text{there is exactly 3 rows full of disks}\}+P(\{\text{there is exactly 4 rows full of disks}\}$

But this probably makes things harder and does not simplifies things.

My third try:
$P(\{\text{there is at least one row full of disks}\}= 1-P(\{\text{there are no rows full of disks}\})$

But I got stuck, I tried to count the number of combinations in which each row got an empty square but here too I counted some combinations multiple times.

Any hint/help will be appreciated.

$\endgroup$

2 Answers 2

3
$\begingroup$

There are ${49\choose20}={49\choose29}$ equiprobable ways to choose the cells obtaining no disk, called empty cells in the following. Each such choice constitutes an arrangement.

We have to count the number $N$ of arrangements where at least one row contains no empty cell. For this count we need the the inclusion-exclusion-principle. It gives $$N={7\choose1}{42\choose 20}-{7\choose2}{35\choose 20}+{7\choose3}{28\choose 20}-{7\choose4}{21\choose 20}=3528443228520\ .\tag{1}$$ (As an example consider the number of arrangements with exactly three rows containing no empty cell. These are counted $3$ times in the first term of $(1)$, $-3$ times in the second term, and $1$ time in the third term.)

The probability $p$ in question is therefore given by $$p={N\over{49\choose20}}={3000376895\over24045516451}\doteq0.124779\ .$$

$\endgroup$
1
  • $\begingroup$ Thanks a lot for this answer. $\endgroup$
    – MathNerd
    Nov 9, 2014 at 16:43
0
$\begingroup$

One approach could be consider that there must be 20 empty squares one in each row if the condition is not satisfied.

Let Xi be the number of empty spaces in row i with 1<=i<=7 then each must be positive and in addition you must consider the number of permutations for each row of empty spaces.

This approach may not work well in general

A second approach could be recursive let r rows be full let A(r) be the number of ways of distributing the remaining points amoung the other rows such that there is atleast one empty point in each row.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.