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

1. ## [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?

2. ## 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 $\displaystyle 2n + 1$ balls in total the maximum number of balls we can place in any single box must be $\displaystyle n$. It should be easy to see that this guarantees the requirement is fulfilled.

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

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

$\displaystyle (N_A ,N_B , N_C)$

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

$\displaystyle (1,n,n)$

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

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

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

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

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

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

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

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