balls and cells

142 Views Asked by At

For $n,k$ non-zero natural numbers we have $4n$ cells and $4k$ balls that are the same, and we need to fill the cells with the balls. in how many ways can we do that if we know that exist at least one pair of consecutive cells whose sum is even. we will mark the number of balls in the $i'th$ cell to be $x_i$. so the question means there exist some $1\le i\le 4n-1$ such that $x_i+x_{i+1}$ is even.

I tried to calculate the inverse which is all the options for $4k$ balls in $4n$ cells minus all the options where all the consecutive cells sum is odd which means we got even, odd, even, odd.. or odd, even, odd, even, and so on for all our cells but here I got stuck...

1

There are 1 best solutions below

0
On BEST ANSWER

Assume $n\leq k$ otherwise it will be trivial. We count the NOT satisfying cases first.

As stated in the question description, we will have $2n$ cells with each containing an odd number of balls, and similar for the even case.

We assign $1$ ball to each odd cell, and for the rest $4k-2n$ balls, we simply distribute them in shares of $2$ balls. By this result

Different approaches to N balls and m boxes problem

we know the number of combinations that do NOT hold is

\begin{align*} 2 \binom{2k+3n-1}{2k-n}\tag{1} \end{align*}

the $2$ factor is for reverse direction.

And the total number of distributions is

\begin{align*} \binom{4k+4n-1}{4k}\tag{1} \end{align*}

The answer will be their difference.