Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
$a+b+c\gt 2c$ comes from adding $c$ to each side of $a+b \gt c$ –  Ross Millikan Sep 21 '11 at 19:16
add comment

3 Answers

up vote 3 down vote accepted

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

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

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

share|improve this answer
add comment

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.

share|improve this answer
    
Suppose $a=0$ and $b=0$, what would $c$ be? –  robjohn Sep 21 '11 at 14:48
    
Does that mean that c = 2n+1? –  Gbean Sep 21 '11 at 14:52
    
@Gbean: it would need to be, but that is too big for $c$. –  robjohn Sep 21 '11 at 14:59
    
How is it too big for c? –  Gbean Sep 21 '11 at 15:20
    
@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. –  robjohn Sep 21 '11 at 17:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.