Vtyjkyuk

I received a word problem that goes like this.

A local kindergarten is thinking of making posters that show all the different ways of adding two or more integers from 1 to 9 to get a sum of 10. If there is enough space on each poster for up to 50 possible solutions, how many posters will the school need to make?

(Note: sums that contain the same number but in a different order are considered to be different; for example, 1 + 9 and 9 + 1 are two different solutions.)

What is the answer to this problem, and more importantly, how do I solve it?

Imagine $10$ ones in a row, and insert plus signs between them; for instance, $|||+||+|||||$ stands for the sum $3+2+5$. So the sums you want to count correspond to the ways of inserting plus signs. There are $9$ slots between the $10$ ones, and you can either insert a plus sign or not in each of them independently, so the number of different ways of doing this is $2^9$. However, one of these corresponds to inserting no plus signs at all, which doesn't yield a sum of at least two numbers, so we have to subtract that and the result is $2^9-1=512-1=511$.

We realize that the requirement of each number being at least $1$ and the sum being $10$ removes the need to cap the number at $9$, so we shall ignore that condition.

Let's first start with the case of two integers. Realize that we can visualize this problem as us having 10 coins and two buckets, and we have to drop coins in each bucket. Each way we can drop coins is a different sum, i.e., if I drop 6 coins in the first bucket, but 4 in the second, then the equivalent sum is $6+4$.

But, we must make sure every bucket has a positive number of coins, so we put one coin in each bucket to start. So, we have 8 coins left to distribute across 2 buckets. So, we can represent this as

********|

Where the bar marks the divider between the buckets. So, we are essentially counting the number of ways to arrange those symbols, which is $9choose1=9$.

We can apply the same logic with three buckets, to get the following symbol list:

*******||

So, the number of ways to arrange the symbols is $9choose2=36$.

We do this all the way to $9choose9=1$. So our answer is $$sumlimits_n=1^99choose n=511$$