Proof that for 2n nodes of +1 and -1 position doesn't count

Question

I'm having a hard time understanding how to solve this problem for my Computer Science 101 class.

On a circle there are $2n$ nodes. $n$ out of these hold -1 power and $n$ hold +1 power. Say we play a game where we randomly start from a node and move clockwise. As we move and land on different nodes, the number on each node we land on is added to our score. So, if we jump from a +1 node to a -1 and then a +1 our score is 1. The rules are:

1. We win after we've gone through all the nodes, and
2. If our score drops to -1 at any point we lose.

The question is to prove that for any random sequence, it doesn't matter which, there's always at least one node we can start from that lets us win the game.

I started first by stating the information a bit differently:

a) I can only start from a +1 node, which would leave any player with $2n+1$ nodes where $n$ nodes are -1.

b) There are $2^{n}$ possible sets of positions, but because for any one of these I can start anywhere the $n$ permuatations, we have $\frac{2^{n}}{n}$ possible games.

I first thought that I could show that the question's assertion holds by creating a DFA that would read the language $L=\{w \in \{-1,+1\} \text{ : sum never becomes -1}\}$. I made it with $q_0$ as my starting state with $n$ states on its right and one on the left with appropriate transitions for -1 and +1. But all that shows is that some $w$s fail and some do not. It doesn't prove that in a set of our nodes there's at least one possible node to pick so we can win.

Any ideas on how I can prove that?

Answer 1

You can prove the claim by induction on $n$. If $n=1$ the claim is clearly true since it suffices to start from the unique "+1" node.

When $n > 1$, let $u$ and $v$ be two consecutive nodes (moving clockwise) such that $u$ is a "+1" node and $v$ is a "-1" node. This pair always exists. By induction hypothesis there is some vertex $w$ that allows you to win the game in the instance with $2n-2$ nodes obtained by deleting $u$ and $v$. Then, starting from $w$ also wins the original instance with $n$ nodes.

Answer 2

Not a complete proof, but a picture that hints to a solution.

If you start at a random point and add the numbers, then after a complete circle you end again at the initial zero. Track all the intermediate scores. If we start at the node with minimal score you will never get a negative score.