3
$\begingroup$

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).

  • 0
    $a+b+c\gt 2c$ comes from adding $c$ to each side of $a+b \gt c$2011-09-21

3 Answers 3

5

"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, 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}$.

  • 0
    @Gbean $\binom{n+1}{2}$ stands for $n+1$ choose 2. See binomial coefficient wikipedia [article](http://en.wikipedia.org/wiki/Binomial_coefficient).2011-09-21
4

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}$

1

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.

  • 0
    @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.2011-09-21