There are $2n+1$ identical books to be put in a bookcase with three shelves. In how many ways can this be done if each pair of shelves together contains more books than the other shelf?

My Approach:

Let $x_1$ = number of books on shelf $1$,

$\quad$ $x_2$ = number of books on shelf $2$

$\quad$ $x_3$ = number of books on shelf $3$

We are given that $x_1+x_2>x_3$, $x_2+x_3>x_1$, $x_1+x_3>x_2$ and $x_1+x_2+x_3=2n+1$

Substitute $a=x_1+x_2-x_3$, $b=x_2+x_3-x_1$ and $c=x_1+x_3-x_2$, to get

$a,b,c>0$ and $a+b+c=2n+1$

This is just the strong composition

So, the answer is $\binom{2n+1-1}{3-1}=\binom{2n}{2}$

But the answer at the back of my book is $\binom{n+1}{2}$. Where did I go wrong?

Note: This is not a duplicate question as it explicitly asks for verification of proof.


Notice that when you say that you are looking for any $a,b,c>0$ with $a+b+c =2n+1$, we know that something must have gone wrong, since we know that every shelf must contain at least one book (otherwise we immediately violate the constraint) and hence we know that $x_1,x_2,x_3>0$ with $x_1+x_2+x_3=2n+1$ ... which is just like the $a,b,c$, ... except that obviously the constraint will constrain $x_1,x_2,x_3$ much more than just them being greater than 0.

OK, but where did you go wrong? Well, you consider $a=2$ and $b=1$ to be part of a possible solution, but then:

$x_1 + x_2 -x_3 = a = 2$

$x_2 + x_3 - x_1 = b = 1$

And so (subtract):

$2x_1 - 2x_3 = 1$

And thus:

$x_1 - x_3 = \frac{1}{2}$

... I think you can see the problem now ...

  • $\begingroup$ So if there are 5 books, $(a,b,c)=(2,1,2)$, how does your example relate to this? $\endgroup$ – Joffan Feb 14 '17 at 3:15
  • $\begingroup$ @Joffan The $(a,b,c) = (2,1,2)$ triple would represent the 'solution' $(x_1,x_2,x_3)=(2,1.5,1.5)$ ... which is not a solution ... $\endgroup$ – Bram28 Feb 14 '17 at 3:21
  • $\begingroup$ Right, so in effect you are saying that since $a=(2n+1)-2x_1$, $a$ (and $b$ and $c$) must be odd. $\endgroup$ – Joffan Feb 14 '17 at 3:33

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.