Results 1 to 2 of 2

Math Help - Number of Valid Lists in a Combination

  1. #1
    Newbie
    Joined
    Jul 2011
    Posts
    6

    Number of Valid Lists in a Combination

    Quote Originally Posted by Puzzle
    Seven numbers, each 1 or -1, are listed in a row in such a way that adding the numbers successively from left to right never gives a negative answer. For example, 1 -1 1 1 -1 -1 1 has successive sums 1, 0, 1, 2, 1, 0, 1 and is valid, while 1 1 -1 -1 -1 1 1 has successive sums 1, 2, 1, 0, -1, 0, 1, and is not valid. How many valid lists are there?
    Well, it's more of help I'm seeking for rather than providing a puzzle to be solved (but who knows, maybe it'll be enjoyable for you to help solve it? :3).

    Anyway, I worked out that there are three combinations that would result in a positive answer (i.e. > 0), irrespective of position. Then for each possible combination I worked out how many variations in positioning there would be, as shown below:



    So in total, there are 18 possible combinations (7+6+5). Is this answer correct?


    EDIT: I'm an idiot, lol =.=
    Last edited by NewUser01; July 31st 2012 at 11:03 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    Re: Number of Valid Lists in a Combination

    Clearly, the first number is 1 and there can be at most three -1's in the sequences. There are \binom{7}{0} + \binom{7}{1} + \binom{7}{2} + \binom{7}{3} = 64 possible sequences with at most three -1's. We count the number of invalid sequences of at most three -1's and subtract from 64. Invalid sequences can occur in one of these cases:

    Case 1: 1,-1,-1,...

    Case 2: 1,1,-1,-1,-1,...

    Case 3: 1,-1,1,-1,-1,...

    Case 1 can occur in 16 ways, and cases 2 and 3 can occur in 4 ways each (no overlap), and 16+4+4 = 24. Hence the answer is 64-24 = 40.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Total number of combinations for combination lock
    Posted in the Advanced Statistics Forum
    Replies: 6
    Last Post: December 26th 2011, 10:11 AM
  2. 3-lists taken from [3]
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 18th 2010, 08:20 AM
  3. valid,non valid arguments
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 8th 2009, 06:12 PM
  4. Number Theory GCD Linear Combination
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 14th 2008, 12:08 AM
  5. number of combination of 8 digits number
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 7th 2008, 03:37 AM

Search Tags


/mathhelpforum @mathhelpforum