7
$\begingroup$

How many positive integer solutions does the equation $a+b+c=100$ have if we require $a<b<c$?

I know how to solve the problem if it was just $a+b+c=100$ but the fact it has the restriction $a<b<c$ is throwing me off.

How would I solve this?

$\endgroup$
5
$\begingroup$

First we count the number of triples of positive integers $(a, b, c)$ with $a + b + c = 100$. There are $\binom{99}{2}$ of them, which results from an elementary application of stars and bars. Just line up a hundred dots, place a bar in between the $a$th and $(a +1)$th dot, and then place another bar $b$ dots to the right of the first one. Then $c$ is the number of dots to the right of the second bar. There are 99 spaces in between a hundred dots and you're choosing two of them to place bars in.

This is an overcount since it doesn't account for the condition $a < b < c$. First we should subtract the number of triples in which $a, b, c$ are not all distinct. There are 49 triples such that $a = b$: to count them, choose $x$ with $ 0 < x<50$, set $a = b = x$ and $c = 100-2x$. This accounts for all possible cases since if $a = b \ge 50$ then $c$ is not positive. There are also 49 triples with $a = c$, or with $b = c$, respectively. There are no triples with $a = b = c$, so the total number of triples with $a , b, c$ not all distinct is $3*49 = 147$.

The number of triples of positive integers $(a, b, c)$ with $a, b, c$ distinct and $a + b + c = 100$ is therefore $\binom{99}{2} -147$. Given a triple $(a, b, c)$ with $a< b < c$ and $a + b + c = 100$, there are six distinct ways to permute $a, b, c$, all of which our current estimate accounts for. Therefore we should divide by 6 to throw out all the triples that are in the wrong order. The final answer is $\frac{1}{6}(\binom{99}{2} -147) = 784$.

$\endgroup$
0
$\begingroup$

Hint: For each possible value of $a$, count the number of possible values of $b$ and $c$. It's a quite regular pattern, so you don't have to brute force much to find it.

$\endgroup$
0
$\begingroup$

Since $a$ is the smallest, the largest number it can be is $32$, so $a$ ranges from $1$ to $32$. The remaining sum $b+c$ must be equal to $100 - a$ and since $b$ is smaller than $c$ then $b$ ranges from $a+1$ to $\lfloor \frac{100-a}{2}\rfloor $. So for a given $a$ there are $\lfloor \frac{100-a}{2}\rfloor - a -1$ different $b$s one can choose. Therefore the possible permutations are

$$\sum_{a=1}^{32} \lfloor \frac{100-a}{2}\rfloor - a -1$$

$$=\sum_{a=1}^{32} \lfloor \frac{100-a}{2}\rfloor - \sum_{a=1}^{32}a -32 $$ $$ = 2\sum_{a=34}^{49}a - \sum_{a=1}^{32}a -32$$ $$=49(50) - 34(33) - \frac{32(33)}{2} -32= 768$$

EDIT:

Following the comments of Vik, it is quite clear that since we are including the case $b = a +1$ the expression should change to $$\sum_{a=1}^{32} \lfloor \frac{100-a}{2}\rfloor - a $$ However as Vik also mentioned this is an over estimate as it would also give us the combination where we have $b = c= (100-a)/2$ the case where $a$ is even. Since $b$ is strictly less than $c$, we need to remove $16$ off of our expression as there are 16 cases of when $a$ is even. Therefore, we get $$\sum_{a=1}^{32}( \lfloor \frac{100-a}{2}\rfloor - a) - 16= 784$$

$\endgroup$
  • 1
    $\begingroup$ Hey, note that the range you can choose $b$ in is actually from $a + 1$ to $\lfloor{(100-a)/2} \rfloor$, inclusive of both endpoints. Therefore you shouldn't be summing $\lfloor{(100-a)/2} \rfloor - (a + 1)$: that excludes the possibility $b = a + 1$. Instead you should sum $\lfloor{(100-a)/2} \rfloor - a$. $\endgroup$ – Vik78 Apr 2 '17 at 9:25
  • 1
    $\begingroup$ Also I think this is an overcount, since it includes several possibilities where $b = c$ (which occurs whenever $b = (100-a)/2$). $\endgroup$ – Vik78 Apr 2 '17 at 9:36
  • 1
    $\begingroup$ Oh yes you are right my bad. I'll edit to fix this but either way I found your solution much more elegant and has a result upvoted. :) $\endgroup$ – Ziad Fakhoury Apr 2 '17 at 9:39
0
$\begingroup$

$a<b<c$ can be translated by $b=a+x$ and $c=b+y=a+(x+y)$, where $a,x,y>0$. $$a + b + c = 100\iff a+a+x+a+x+y=100 \iff3a+2x+y=100$$

Let $a_k$ the number of solutions of the diophantine equation $3a+2x+y=k$, where $a,x,y>0$.

$$\sum_{d=0}^\infty a_k t^k=\sum_{k=0}^\infty(\sum_{3a+2x+y=k\\a,x,y>0}t^k)=(\sum_{k=1}^\infty t^{3k})(\sum_{k=1}^\infty t^{2k})(\sum_{k=1}^\infty t^{k})=\frac{t^6}{(1-t^3)(1-t^2)(1-t)}$$

We will calculate explecitely $a_k$ now : $$\frac{t^6}{(1-t^3)(1-t^2)(1-t)}\\=\frac{t + 2}{9 (t^2 + t + 1))} - \frac{89}{72 (t - 1)} + \frac{1}{8 (t + 1)} - \frac{3}{4 (t - 1)^2} -\frac{1}{6 (t - 1)^3}-1\\=\sum_{n=1}^∞ t^n\frac{1}{72} (47 + 9 (-1)^n + 8 e^{-(2 i n π)/3} + 8 e^{(2 i n π)/3} + 6 n^2-36n)\\=\sum_{n=1}^∞ t^n\frac{1}{72} (47 + 9 (-1)^n + 16\cos(2\pi \frac{n}{3}) + 6 n^2-36n)$$

So : $$a_{100}=\frac{1}{72} (47+9 -8 +60000-3600)=784$$

$\endgroup$
0
$\begingroup$

By stars and bars there are ${99\choose2}$ nonnegative solutions to the equation $x_1+x_2+x_3=97$. Among these there are $3\cdot49$ having two equal $x_i\in[0\ ..\ 48]$, so that there are $${1\over6}\left({99\choose2}-3\cdot49\right)=784$$ solutions satisfying $x_1<x_2<x_3$. For each of these the numbers $a:=1+x_1$, $b:=1+x_2$, $c:=1+x_3$ form an admissible triple.

$\endgroup$

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.