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.
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
Explanation:
We can enumerate the valid sequences as follows:
Noting that there may be at most three
#+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
Notes
Using this kind of approach we can manually or with computer assistance find the number of valid sequences for
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.