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?

x1 = number of books on shelf 1, x2 = number of books on shelf 2, x3 = number of books on shelf 3

I have the following inequalities:

a+b > c

a+b+c > 2c (don't understand where this one comes from)

2n+1 > 2c

c < n+ (1/2)

c is an integer, so c =< n. Same for a, and b.

=> a+b+c = 2n+1, where 0 =< a, b, c =< n

At this point, I don't know how to finish the computation of the number of integral solutions. The answer is (n+1) choose (2).

I would have thought that r = 2n+1, and k = 3, so the answer would have been: (2n+3) choose (2).

  • $\begingroup$ $a+b+c\gt 2c$ comes from adding $c$ to each side of $a+b \gt c$ $\endgroup$ – Ross Millikan Sep 21 '11 at 19:16

"each pair of shelves together contains more books than the other shelf" is equivalent to "each shelf holds less than half the books" (at most $n$ books). Let $\{s_i\}_{i=1}^3$ be the number of books on each shelf. For each choice of $s_1$ and $s_2$ so that $s_1+s_2<n+1$, we would need $s_3>n$. For each $s_1+s_2\ge n+1$, we have $s_3=2n+1-(s_1+s_2)\le n$. Thus, we need to count the number of $s_1,s_2\le n$ so that $s_1+s_2\ge n+1$. For $s_1=1$, there is $1$ choice for $s_2$ (i.e. $n$). For $s_1=2$, there are $2$ choices (i.e. $n$ and $n-1$). This continues up to $s_1=n$, where there are $n$ choices for $s_2$. Therefore, the number of arrangements is $1+2+\dots+n=\binom{n+1}{2}$.

  • $\begingroup$ So the answer is not n+1 choose 2? $\endgroup$ – Gbean Sep 21 '11 at 15:01
  • $\begingroup$ @Gbean $\binom{n+1}{2}$ stands for $n+1$ choose 2. See binomial coefficient wikipedia article. $\endgroup$ – Sasha Sep 21 '11 at 15:29

A more natural and shorter approach that uses only the lower bounds for the equation

$$a+b+c = 2n+1$$ is next:

You can count all of the solutions to the equation when there is no restriction and then, using the subtraction principle, remove those solutions when there's a shelf with more than $n$ books on it(this would mean that the other two shelves have $\leq n$ books on them).

The equation when there are more than $n$ books on shelf $a$ is

$$a + b + c = 2n + 1, \\a \geq n + 1,\: b \geq 0,\: c \geq 0\: .$$

The number of solutions to this equation is $\dbinom{n + 2}{2}$.

But, one must notice that this number only counts the situation when there are more books on shelf $a$, in order to account for the other shelves the number should be multiplied by 3.

The final solution is $$\dbinom{2n+3}{2} - 3\dbinom{n + 2}{2} = \dbinom{n + 1}{2}$$


a+b+c>2c comes from multiplying the previous inequality by 2.

There are (n+1)choose(2) combinations of a,b because 0<=a,b<=n. For each of these possibilities there is exactly one 0<=c<=n such that a+b+c=2n+1.

  • $\begingroup$ Suppose $a=0$ and $b=0$, what would $c$ be? $\endgroup$ – robjohn Sep 21 '11 at 14:48
  • $\begingroup$ Does that mean that c = 2n+1? $\endgroup$ – Gbean Sep 21 '11 at 14:52
  • $\begingroup$ @Gbean: it would need to be, but that is too big for $c$. $\endgroup$ – robjohn Sep 21 '11 at 14:59
  • $\begingroup$ How is it too big for c? $\endgroup$ – Gbean Sep 21 '11 at 15:20
  • $\begingroup$ @Gbean: "each pair of shelves together contains more books than the other shelf". If $c=2n+1$ and $a=0$ and $b=0$ we have $a+b\le c$ instead of $a+b>c$ as the problem requires. $\endgroup$ – robjohn Sep 21 '11 at 17:52

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.