# [SOLVED] In how many ways can (2n + 1) identical balls be placed?

• May 27th 2009, 09:39 AM
fardeen_gen
[SOLVED] In how many ways can (2n + 1) identical balls be placed?
In how many ways can (2n + 1) identical balls be placed in 3 distinct boxes so that any two boxes together will contain more balls than the third?
• Jun 4th 2009, 03:29 PM
the_doc
Turns out to be quite simple!
Here's how to solve it:

Spoiler:

The wording of this question is quite subtle. It ask for us to count the number of ways that the balls can be put in the box such that any two boxes have more balls than the third.

I assume the question refers to using all the balls i.e. no ball can be left outside a box.

Hence in order for this requirement to be fulfilled no single box can have more than half the balls i.e. since there are $2n + 1$ balls in total the maximum number of balls we can place in any single box must be $n$. It should be easy to see that this guarantees the requirement is fulfilled.

Now let's call the three distinct boxes $A$, $B$ and $C$ and the respective number of balls placed in each $N_A$, $N_B$ and $N_C$.

If we start by placing a ball in $A$ then $B$ and $C$ must have $n$ balls each i.e. using the notation

$(N_A ,N_B , N_C)$

to signify the different configurations we have that when $N_A = 1$ the configuration must be

$(1,n,n)$

and this is the only possible configuration for $N_A = 1$ since exchanging a ball from $B$ to $C$ would result in $N_B > n$ and vice versa.

Now it should be easy to see that when we have $N_A = k$ ( $k \le n$) one configuration we have is

$(k,n+1-k,n)$

and we can make $k-1$ exchanges from $C$ to $B$ so in total (including the above configuration) we have $k$ configurations of the balls when $N_A = k$ .

Hence the total number of configurations, $N_c$, is given by

$N_c = \sum_{k=1}^{n} k$

So using the well known result for this arithmetic progression we have that

$\color[rgb]{0,0,1} \boxed{N_c =\frac{1}{2} n (n+1)}$.