6
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ This problem can be extended to continuous setting: Imagine a circular, continuous circuit, with a finite number of gas tanks located at some points around the circuit. Every gas tank contains a finite quantity of gas. The total quantity of gas in gas tanks around the circuit is greater than or equal to the quantity of gas required for a car to drive around the circuit. You drive around the circuit with a car, refilling the car's tank when you can. Assuming the car's tank is initially empty, but has unbounded capacity, prove there exists a starting point that allows to complete the circuit. $\endgroup$
    – Stef
    Nov 29 '21 at 13:46
19
$\begingroup$

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.

enter image description here

$\endgroup$
3
  • $\begingroup$ This is how I would do it too. In short, there is always a node with the minimum cumulative value. We can start from there. $\endgroup$
    – justhalf
    Nov 28 '21 at 14:38
  • $\begingroup$ How do we prove that there's always a node with the minumum cumulative value? $\endgroup$
    – Tita
    Nov 29 '21 at 18:18
  • 2
    $\begingroup$ @Tita The set of nodes is finite. $\endgroup$
    – Steven
    Nov 29 '21 at 19:11
12
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.