patternModerate
Proof that for 2n nodes of +1 and -1 position doesn't count
Viewed 0 times
nodespositiondoesnthatforandcountproof
Problem
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:
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?
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:
- We win after we've gone through all the nodes, and
- 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?
Solution
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.
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.
Context
StackExchange Computer Science Q#146157, answer score: 19
Revisions (0)
No revisions yet.