Results 1 to 8 of 8
Like Tree3Thanks
  • 1 Post By Plato
  • 1 Post By SlipEternal
  • 1 Post By romsek

Thread: Combination Problem Involving Numbers 1-9 to Form a Sum of 10

  1. #1
    Newbie
    Joined
    Sep 2018
    From
    U.S.
    Posts
    1

    Combination Problem Involving Numbers 1-9 to Form a Sum of 10

    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?

    To make clear, a solution such as, "1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1," is a valid one.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,078
    Thanks
    2981
    Awards
    1

    Re: Combination Problem Involving Numbers 1-9 to Form a Sum of 10

    Quote Originally Posted by JollyJack View Post
    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?
    To make clear, a solution such as, "1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1," is a valid one.
    Consider $3 + 2 + 2 + 1 + 1 + 1 + 1 + 1$ that sum is $10$.
    But those eight digits can be arranged in $\dfrac{8!}{(5!)(2!)}=168$ ways.
    Personally I doubt that your idea that order makes a difference is correct.

    This general question is well known as integer partitions into sums.
    But order makes no difference.
    Last edited by Plato; Sep 10th 2018 at 04:44 PM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Dec 2016
    From
    Earth
    Posts
    216
    Thanks
    100

    Re: Combination Problem Involving Numbers 1-9 to Form a Sum of 10

    Quote Originally Posted by Plato View Post
    Consider $3 + 2 + 2 + 1 + 1 + 1 + 1 + 1$ that sum is $10$.<br>
    But those eight digits can be arranged in $\dfrac{8!}{(5!)(2!)}=168$ ways.

    That accidental sum is 12 instead of the intended 10. I was wondering what you intended the actual addends to be for your example.
    Last edited by greg1313; Sep 10th 2018 at 08:29 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,078
    Thanks
    2981
    Awards
    1

    Re: Combination Problem Involving Numbers 1-9 to Form a Sum of 10

    Quote Originally Posted by greg1313 View Post
    That accidental sum is 12 instead of the intended 10. You are a combinations expert,
    so I was wondering what you intended the actual addends to be for your example.
    No you are correct. I JUST CAN'T ADD. I wanted $3+2+2+1+1+1$
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,722
    Thanks
    1515

    Re: Combination Problem Involving Numbers 1-9 to Form a Sum of 10

    Quote Originally Posted by JollyJack View Post
    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?

    To make clear, a solution such as, "1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1," is a valid one.
    Suppose there is exactly 1 plus sign. We will use dots and a single plus sign. A valid configuration would be something like this:
    .+......... (which represents 1+9)
    We know there must be at least one dot to the right of the plus, so we will treat +. as a single symbol. We cannot start the pattern with a +, so we will place a single . to the far left. That leaves 8 dots and the +. We permute everything but the left-most dot (which is fixed). There are $\dbinom{9}{1} = 9$ such permutations.

    Suppose there are exactly 2 plus signs. We place the left-most . again. Then, we have +. and +. along with seven other .'s. We permute everything but the left-most .: $\dbinom{9}{2}$ ways.

    Suppose there are exactly 3 plus signs. We place the left-most . again. Then we have 3x '+.' and 6x '.' for which there are $\dbinom{9}{3}$ permutations of these nine symbols (we do not permute the left-most .).

    We see the pattern and get:

    $$\sum_{i=1}^9 \dbinom{9}{i} = 2^9-1 = 511$$

    I believe that is the correct number of sums, but I have not double-checked my work.

    It would then take 11 posters.
    Last edited by SlipEternal; Sep 10th 2018 at 09:38 PM.
    Thanks from romsek
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,078
    Thanks
    2981
    Awards
    1

    Re: Combination Problem Involving Numbers 1-9 to Form a Sum of 10

    I still doubt that the OP means to ask the question that implies that order makes a difference.
    This is a well known question about integer partitions.
    Look at this webpage.
    Now my subscription is for WolframalphaPro. So I hope all can see that there are 42 partitions of 10.
    But for this problem, using only single digits there would be only 41.
    Here they are:Combination Problem Involving Numbers 1-9 to Form a Sum of 10-part10.gif
    If from that list we choose $3+2+2+1+1+1=10$ and order makes a difference, then there are $\dfrac{6!}{(2!)(3!)}=60$ in that count.
    So we would need to do that for each of the 41 cases.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,722
    Thanks
    1515

    Re: Combination Problem Involving Numbers 1-9 to Form a Sum of 10

    Quote Originally Posted by Plato View Post
    I still doubt that the OP means to ask the question that implies that order makes a difference.
    This is a well known question about integer partitions.
    Look at this webpage.
    Now my subscription is for WolframalphaPro. So I hope all can see that there are 42 partitions of 10.
    But for this problem, using only single digits there would be only 41.
    Here they are:Click image for larger version. 

Name:	part10.gif 
Views:	5 
Size:	19.8 KB 
ID:	38938
    If from that list we choose $3+2+2+1+1+1=10$ and order makes a difference, then there are $\dfrac{6!}{(2!)(3!)}=60$ in that count.
    So we would need to do that for each of the 41 cases.
    Combination Problem Involving Numbers 1-9 to Form a Sum of 10-sums.png

    This indicates that if order matters, my answer above was correct.

    Also, there is a fairly straightforward combinatorial argument. Consider the initial string:

    1+1+1+1+1+1+1+1+1+1

    There are 9 pluses. If we remove a plus, we add the adjacent digits together. Example, if we remove the first plus, we get:
    11+1+1+1+1+1+1+1+1
    which becomes
    2+1+1+1+1+1+1+1+1

    So, if we consider the nine element set of positions of pluses, each ordered sum is in one-to-one bijection with a subset of this set of nine positions. The only subset that is not matched to a sum is the empty set (no pluses, which would just be the number 10). So, since there are $2^9$ subsets of the nine element set, and we remove the empty set, there are $2^9-1=511$ nonempty subsets, which is equal to the number of ordered sums.
    Last edited by SlipEternal; Sep 11th 2018 at 06:23 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    6,316
    Thanks
    2712

    Re: Combination Problem Involving Numbers 1-9 to Form a Sum of 10

    511 is the number I get as well.
    Thanks from SlipEternal
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combination problem involving book selling.
    Posted in the Statistics Forum
    Replies: 3
    Last Post: Jan 21st 2014, 02:57 PM
  2. Replies: 7
    Last Post: Aug 16th 2012, 04:46 PM
  3. [SOLVED] A problem involving complex numbers in polar form
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: Sep 2nd 2010, 01:13 PM
  4. combinatorics problem involving even numbers?
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Sep 22nd 2009, 03:20 PM
  5. Combination Problem Involving Alphabet
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Dec 8th 2008, 07:17 AM

Search Tags


/mathhelpforum @mathhelpforum