0
$\begingroup$

$100$ can be divided into the sum of several numbers as $1+99$ or $1+1+98$, and we set all the numbers have to be positive. Besides, $1+99$ is different from $99+1$. How many different possibilities are there?

I start to divide $100$ into the sum of two numbers. There are 99 possibilities.

Then divide $100$ into the sum of three numbers. There are $98+97+\dots+1$ possibilities.

Then divide $100$ into the sum of four numbers. For example $1+a+b+c=100$. Then there are $97+96+\dots+1$ ways to write $a,b,c$. For $2+a'+b'+c'=100$, there are $96+95+\dots+1$ ways to write $a',b',c'$.

However I don't think this approach is promising. Is there any feasible way to solve this problem?

$\endgroup$
4
$\begingroup$

There are $\binom{n-1}{r-1}$ integer solutions $(x_1 ,\ldots, x_r)$, all $\ge 1$ to $x_1 + x_2 + \ldots x_r =n$ , see here, e.g.

You want this for all $r=1,\dots 100$, just sum these:

$$\sum_{r=1}^{100} \binom{99}{r-1} = 2^{99}$$

I think the following combinatorial argument works: write $100 = 1 + \ldots + 1$, now we can either leave or delete one of the 99 $+$-signs ((and when deleting combine the numbers on both sides): e.g. for $n=3 = 1 + 1 + 1$, deleting none leaves 3 =1 + 1 +1 , deleting the first + leaves 3 = 2 + 1, deleting the second 1+2, deleting all leaves 3 = 3, etc., so $2^2$ solutions in all, if you don't want the last trivial one, subtract 1 from my answer. )

$\endgroup$
  • $\begingroup$ The combinatorial argument uses the technique known as stars and bars; more can be found on its wikipage here. $\endgroup$ – Benjamin Dickman Mar 26 '17 at 9:33
  • $\begingroup$ @BenjaminDickman The first one does, my reasoning for the final answer does not use this technique. $\endgroup$ – Henno Brandsma Mar 26 '17 at 11:29

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.