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. How many valid lists are there?

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.

1 Answer
George C.
Aug 9, 2018

#35#

Explanation:

We can enumerate the valid sequences as follows:

Noting that there may be at most three #-1's#, we can write down the possibilities hierarchically. For each valid sequence with less than three #-1#'s, write out nested possibities below it with #-1#'s in each possible position that occurs after the existing #-1#'s:

#+1, +1, +1, +1, +1, +1, +1#

#+1, color(red)(-1), +1, +1, +1, +1, +1#

#+1, color(red)(-1), +1, color(red)(-1), +1, +1, +1#

#+1, color(red)(-1), +1, color(red)(-1), +1, color(red)(-1), +1#

#+1, color(red)(-1), +1, color(red)(-1), +1, +1, color(red)(-1)#

#+1, color(red)(-1), +1, +1, color(red)(-1), +1, +1#

#+1, color(red)(-1), +1, +1, color(red)(-1), color(red)(-1), +1#

#+1, color(red)(-1), +1, +1, color(red)(-1), +1, color(red)(-1)#

#+1, color(red)(-1), +1, +1, +1, color(red)(-1), +1#

#+1, color(red)(-1), +1, +1, +1, color(red)(-1), color(red)(-1)#

#+1, color(red)(-1), +1, +1, +1, +1, color(red)(-1)#

#+1, +1, color(red)(-1), +1, +1, +1, +1#

#+1, +1, color(red)(-1), color(red)(-1), +1, +1, +1#

#+1, +1, color(red)(-1), color(red)(-1), +1, color(red)(-1), +1#

#+1, +1, color(red)(-1), color(red)(-1), +1, +1, color(red)(-1)#

#+1, +1, color(red)(-1), +1, color(red)(-1), +1, +1#

#+1, +1, color(red)(-1), +1, color(red)(-1), color(red)(-1), +1#

#+1, +1, color(red)(-1), +1, color(red)(-1), +1, color(red)(-1)#

#+1, +1, color(red)(-1), +1, +1, color(red)(-1), +1#

#+1, +1, color(red)(-1), +1, +1, color(red)(-1), color(red)(-1)#

#+1, +1, color(red)(-1), +1, +1, +1, color(red)(-1)#

#+1, +1, +1, color(red)(-1), +1, +1, +1#

#+1, +1, +1, color(red)(-1), color(red)(-1), +1, +1#

#+1, +1, +1, color(red)(-1), color(red)(-1), color(red)(-1), +1#

#+1, +1, +1, color(red)(-1), color(red)(-1), +1, color(red)(-1)#

#+1, +1, +1, color(red)(-1), +1, color(red)(-1), +1#

#+1, +1, +1, color(red)(-1), +1, color(red)(-1), color(red)(-1)#

#+1, +1, +1, color(red)(-1), +1, +1, color(red)(-1)#

#+1, +1, +1, +1, color(red)(-1), +1, +1#

#+1, +1, +1, +1, color(red)(-1), color(red)(-1), +1#

#+1, +1, +1, +1, color(red)(-1), color(red)(-1), color(red)(-1)#

#+1, +1, +1, +1, color(red)(-1), +1, color(red)(-1)#

#+1, +1, +1, +1, +1, color(red)(-1), +1#

#+1, +1, +1, +1, +1, color(red)(-1), color(red)(-1)#

#+1, +1, +1, +1, +1, +1, color(red)(-1)#

I count #35# valid sequences.

Notes

Using this kind of approach we can manually or with computer assistance find the number of valid sequences for #n=1, 2, 3,...#

We can then look up the resulting sequence in the online encyclopedia of integer sequences https://oeis.org . They almost certainly have an entry for it with some interesting information.

Related questions
Impact of this question
1380 views around the world
You can reuse this answer
Creative Commons License